Хеширование

Разбить на страницы

Показывать лекцию целиком

Рассмотренные нами алгоритмы поиска обычно основаны на абстрактной операции сравнения. Из этого ряда существенно выделяется метод распределяющего поиска, описанный в , при котором элемент с ключом i хранится в i-ой позиции таблицы, что позволяет обратиться к нему непосредственно. При распределяющем поиске значения ключей используются в качестве индексов массива, а не операндов операции сравнения; сам метод основан на том, что ключи являются различными целыми числами из того же диапазона, что и индексы таблицы. В этой главе мы рассмотрим хеширование (hashing) — расширенный вариант распределяющего поиска, применяемый в более типичных приложениях поиска, где ключи не обладают столь удобными свойствами. Конечный результат применения данного подхода совершенно не похож на методы, основанные на сравнении — вместо перемещения по структурам данных словаря с помощью сравнения ключей поиска с ключами в элементах, мы пытаемся обратиться к элементам в таблице непосредственно, выполняя арифметическое преобразование ключей в адреса таблицы.

Алгоритмы поиска, использующие хеширование, состоят из двух отдельных частей. Первый шаг — вычисление хеш-функции (hash function), которая преобразует ключ поиска в адрес в таблице. В идеале различные ключи должны были бы отображаться на различные адреса, но часто два или более различных ключа могут дать один и тот же адрес в таблице. Поэтому вторая часть поиска методом хеширования — процесс разрешения коллизий (collision resolution), который обрабатывает такие ключи. В одном из методов разрешения конфликтов, который мы рассмотрим в этой главе, используются связные списки, поэтому он находит непосредственное применение в динамических ситуациях, когда трудно заранее предугадать количество ключей поиска. В других двух методах разрешения коллизий достигается высокая производительность поиска, поскольку элементы хранятся в фиксированном массиве. Мы рассмотрим способ усовершенствования этих методов, позволяющий использовать их и в тех случаях, когда нельзя заранее предсказать размеры таблицы.

Хеширование — хороший пример баланса между временем и объемом памяти. Если бы не было ограничения на объем используемой памяти, любой поиск можно было бы выполнить с помощью всего лишь одного обращения к памяти, просто используя ключ в качестве адреса памяти, как при распределяющем поиске. Однако обычно этот идеальный случай недостижим, поскольку для длинных ключей может потребоваться огромный объем памяти. С другой стороны, если бы не было ограничений на время выполнения, можно было бы обойтись минимальным объемом памяти, пользуясь методом последовательного поиска. Хеширование представляет собой способ использования приемлемого объема как памяти, так и времени, и достижения баланса между этими двумя крайними требованиями. В частности, можно поддерживать любой баланс, просто меняя размер таблицы, а не переписывая код и не выбирая другие алгоритмы.

Хеширование — одна из классических задач компьютерных наук: его различные алгоритмы подробно исследованы и находят широкое применение. Мы увидим, что при совсем не жестких допущениях можно надеяться на поддержку операций найти и вставить в таблицах символов с постоянным временем выполнения, независимо от размера таблицы.

Это ожидаемое значение — теоретический оптимум производительности для любой реализации таблицы символов, но хеширование все же не является панацеей по двум основным причинам. Во-первых, время выполнения зависит от длины ключа, которая в реальных приложениях, использующих длинные ключи, может быть значительной. Во-вторых, хеширование не обеспечивает эффективные реализации других операций с таблицами символов, таких, как выбрать или сортировать. В этой главе мы подробно рассмотрим эти и другие вопросы.

Хеш-функции

Прежде всего необходимо решить задачу вычисления хеш-функции, преобразующей ключи в адреса таблицы. Обычно реализация этого арифметического вычисления не представляет сложности, но все же необходимо соблюдать осторожность, чтобы не нарваться на различные малозаметные подводные камни. При наличии таблицы, которая может содержать M элементов, нужна функция, преобразующая ключи в целые числа в диапазоне [0, M — 1]. Идеальная хеш-функция должна легко вычисляться и быть похожей на случайную функцию: для любых аргументов результаты в некотором смысле должны быть равновероятными.

Хеш-функция зависит от типа ключа. Строго говоря, для каждого возможного вида ключей требуется отдельная хеш-функция. Для повышения эффективности обычно желательно избегать явного преобразования типов, обратившись вместо этого к идее рассмотрения двоичного представления ключей в машинном слове в виде целого числа, которое можно использовать в арифметических вычислениях. Хеширование появилось до языков высокого уровня — на ранних компьютерах было обычным делом рассматривать какое-либо значение то как строковый ключ, то как целое число. В некоторых языках высокого уровня затруднительно создавать программы, которые зависят от представления ключей в конкретном компьютере, поскольку такие программы, по сути, являются машинно-зависимыми, и поэтому их трудно перенести на другой компьютер. Обычно хеш-функции зависят от процесса преобразования ключей в целые числа, поэтому в реализациях хеширования бывает трудно одновременно обеспечить и машинную независимость, и эффективность. Как правило, простые целочисленные ключи или ключи типа с плавающей точкой можно преобразовать с помощью всего одной машинной операции, но строковые ключи и другие типы составных ключей требуют больших затрат и большего внимания к эффективности.

Вероятно, простейшей является ситуация, когда ключами являются числа с плавающей точкой из фиксированного диапазона. Например, если ключи — числа, большие 0 и меньшие 1, их можно просто умножить на M, округлить результат до меньшего целого числа и получить адрес в диапазоне между 0 и . Если ключи больше s и меньше t, их можно масштабировать, вычтя s и разделив на t—s, в результате чего они попадут в диапазон значений между 0 и 1, а затем умножить на M и получить адрес в таблице.

(рис 14.1) Мультипликативная хеш-функция для ключей с плавающей точкой

Для преобразования чисел с плавающей точкой в диапазоне между 0 и 1 в индексы таблицы, размер которой равен 97, выполняется умножение этих чисел на 97. В данном примере произошло три коллизии: для индексов, равных 17, 53 и 76. Хеш-значения определяются старшими разрядами ключа, младшие разряды не играют никакой роли. Одна из целей разработки хеш-функции — устранение такого дисбаланса, чтобы во время вычисления учитывался каждый разряд.

Если ключи являются w-разрядными целыми числами, их можно преобразовать в числа с плавающей точкой и разделить на 2^w для получения чисел с плавающей точкой в диапазоне между 0 и 1, а затем умножить на M, как в предыдущем абзаце. Если операции с плавающей точкой занимают много времени, а числа не столь велики, чтобы привести к переполнению, этот же результат может быть получен с помощью целочисленных арифметических операций: нужно ключ умножить на M, а затем выполнить сдвиг вправо на w разрядов для деления на 2^w (или, если умножение приводит к переполнению, выполнить сдвиг, а затем умножение). Такие методы бесполезны для хеширования, если только ключи не распределены по диапазону равномерно, поскольку хеш-значение определяется только ведущими цифрами ключа.

Более простой и эффективный метод для w-разрядных целых чисел — один из, пожалуй, наиболее часто используемых методов хеширования — выбор в качестве размера M таблицы простого числа и вычисление остатка от деления к на M, т.е. .

(рис 14.2) Модульная хеш-функция для целочисленных ключей

В трех правых столбцах показан результат хеширования 16-разрядных ключей, приведенных слева, с помощью следующих функций:

v % 97 (слева)

v % 100 (в центре) и

(int) (a * v) % 100 (справа),

где a = .618033. Размеры таблицы для этих функций соответственно равны 97, 100 и 100. Значения выглядят случайными (поскольку случайны ключи). Вторая функция (v % 100) использует лишь две крайние правые цифры ключей и поэтому для неслучайных ключей может показывать низкую производительность.

Модульное хеширование применимо и к ключам с плавающей точкой. Если ключи принадлежат небольшому диапазону, можно масштабировать их в числа из диапазона между 0 и 1, 2^w для получения w-разрядных целочисленных значений, а затем использовать модульную хеш-функцию. Другой вариант — просто использовать в качестве операнда модульной хеш-функции двоичное представление ключа (если оно доступно).

Модульное хеширование применяется во всех случаях, когда имеется доступ к битам, из которых состоят ключи, независимо от того, являются ли они целыми числами, представленными машинным словом, последовательностью символов, упакованных в машинное слово, или представлены любым другим возможным вариантом. Последовательность случайных символов, упакованная в машинное слово — не совсем то же, что случайные целочисленные ключи, поскольку не все разряды используются для кодирования. Но оба эти типа (и любой другой тип ключа, закодированный так, чтобы уместиться в машинном слове) можно заставить выглядеть случайными индексами в небольшой таблице.

Основная причина выбора в качестве размера M хеш-таблицы простого числа для модульного хеширования показана на рис 14.3. В этом примере символьных данных с 7-разрядным кодированием ключ трактуется как число с основанием 128 — по одной цифре для каждого символа в ключе. Слово now соответствует числу 1816567, которое может быть также записано как $$$$110 \cdot 128^{2} + 111 \cdot 128^{1} + 119 \cdot 128^{0}$$$$

поскольку в ASCII-коде символам n, o и w соответствуют числа 1568 = 110, 1578 = 111 и 1678 = 119. Выбор размера таблицы M = 64 для этого типа ключа неудачен, поскольку добавление к х значений, кратных 64 (или 128), не меняет значение х mod 64 — для любого ключа значением хеш-функции является значение последних 6 разрядов этого ключа. Безусловно, хорошая хеш-функция должна учитывать все разряды ключа, особенно для символьных ключей. Аналогичные ситуации могут возникать, когда M содержит множитель, являющийся степенью 2. Простейший способ избежать этого — выбрать в качестве M простое число.

(рис 14.3) Модульные хеш-функции для кодированных символов

В каждой строке этой таблицы приведены: 3-буквенное слово, представление этого слова в ASCII-коде как 21-битовое число в восьмеричной и десятичной формах и стандартные модульные хеш-функции для размеров таблиц 64 и 31 (два крайних справа столбца). Размер таблицы 64 приводит к нежелательным результатам, поскольку для получения хеш-значения используются только самые правые разряды ключа, а буквы в словах обычного языка распределены неравномерно. Например, всем словам, оканчивающимся на букву у, соответствует хеш-значение 57. И, напротив, простое значение 31 вызывает меньше коллизий в таблице более чем вдвое меньшего размера.

Модульное хеширование очень просто реализовать, за исключением того, что размер таблицы должен быть простым числом. Для некоторых приложений можно довольствоваться небольшим известным простым числом или же поискать в списке известных простых чисел такое, которое близко к требуемому размеру таблицы. Например, числа равные 2^t — 1, являются простыми при ). Использование модульного хеширования — не единственная причина, по которой размер таблицы стоит сделать простым числом; еще одна причина рассматривается в разделе 14.4.

(рис 14.4) Простые числа для хеш-таблиц

Эта таблица наибольших простых чисел, меньших 2ⁿ, для $$$8 \leq n\leq 32$$$, может использоваться для динамического распределения хеш-таблицы, когда нужно, чтобы размер таблицы был простым числом. Для любого данного положительного значения в охваченном диапазоне эту таблицу можно использовать для определения простого числа, отличающегося от него менее чем в 2 раза.

Другой вариант обработки целочисленных ключей — объединение мультипликативного и модульного методов: нужно умножить ключ на константу в диапазоне между 0 и 1, а затем выполнить деление по модулю M. Другими словами, необходимо использовать функцию $$$h(k)= \lfloor{k \alpha}\rfloor \mod {M}$$$. Между значениями $$$\alpha$$$, M и эффективным основанием системы счисления ключа существует взаимосвязь, которая теоретически могла бы привести к аномальному поведению, но если использовать произвольное значение a, в реальном приложении вряд ли возникнет какая-либо проблема. Часто в качестве a выбирают значение ф = 0,618033... (золотое сечение).

Изучено множество других вариаций на эту тему, в частности, хеш-функции, которые могут быть реализованы с помощью таких эффективных машинных инструкций, как сдвиг и выделение по маске (см. раздел ссылок).

Во многих приложениях, в которых используются таблицы символов, ключи не являются числами и не обязательно являются короткими; чаще это алфавитно-цифровые строки, которые могут быть весьма длинными. Ну и как вычислить хеш-функцию для такого слова, как averylongkey?

В 7-разрядном ASCII-коде этому слову соответствует 84-разрядное число \begin{align*} 97 \cdot 128^{11} + 118 \cdot 128^{10} + 101 \cdot 128^{9} + 114 \cdot 128^{8} + 121 \cdot 128^{7}\\ + 108 \cdot 128^{6} + 111 \cdot 128^{5} + 110 \cdot 128^{4} + 103 \cdot 128^{3}\\ + 107 \cdot 128^{2} + 101 \cdot 128^{1} + 121 \cdot 128^{0}, \end{align*},

которое слишком велико, чтобы с ним можно было выполнять обычные арифметические функции в большинстве компьютеров. А зачастую требуется обрабатывать и гораздо более длинные ключи.

Чтобы вычислить модульную хеш-функцию для длинных ключей, они преобразуются фрагмент за фрагментом. Можно воспользоваться арифметическими свойствами функции модуля и использовать алгоритм Горнера (см. раздел 4.9 ). Этот метод основан на еще одном способе записи чисел, соответствующих ключам. Для рассматриваемого примера запишем следующее выражение: \begin{align*} ((((((((((97 \cdot 128^{11} + 118) \cdot 128^{10} + 101) \cdot 128^{9} + 114) \cdot 128^{8} + 121) \cdot 128^{7}\\ + 108) \cdot 128^{6} + 111) \cdot 128^{5} + 110) \cdot 128^{4} + 103) \cdot 128^{3}\\ + 107) \cdot 128^{2} + 101) \cdot 128^{1} + 121. \end{align*}

То есть десятичное число, соответствующее символьной кодировке строки, можно вычислить при просмотре ее слева направо, умножая накопленное значение на 128, а затем добавляя кодовое значение следующего символа. В случае длинной строки этот способ вычисления в конце концов приведет к числу, большему того, которое вообще можно представить в компьютере. Однако это число и не нужно, поскольку требуется только (небольшой) остаток от его деления на M. Результат можно получить, даже не сохраняя большое накопленное значение, т.к. в любой момент вычисления можно отбросить число, кратное M — при каждом выполнении умножения и сложения нужно хранить только остаток от деления по модулю M. Результат будет таким же, как если бы у нас имелась возможность вычислить длинное число, а затем выполнять деление (см. упражнение 14.10). Это наблюдение ведет к непосредственному арифметическому способу вычисления модульных хеш-функций для длинных строк — см. программу 14.1. В этой программе используется еще одно, последнее ухищрение: вместо основания 128 в ней используется простое число 127. Причина этого изменения рассматривается в следующем абзаце.

Существует множество способов вычисления хеш-функций приблизительно с теми же затратами, что и для модульного хеширования с использованием метода Горнера (одна-две арифметические операции для каждого символа в ключе). Для случайных ключей эти методы практически не отличаются друг от друга, но реальные ключи редко бывают случайными. Возможность ценой небольших затрат придать реальным ключам случайный вид приводит к рассмотрению рандомизированных алгоритмов хеширования, поскольку нам требуются хеш-функции, которые создают случайные индексы таблицы независимо от распределения ключей. Рандомизацию организовать нетрудно, поскольку вовсе не требуется буквально придерживаться определения модульного хеширования — нужно всего лишь, чтобы в вычислении целого числа, меньшего M, использовались все разряды ключа.

Программа 14.1. Хеш-функция для строковых ключей

Данная реализация хеш-функции для строковых ключей использует одно умножение и одно сложение для каждого символа в ключе. Если константу 127 заменить на 128, программа просто вычисляла бы методом Горнера остаток от деления числа, соответствующего 7-разрядному ASCII-представлению ключа, на размер таблицы. Простое основание, равное 127, помогает избежать аномалий, которые возникают, если размер таблицы является степенью 2 или кратным 2.

  int hash(char *v, int M)
    { int h = 0, a = 127;
      for (; *v != 0; v++)
        h = (a*h + *v) % M;
      return h;
    }

(рис 14.5) Хеш-функции для символьных строк

На этих диаграммах показано распределение для набора английских слов (первые 1000 различных слов романа Мел-вилла " Моби Дик " ) при использовании программы 14.1 с

M = 96 и a = 128 (вверху),

M = 97 и a = 128 (в центре) и

M = 96 и a = 127 (внизу)

Неравномерное распределение в первом случае является результатом неравномерного употребления букв и сохранения неравномерности из-за того, что и размер таблицы, и множитель кратны 32. Два других примера выглядят случайными, поскольку размер таблицы и множитель являются взаимно простыми числами.

В программе 14.1 показан один из способов сделать это: использование простого основания вместо степени 2 и целого числа, соответствующего ASCII-представлению строки. На рис. 14.5 рис 14.5 показано, как это изменение улучшает распределение для типичных строковых ключей. Теоретически хеш-значения, созданные программой 14.1, могут давать плохие результаты для размеров таблицы, которые кратны 127 (хотя на практике это, скорее всего, будет почти незаметно); для создания рандомизированного алгоритма можно было бы выбрать значение множителя наугад. Еще более эффективный подход — использование случайных значений коэффициентов в вычислении и различных случайных значений для каждой цифры ключа. Такой подход дает рандомизированный алгоритм, называемый универсальным хешированием (universal hashing).

Теоретически идеальная универсальная хеш-функция — это функция, для которой вероятность коллизии между двумя различными ключами в таблице размером M в точности равна 1/M. Можно доказать, что использование в качестве коэффициента а в программе 14.1 не фиксированного произвольного значения, а последовательности случайных различных значений преобразует модульное хеширование в универсальную хеш-функцию. Однако затраты на генерирование нового случайного числа для каждого символа в ключе обычно неприемлемы. На практике можно достичь компромисса, показанного в программе 14.1, не храня массив различных случайных чисел для каждого символа ключа, а варьируя коэффициенты с помощью генерации простой псевдослучайной последовательности.

Подведем итоги: чтобы для реализации абстрактной таблицы символов использовать хеширование, сначала необходимо расширить интерфейс абстрактного типа, включив в него операцию hash, которая отображает ключи на неотрицательные целые числа, меньшие размера таблицы M.

Непосредственная реализация

  inline int hash(Key v, int M)
    { return (int) M*(v-s)/(t-s); }

выполняет эту задачу для ключей с плавающей точкой со значениями между s и t; для целочисленных ключей можно просто вернуть значение v % M. Если M не является простым числом, хеш-функция может возвращать

  (int) (.616161 * (float) v) % M

или результат аналогичного целочисленного выражения, вроде

  (16161 * (unsigned) v) % M

Все эти функции, включая программу 14.1 для работы со строковыми ключами, проверены временем; они равномерно распределяют ключи и служат программистам в течение многих лет. Универсальный метод, представленный в программе 14.2 — заметное усовершенствование для строковых ключей, которое обеспечивает случайные хеш-значения при небольших дополнительных затратах; аналогичные рандомизированные методы можно применять и к целочисленным ключам (см. упражнение 14.1).

В конкретном приложении универсальное хеширование может работать значительно медленнее, чем более простые методы, поскольку при наличии длинных ключей выполнение двух арифметических операций для каждого символа в ключе может потребовать слишком много времени. Для обхода этого ограничения ключи можно обрабатывать большими фрагментами. Действительно, можно использовать наибольшие фрагменты, которые помещаются в машинное слово, так же, как и в случае с элементарным модульным хешированием. Как уже подробно обсуждалось ранее, в некоторых строго типизованных языках высокого уровня подобная операция может оказаться труднореализуемой или требовать специальных вывертов, но в C++ она может не требовать больших затрат или вовсе ничего не требовать, если использовать приведение к подходящим форматам представления данных. Во многих ситуациях эти факторы важно учитывать, поскольку вычисление хеш-функции может выполняться во внутреннем цикле — следовательно, ускорив хеш-функцию, можно ускорить все вычисление.

Несмотря на очевидные преимущества рассмотренных методов, их реализация требует внимания по двум причинам. Во-первых, необходимо быть внимательным во избежание ошибок при преобразовании типов и использовании арифметических функций для различных машинных представлений ключей.

Программа 14.2. Универсальная хеш-функция (для строковых ключей)

Эта программа выполняет те же вычисления, что и программа 14.1, однако для аппроксимации вероятности возникновения конфликтов для двух несовпадающих ключей до значения 1/M вместо фиксированных оснований системы счисления применяются псевдослучайные значения коэффициентов. Для минимизации нежелательных затрат времени при вычислении хеш-функции используется грубый генератор случайных чисел.

  int hashU(char *v, int M)
    { int h, a = 31415, b = 27183;
      for (h = 0; *v != 0; v++, a = a*b % (M-1))
        h = (a*h + *v) % M;
      return (h < 0) ? (h + M) : h;
    }

Такие операции часто являются источниками ошибок, особенно при переносе программы со старого компьютера на новый, с другим количеством разрядов в слове или прочими отличиями в точности выполнения операций. Во-вторых, весьма вероятно, что во многих приложениях вычисление хеш-функции будет выполняться во внутреннем цикле, и время ее выполнения может в значительной степени определять общее время выполнения. В подобных случаях важно убедиться, что функция сводится к эффективному машинному коду. Подобные операции — известные источники неэффективности; например, разница во времени выполнения простого модульного метода для целых чисел и версии, в которой вначале выполняется умножение ключа на 0,61616, может быть существенной. Наиболее быстрый метод для многих компьютеров — принять M равным степени 2 и воспользоваться хеш-функцией

  inline int hash(Key v, int M)
    { return v  (M-1); }

Эта функция использует только lg M — 1 младших разрядов ключей. Для устранения нежелательных эффектов плохого распределения ключей можно применять операцию побитового " И " , которая выполняется существенно быстрее и проще, чем другие операции.

Типичная ошибка в реализациях хеширования заключается в том, что хеш-функция всегда возвращает одно и то же значение — возможно, из-за неправильного выполнения требуемого преобразования типов. Такая ошибка называется ошибкой производительности, поскольку использующая такой метод хеширования программа вполне может выполняться корректно, но крайне медленно (т.к. ее эффективная работа возможна только при равномерном распределении хеш-значений). Однострочные реализации этих функций очень легко тестировать, поэтому настоятельно рекомендуется проверять, насколько успешно они работают для типов ключей, которые ожидаются в любой конкретной реализации таблицы символов.

Для проверки гипотезы, что хеш-функция создает случайные значения, можно использовать критерий $$$\chi^{2}$$$ (см. упражнение 14.5), но, возможно, это требование слишком жесткое. Вообще вполне достаточно, если метод хеширования выдает каждое значение одинаковое количество раз — такое поведение соответствует значению %2, равному 0, и совсем не является случайным. Однако следует с подозрением относиться и к очень большим значениям %2. На практике, вероятно, достаточно проверить, что значения распределены так, что ни одно из них не доминирует (см. упражнение 14.15). По этим же соображениям хорошо разработанная реализация таблицы символов, основанная на универсальном хешировании, могла бы периодически проверять, являются ли хеш-значения равномерно распределенными. А клиентскую программу можно информировать о том, что имело место либо маловероятное событие, либо ошибка в хеш-функции. Подобного рода проверка оказалась бы разумным дополнением к любому реальному рандомизированному алгоритму.

Упражнения

14.1. Используя абстракцию digit из для обработки машинного слова как последовательности байтов, реализуйте рандомизированный метод хеширования для ключей, представленных битами в машинных словах.

14.2. Проверьте, требуется ли время на преобразование 4-байтового ключа в 32-разрядное целое число в используемой вами программной среде.

о 14.3. Разработайте функцию хеширования для строковых ключей, основанную на идее одновременной загрузки 4 байтов с последующим выполнением арифметических операций сразу над 32 битами. Сравните время выполнения этой функции с временем выполнения программы 14.1 для 4-, 8-, 16- и 32-байтовых ключей.

14.4. Напишите программу для определения значений а и M при минимально возможном значении M, чтобы хеш-функция . Полученный результат является примером совершенной хеш-функции.

о 14.5. Напишите программу для вычисления критерия $$$\chi^{2}$$$ для хеш-значений N ключей при размере таблицы, равном M. Это число определяется равенством $$$$\chi^{2}=\dfrac{M}{N}\sum \limits_{0\leq i\leq M}(f_{i}-\dfrac{N}{M})^{2},$$$$ где f_i — количество ключей с хеш-значением i. Если хеш-значения являются случайными, значение этой функции для N > cM должно быть равно $$$M\pm\sqrt{M}$$$ с вероятностью 1 — 1/с.

14.6. Воспользуйтесь программой из упражнения 14.5 для вычисления хеш-функции 618033*x % 10000 для ключей, которые являются случайными положительными целыми числами, меньшими 10⁶.

14.7. Воспользуйтесь программой из упражнения 14.5 для вычисления хеш-функции из программы 14.1 для различных строковых ключей, полученных из какого-либо большого файла в вашей системе, например, словаря.

14.8. Пусть ключи являются t-разрядными двоичными целыми числами. Для модульной хеш-функции с простым основанием M докажите, что каждый бит ключа обладает тем свойством, что существуют два ключа с различными хеш-значениями, отличающиеся только этим битом.

14.9. Рассмотрите идею реализации модульного хеширования для целочисленных ключей с помощью выражения (a*x) % M, где а — произвольное фиксированное простое число. Приводит ли это изменение к достаточному перемешиванию разрядов, чтобы можно было использовать не простое значение M?

14.10. Докажите, что (((ax) mod M) + b) mod M = (ax + b) mod M, при условии, что a, b, x и M — неотрицательные целые числа.

14.11. Если в упражнении 14.7 использовать слова из текстового файла, например книги, то вряд ли удастся получить хороший критерий $$$\chi^{2}$$$. Объясните, почему это так.

14.12. Воспользуйтесь программой из упражнения 14.5 для вычисления хеш-функции 97*x % M для всех размеров таблицы в диапазоне от 100 до 200, используя в качестве ключей 10³ случайных положительных целых чисел, меньших 10⁶.

14.13. Воспользуйтесь программой из упражнения 14.5 для вычисления хеш-функции 97*x % M для всех размеров таблицы в диапазоне от 100 до 200, используя в качестве ключей целые числа в диапазоне от 10² до 10³.

14.14. Воспользуйтесь программой из упражнения 14.5 для вычисления хеш-функции 100*x % M для всех размеров таблицы в диапазоне от 100 до 200, используя в качестве ключей 10³ случайных положительных целых чисел, меньших 10⁶.

14.15. Выполните упражнения 14.12 и 14.14, но используйте более простой критерий отбрасывания хеш-функций, которые выдают любое значение более 3N/ M раз.

Цепочки переполнения

Рассмотренные в разделе 14.1 функции хеширования преобразуют ключи в адреса таблицы; второй компонент алгоритма хеширования — определение обработки случаев, когда два ключа преобразуются в один и тот же адрес. Первое, что приходит на ум — построить для каждого адреса таблицы связный список элементов, ключи которых отображаются на этот адрес. Этот подход непосредственно приводит к обобщению метода элементарного поиска в списке (см. ) в программе 14.3, в которой вместо единственного списка используются M списков.

Такой метод традиционно называется цепочками переполнения (separate chaining), поскольку конфликтующие элементы объединяются в отдельные связные списки-цепочки. Пример таких цепочек приведен на , но для цепочек переполнения более важна не экономия времени (поскольку списки невелики), а экономия памяти (поскольку списков много).

Для упрощения кода вставки в упорядоченный список можно было бы использовать ведущий узел, но применение M ведущих узлов для отдельных цепочек переполнения не всегда удобно.

(рис 14.6) Хеширование с цепочками переполнения

Здесь показан результат вставки ключей A S E R C H I N G X M P L в первоначально пустую хеш-таблицу с цепочками переполнения (неупорядоченные списки); используются хеш-значения, приведенные вверху. A попадает в список 0, затем S попадает в список 2, E — в список 0 (в его начало, чтобы время вставки было постоянным), R — в список 4 и т.д.

Программа 14.3. Хеширование с цепочками переполнения

Данная реализация таблицы символов основана на замене конструктора ST и функций search и insert в таблице символов с применением связных списков из программы 12.6 на приведенные здесь функции, а также на замене ссылки head на массив ссылок heads. Здесь используются те же рекурсивные функции поиска и удаления в списке, что и в программе 12.6, но при этом используются M списков с ведущими ссылками в heads, с использованием хеш-функции для выбора одного из списков. Конструктор устанавливает M так, что каждый список будет содержать около пяти элементов; поэтому для выполнения остальных операций требуется всего несколько проверок.

  private:
    link* heads;
    int N, M;
  public:
    ST(int maxN)
      { N = 0; M = maxN/5;
        heads = new link[M];
        for (int i = 0; i < M; i++) heads[i] = 0;
      }
    Item search(Key v)
      { return searchR(heads[hash(v, M)], v); }
    void insert(Item item)
      { int i = hash(item.key(), M);
        heads[i] = new node(item, heads[i]); N++;
      }

Более того, для элементов примитивного типа можно было бы даже исключить M ссылок на эти списки, поместив первые узлы списков в саму таблицу (см. упражнение 14.20). Для неудачных поисков можно считать, что хеш-функция достаточно равномерно перемешивает значения ключей, чтобы поиск в каждом из M списков был равновероятным. Тогда характеристики производительности, рассмотренные в , применимы к каждому списку.

Лемма 14.1. Цепочки переполнения уменьшают количество сравнений, выполняемых при последовательном поиске, в M раз (в среднем) и используют дополнительный объем памяти для M ссылок.

Средняя длина списков равна , можно ожидать, что успешные поиски будут доходить приблизительно до середины какого-либо списка. Неудачные поиски будут доходить до конца списка, если списки неупорядочены, и до половины списка, если они упорядочены. $$$\blacksquare$$$

Чаще всего для цепочек переполнения используются неупорядоченные списки, поскольку этот подход прост в реализации и эффективен: операция вставить выполняется за постоянное время, а операция найти — за время, пропорциональное N/M. Если ожидается очень большое количество неудачных поисков, их обнаружение можно ускорить в два раза, храня списки в упорядоченном виде, но за счет замедления операции вставить.

Лемма 14.1 тривиальна, поскольку средняя длина списков равна N/M независимо от распределения элементов по спискам. Например, предположим, что все элементы попадают в первый список. Тогда средняя длина списков равна (N + 0 + 0 + ... + 0)/M = N/M. Истинная причина практической пользы хеширования заключается в том, что очень высока вероятность наличия около N/M элементов в каждом списке.

Лемма 14.2. В хеш-таблице с цепочками переполнения, содержащей M списков и N ключей, вероятность того, что количество ключей в каждом списке отличается от N/M на небольшой постоянный коэффициент, очень близка к 1.

Для читателей, которые знакомы с основами вероятностного анализа, приведем краткое изложение этих классических рассуждений. Легко видеть, что вероятность того, что данный список будет содержать к элементов, равна $$ $$\left(\begin{array}{c} N\\ k \end{array}\right)\left(\dfrac{1}{M}\right)^{k}\left(1-\dfrac{1}{M}\right)^{N-k}$$ $$

Здесь выбираются k из N элементов: эти к элементов попадают в данный список с вероятностью 1/M, а остальные N — k элементов не попадают в данный список с вероятностью 1 — 1/M. Обозначив $$$\alpha = N/M$$$, это выражение можно переписать как $$ $$\left(\begin{array}{c} N\\ k \end{array}\right)\left(\dfrac{\alpha}{N}\right)^{k}\left(1-\dfrac{\alpha}{N}\right)^{N-k}$$ $$

что, согласно классической аппроксимации Пуассона, меньше чем $$$$\dfrac{\alpha^{k}e^{-\alpha}}{k!}$$$$.

Отсюда следует, что вероятность наличия в списке более чем $$$t\alpha$$$ элементов меньше, чем $$$$\left(\dfrac{\alpha e}{t}\right)^{t}e^{-\alpha}$$$$.

Для используемых на практике диапазонов параметров эта вероятность исключительно мала. Например, если средняя длина списков равна 20, вероятность того, что в какой-либо список попадут более 40 элементов, меньше чем $$$(40e/2)^{2}e^{-20} \approx 0,0000016$$$. $$$\blacksquare$$$

Приведенный анализ — пример классической задачи о размещении: N шаров случайным образом вбрасываются в одну из M урн, и анализируется распределение шаров по урнам. Классический математический анализ этих задач дает и много других интересных фактов, имеющих отношение к изучению алгоритмов хеширования. Например, в соответствии с аппроксимацией Пуассона количество пустых списков близко к $$$e^{-\alpha}$$$. Хотя более интересен факт, что среднее количество элементов, вставленных до первой коллизии, равно приблизительно $$$\sqrt{\pi M/2}\approx1,25\sqrt{M}$$$. Этот результат — решение классической задачи о дне рождения. Например, в соответствии с этими же рассуждениями, при M= 365 среднее количество людей, среди которых найдутся двое с одинаковыми датами рождения, приблизительно равно 24. В соответствии со вторым классическим результатом среднее количество элементов, вставленных прежде, чем в каждом списке окажется по меньшей мере по одному элементу, приблизительно равно MH_M Этот результат — решение классической задачи коллекционера карточек. Например, аналогичный анализ утверждает, что при M = 1280 нужно собрать около 9898 бейсбольных карточек (купонов), прежде чем удастся заполучить по одной карточке для каждого из 40 игроков каждой из 32 команд. Данные результаты весьма показательны для рассмотренных свойств хеширования. Практически они означают, что цепочки переполнения можно успешно использовать, если хеш-функция выдает значения, близкие к случайным (см. раздел ссылок).

Обычно в реализациях цепочек переполнения значение M выбирают достаточно малым, чтобы не тратить понапрасну большие непрерывные участки памяти с пустыми ссылками, но достаточно большим, чтобы последовательный поиск в списках был наиболее эффективным методом. Гибридные методы (вроде использования бинарных деревьев вместо связных списков), вряд ли стоят рассмотрения. Как правило, можно выбирать значение M равным приблизительно одной пятой или одной десятой от ожидаемого количества ключей в таблице, чтобы каждый из списков в среднем содержал порядка 5—10 ключей. Одно из достоинств цепочек переполнения состоит в том, что этот выбор не критичен: при наличии большего, чем ожидалось, количества ключей поиски будут требовать несколько больше времени, чем если бы заранее был выбран больший размер таблицы; при наличии в таблице меньшего количества ключей поиск будет сверхбыстрым при (скорее всего) небольшом дополнительном расходе памяти. Если памяти хватает, значение M можно выбрать достаточно большим, чтобы время поиска было постоянным; если же объем памяти критичен, все-таки можно повысить производительность в M раз, выбрав максимально возможное значение M.

Приведенные в предыдущем абзаце рассуждения относятся к времени поиска. На практике для цепочек переполнения обычно применяются неупорядоченные списки, по двум основным причинам. Во-первых, как уже упоминалось, исключительно быстро выполняется операция вставить: вычисляем хеш-функцию, выделяем память для узла и связываем его с началом соответствующего списка. Во многих приложениях шаг распределения памяти не требуется (поскольку элементами, вставляемыми в таблицу символов, могут быть существующие записи с доступными полями ссылок), и для выполнения операции вставить остается выполнить всего три—четыре машинные инструкции. Второе важное преимущество использования в программе 14.3 реализации с использованием неупорядоченных списков заключается в том, что все списки работают подобно стекам, поэтому можно легко удалить последние вставленные элементы, которые размещаются в начале списков (см. упражнение 14.21). Эта операция важна при реализации таблицы символов с вложенными областями видимости (например, в компиляторе).

Как и в нескольких предыдущих реализациях, клиенту неявно предоставляется выбор способа обработки повторяющихся ключей. Клиент вроде программы 12.11 может перед любой операцией вставить выполнить операцию найти для проверки наличия такого ключа и таким образом обеспечить, что таблица не будет содержать повторяющихся ключей. Другой клиент может сэкономить сопряженные с операцией найти затраты, оставляя дубликаты в таблице и тем самым ускорив выполнение операций вставить.

В общем случае хеширование не подходит для использования в приложениях, в которых требуются реализации операций АТД сортировать и выбрать. Однако хеширование часто используется в типичных ситуациях, когда необходимо использовать таблицу символов с потенциально большим количеством операций найти, вставить и удалить с последующим однократным выводом элементов в порядке их ключей. Одним из примеров такого приложения является таблица символов в компиляторе; другой пример — программа удаления повторяющихся ключей, наподобие программы 12.11. Для обработки этой ситуации в реализации цепочек переполнения в виде неупорядоченных списков нужно воспользоваться одним из методов сортировки, описанных в лекциях 6—10. В реализации с использованием упорядоченных списков сортировку можно выполнить слиянием всех списков (см. упражнение 14.23) за время, пропорциональное Nlg M.

Упражнения

14.16. Сколько времени может потребоваться в худшем случае для вставки N ключей в первоначально пустую таблицу с цепочками переполнения в виде (1) неупорядоченных списков и (2) упорядоченных списков?

14.17. Приведите содержимое хеш-таблицы, образованной вставками элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустую таблицу из M = 5 списков при использовании цепочек переполнения в виде неупорядоченных списков. Для преобразования k-ой буквы алфавита в индекс таблицы используйте хеш-функцию 11k mod M.

14.18. Выполните упражнение 14.17, но для случая упорядоченных списков. Зависит ли ответ от порядка вставки элементов?

14.19. Напишите программу, которая вставляет N случайных целых чисел в таблицу размером N/100 с цепочками переполнения, а затем определяет длину самого короткого и самого длинного списков, при N = 10³, 10⁴, 10⁵ и 10⁶.

14.20. Измените программу 14.3, чтобы исключить из нее ведущие ссылки с помощью представления таблицы символов в виде массива узлов типа node (каждый элемент таблицы является первым узлом в ее списке).

14.21. Измените программу 14.3, включив в нее для каждого элемента целочисленное поле, значение которого устанавливается равным количеству элементов в таблице на момент вставки элемента. Затем реализуйте функцию, удаляющую все элементы, для которого значение этого поля больше заданного целого числа N.

14.22. Измените реализацию функции search в программе 14.3, чтобы она выводила все элементы с ключами, равными заданному ключу, так же, как это сделано в функции show.

14.23. Разработайте реализацию таблицы символов с цепочками переполнения в виде упорядоченных списков, которая включает деструктор, конструктор копирования и перегруженную операцию присваивания и поддерживает операции создать, подсчитать, найти, вставить, удалить, объединить, выбрать и сортировать для АТД первого класса таблицы символов при поддержке клиентских дескрипторов (см. упражнения 12.6 и 12.7).

Линейное опробование

Если можно заранее оценить количество элементов, которые должны быть помещены в хеш-таблицу, и имеется достаточно большая непрерывная область памяти, в которой можно поместить все ключи и оставить еще свободные участки, то тогда в хеш-таблице, вероятно, вообще не стоит использовать какие-либо ссылки. Существует несколько методов хранения N элементов в таблице размером M > N, при которых разрешение коллизий основано на использовании пустых мест в таблице. Такие методы называются методами хеширования с открытой адресацией (open-addressing).

Простейший метод открытой адресации называется линейным опробованием (linear probing): при возникновении коллизии (когда хеширование дает адрес в таблице, который уже занят элементом с ключом, не совпадающим с ключом поиска) мы просто проверяем следующую позицию в таблице. Обычно такую проверку (определяющую, содержит ли данная позиция таблицы элемент с ключом, равным ключу поиска) называют пробой (probe). При линейном опробовании определяется один из трех возможных исходов пробы: если позиция таблицы содержит элемент, ключ которого совпадает с искомым, то поиск завершился успешно; в противном случае (если позиция таблицы содержит элемент, ключ которого не совпадает с искомым) мы просто проверяем позицию таблицы с большим индексом, продолжая этот процесс (с возвратом к началу таблицы при достижении ее конца) до тех пор, пока не будет найден искомый ключ или пустая позиция таблицы. Если элемент, содержащий искомый ключ, должен быть вставлен после неудачного поиска, он помещается в пустое место таблицы, где был завершен поиск. Программа 14.4 является реализацией АТД таблицы символов, использующей этот метод. Процесс построения хеш-таблицы с использованием линейного опробования для некоторого набора ключей показан на рис 14.7.

(рис 14.7) Хеширование методом линейного опробования

На этой диаграмме показан процесс вставки ключей A S E R C H I N G X M P в первоначально пустую хеш-таблицу с открытой адресацией, размер которой равен 13. Используются показанные вверху хеш-значения и разрешение коллизий методом линейного опробования. Вначале A попадает в позицию 7, затем S попадает в позицию 3, E — в позицию 9. Потом, после коллизии в позиции 9, R попадает в позицию 10 и т.д. При достижении правого конца таблицы опробование продолжается с левого конца: например, последний вставленный ключ P хешируется в позицию 8, но после коллизий в позициях 8—12 и 0—4 попадает в позицию 5. Неопробованные позиции таблицы затенены.

Как и в случае цепочек переполнения, производительность методов с открытой адресацией зависит от коэффициента $$$\alpha = N/M$$$, но при этом он интерпретируется иначе.

Программа 14.4. Линейное опробование

Данная реализация таблицы символов хранит элементы в таблице, размер которой вдвое превышает максимально ожидаемое количество элементов и которая первоначально содержит значения nullItem. Таблица содержит сами элементы, но если элементы велики, тип элемента можно изменить, чтобы таблица содержала ссылки на элементы.

Для вставки нового элемента выполняется хеширование в позицию таблицы и ее просмотр вправо (чтобы найти незанятую позицию), используя пустые элементы в незанятых позициях в качестве сигнальных, точно так же, как и при поиске с индексацией по ключам (программа 12.4). Для поиска элемента с данным ключом мы начинаем с хеш-позиции ключа в таблице и просматриваем ее на совпадение, завершая процесс при обнаружении незанятой позиции.

Конструктор устанавливает M таким образом, чтобы таблица была заполнена менее чем наполовину, поэтому, если хеш-функция выдает значения, похожие на случайные, для выполнения остальных операций потребуется всего несколько проб.

  private:
    Item *st;
    int N, M;
    Item nullItem;
  public:
    ST(int maxN)
      { N = 0; M = 2*maxN;
        st = new Item[M];
        for (int i = 0; i < M; i++) st[i] = nullItem;
      }
    int count() const
      { return N; }
    void insert(Item item)
      { int i = hash(item.key(), M);
        while (!st[i].null()) i = (i+1) % M;
        st[i] = item; N++;
      }
    Item search(Key v)
      { int i = hash(v, M);
        while (!st[i].null())
          if (v == st[i].key())
            return st[i];
          else
            i = (i+1) % M;
        return nullItem;
    }

В случае цепочек переполнения — среднее количество элементов в одном списке, обычно большее 1. В случае открытой адресации а — доля занятых позиций таблицы; она должна быть меньше 1. Иногда а называют коэффициентом загрузки хеш-таблицы.

В случае разреженной таблицы (значение $$$\alpha$$$ мало) очевидно, что для большинства операций поиска пустая позиция будет найдена после всего нескольких проб. В случае почти полной таблицы (значение близко $$$\alpha$$$ к 1) для выполнения поиска может потребоваться очень большое количество проб, а при полностью заполненной таблице поиск может даже привести к бесконечному циклу. Как правило, чтобы время поиска не было слишком большим, при использовании линейного опробования нужно не допускать заполнения таблицы. То есть вместо того, чтобы использовать дополнительную память для ссылок, она используется для создания дополнительного места в хеш-таблице, что позволяет сократить последовательности проб. При использовании линейного опробования размер таблицы больше, чем с цепочками переполнения, т.к. необходимо соблюдение условия M > N, но общий объем используемой памяти может быть меньше, поскольку не используются ссылки. Вопросы сравнения используемого объема памяти будут подробно рассмотрены в разделе 14.5; а пока проанализируем время выполнения линейного опробования как функцию от $$$\alpha$$$.

Средние затраты на выполнение линейного опробования зависят от того, как элементы при их вставке объединяются в непрерывные группы занятых ячеек таблицы, называемые кластерами (cluster). Рассмотрим следующие два крайних случая заполненной наполовину (M = 2N) таблицы линейного опробования. В лучшем случае позиции таблицы с четными индексами будут пустыми, а с нечетными — занятыми (или наоборот — прим. перев.). В худшем случае первая (вообще-то любая непрерывная — прим. перев.) половина позиций таблицы будет пустой, а вторая — заполненной. Средняя длина кластеров в обоих случаях равна N/(2N) = 1/2, но среднее количество проб при неудачном поиске равно 1 (нужна по меньшей мере одна проба) плюс $$$$(0 + 1 + 0 + 1 + ...) / (2N ) = 1/2$$$$

в лучшем случае и 1 плюс $$$$(N + (N - 1) + (N - 2) + ...) / (2N) \approx N/4$$$$

в худшем случае.

Обобщая эти рассуждения, приходим к выводу, что среднее количество проб при неудачном поиске пропорционально квадратам длин кластеров. Среднее значение рассчитывается путем вычисления затрат при неудачном поиске, начиная с каждой позиции таблицы, и деления суммы на M. Для неудачного поиска требуется не менее 1 пробы, поэтому будем считать количество проб, следующих за первой. Если кластер имеет дину t, то вклад этого кластера в общую сумму определяется выражением $$$$(t + (t - 1) + ... + 2 + 1) / М = t (t + 1) / (2М )$$$$

Сумма длин кластеров равна N, поэтому, суммируя эти затраты для всех ячеек в таблице, находим, что общие средние затраты при неудачном поиске равны 1 + N / (2M) плюс сумма квадратов длин кластеров, деленная на 2M. Имея заданную таблицу, можно быстро вычислить средние затраты на неудачный поиск в этой таблице (см. упражнение 14.28), но общую аналитическую формулу дать трудно, поскольку кластеры образуются в результате сложного динамического процесса (алгоритма линейного опробования).

Лемма 14.3. При разрешении коллизий с помощью линейного опробования среднее количество проб, нужных для поиска в хеш-таблице размером M, которая содержит $$$N = \alpha М$$$ ключей, приблизительно равно

$$$\dfrac{1}{2}\left(1+\dfrac{1}{1-\alpha }\right)$$$ и

$$$\dfrac{1}{2}\left(1+\dfrac{1}{(1-\alpha)^{2}}\right)$$$

соответственно для успешного и неудачного поиска.

Несмотря на сравнительно простую форму этих результатов, точный анализ линейного опробования представляет собой сложную задачу. Его вывод, полученный Кнутом (Knuth) в 1962 г., явился значительной вехой в анализе алгоритмов (см. раздел ссылок). $$$\blacksquare$$$

Точность этих выражений уменьшается с приближением значения $$$\alpha$$$ к 1, но в данном случае это не важно, поскольку в любом случае линейное опробование не следует использовать в почти заполненной таблице. Для меньших значений а равенства достаточно точны. Ниже приведена таблица, в которую сведены ожидаемые количества проб при успешном и неудачном поиске с использованием линейного опробования:

коэффициент загрузки ($$$\alpha$$$ )	`1/2`	`2/3`	`3/4`	`9/10`
успешный поиск	`1,5`	`2,0`	`3,0`	`5,5`
неудачный поиск	`2,5`	`5,0`	`8,5`	`55,5`

Для неудачного поиска всегда требуются большие затраты, чем для успешного, и можно ожидать, что в обоих случаях в заполненной менее чем наполовину таблице в среднем требуется лишь несколько проб.

(рис 14.8) Удаление в хеш-таблице с линейным опробованием

На этой диаграмме показан процесс удаления ключа X из таблицы, показанной на рис 14.7. Во второй строке показан результат простого удаления X из таблицы, что неприемлемо, поскольку в этом случае M и P оказываются отрезаны от своиххеш-позиций пустой позицией, оставшейся после X. Поэтому ключи M, S, H и P (справа от X в этом же кластере) повторно вставляются в указанном порядке с использованием хеш-значений, указанных сверху, и с разрешением коллизий с помощьюли-нейного опробования. M заполняет свободное место, оставленное ключом X, потом в таблицу без коллизий вставляются S и H, а затем в позицию 2 вставляется P.

Как и в случае цепочек переполнения, выбор, хранить ли в таблице элементы с повторяющимися ключами, предоставляется клиенту. Такие элементы не обязательно размещаются в таблице с линейным опробованием в соседних позициях — среди элементов с одинаковыми ключами могут размещаться и другие элементы с таким же хеш-значением.

По самой сути построения ключи в таблице, построенной с помощью линейного опробования, размещаются в случайном порядке. В результате операции АТД сортировать и выбрать требуют выполнения заново по одному из методов, описанных в лекциях 6-10. Поэтому линейное опробование не годится для приложений, в которых эти операции выполняются часто.

А как удалить ключ из таблицы, построенной с помощью линейного опробования? Просто убрать его нельзя, поскольку элементы, которые были вставлены позже, могли перескочить через этот элемент, и поэтому их поиск будет постоянно прерываться на пустой позиции, оставшейся после удаленного элемента. Одно из решений этой проблемы заключается в повторном хешировании всех элементов, для которых эта проблема могла бы возникнуть — между удаленным элементом и следующей незанятой позицией справа от него. Пример, иллюстрирующий этой процесс, приведен на рис 14.8, а программа 14.5 содержит реализацию этого подхода. В разреженной таблице в большинстве случаев такой процесс потребует лишь нескольких операций повторного хеширования. Другой способ реализации удаления — замена удаленного ключа сигнальным ключом, который будет служить заполнителем для поиска, но может быть повторно использован для вставок (см. упражнение 14.33).

Программа 14.5. Удаление из хеш-таблицы с линейным опробованием

Для удаления элемента с заданным ключом выполняется поиск этого элемента и замена его пустым элементом nullItem. Затем необходимо внести изменения на случай, если какой-либо элемент, расположенный справа от теперь незанятой позиции, хешируется в эту позицию или левее нее, т.к. свободная позиция может привести к прерыванию поиска такого элемента. Поэтому выполняется повторная вставка всех элементов, расположенных в одном кластере с удаленным элементом правее него. Поскольку таблица заполнена менее чем наполовину, в среднем количество повторно вставляемых элементов будет мало.

  void remove(Item x)
    { int i = hash(x.key(), M), j;
      while (!st[i].null())
        if (x.key() == st[i].key())
          break;
        else
          i = (i+1) % M;
      if (st[i].null()) return;
      st[i] = nullItem; N--;
      for (j = i+1; !st[j].null(); j = (j + 1) % M, N--)
        { Item v = st[j]; st[j] = nullItem; insert(v); }
    }

Упражнения

14.24. Какое время может потребоваться в худшем случае для вставки N ключей в первоначально пустую таблицу при использовании линейного опробования?

14.25. Приведите содержимое хеш-таблицы, образованной вставками элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустую таблицу размером M= 16, использующую линейное опробование. Для преобразования k-ой буквы алфавита в индекс таблицы используйте хеш-функцию 11k mod М.

14.26. Выполните упражнение 14.25 для М = 10.

14.27. Напишите программу, которая вставляет 10⁵ случайных неотрицательных целых чисел, меньших 10⁶, в таблицу размером 10⁵, использующую линейное опробование. Программа должна выводить гистограмму количества проб, использованных для каждых 10³ последовательных вставок.

14.28. Напишите программу, которая вставляет N/2случайных целых чисел в таблицу размером N, использующую линейное опробование, а затем на основании длин кластеров вычисляет средние затраты на неудачный поиск в результирующей таблице, для N= 10³, 10⁴, 10⁵ и 10⁶.

14.29. Напишите программу, которая вставляет N/2случайных целых чисел в таблицу размером N, использующую линейное опробование, а затем вычисляет средние затраты на успешный поиск в результирующей таблице, для N= 10³, 10⁴, 10⁵ и 10⁶. Не выполняйте поиск всех ключей после построения таблицы (отслеживайте затраты на ее построение).

14.30. Определите экспериментальным путем, изменяются ли средние затраты на успешный и неудачный поиск в случае выполнения длинной последовательности чередующихся случайных вставок и удалений с помощью программ 14.4 и 14.5 в хеш-таблице размером 2N, содержащей N ключей, для N = 10, 100 и 1000 и до N² пар вставок-удалений для каждого значения N.

Двойное хеширование

Основной принцип линейного опробования (а, вообще-то, и любого метода хеширования) —гарантирование того, что при поиске конкретного ключа мы просматриваем каждый ключ, который отображается в тот же адрес в таблице (в частности, сам ключ, если он есть в таблице). Однако при использовании схемы с открытой адресацией, как правило, просматриваются и другие ключи, особенно когда заполнение таблицы велико. В примере, приведенном на рис 14.7, при поиске ключа N просматриваются ключи C, E, R и I, ни один из которых не имеет такого же хеш-значения. Что еще хуже, вставка ключа с одним хеш-значением может существенно увеличить время поиска ключей с другими хеш-значениями: на рис 14.7 вставка ключа M приводит к увеличению времени поиска для позиций 7-12 и 0-1. Это явление называется кластеризацией (clustering), поскольку оно связано с процессом образования кластеров. Для почти заполненных таблиц оно может значительно замедлять линейное опробование.

К счастью, существует простой способ избежать возникновения проблемы кластеризации — двойное хеширование (double hashing). Основная стратегия остается той же, что и при выполнении линейного опробования; единственное различие состоит в том, что вместо просмотра каждой позиции таблицы, следующей за коллизией, мы используем вторую хеш-функцию для получения постоянного шага, используемого для последовательных проб. Реализация этого способа приведена в программе 14.6.

Программа 14.6. Двойное хеширование

Двойное хеширование аналогично линейному опробованию, за исключением того, что здесь используется вторая хеш-функция — для определения шага поиска, используемого после каждой коллизии. Шаг поиска должен быть ненулевым, а размер таблицы и шаг поиска должны быть взаимно простыми числами. Функция remove для линейного опробования (см. программу 14.5) не работает с двойным хешированием, поскольку любой ключ может присутствовать во многих различных последовательностях проб.

  void insert(Item item)
    { Key v = item.key();
      int i = hash(v, M), k = hashtwo(v, M);
      while (!st[i].null()) i = (i+k) % M;
      st[i] = item; N+ + ;
    }
  Item search(Key v)
    { int i = hash(v, M), k = hashtwo(v, M);
      while (!st[i].null())
      if (v == st[i].key())
        return st[i];
      else
        i = ( i+k) % M;
      return nullItem;
    }

Выбор второй хеш-функции требует определенной осторожности, поскольку в противном случае программа может вообще не работать. Во-первых, необходимо исключить случай, когда вторая хеш-функция дает нулевое значение, поскольку при первой же коллизии это приведет к бесконечному циклу. Во-вторых, важно, чтобы значение второй хеш-функции и размер таблицы были взаимно простыми числами, т.к. иначе некоторые из последовательностей проб могут оказаться очень короткими (например, в случае, когда размер таблицы вдвое больше значения второй хеш-функции). Один из способов претворения этих правил в жизнь — выбор в качестве M простого числа и выбор второй хеш-функции, возвращающей значения, меньшие M. На практике во многих ситуациях, если размер таблицы не слишком мал, будет достаточно простой второй хеш-функции вроде

  inline int hashtwo(Key v) { return (v % 97) + 1; }

Кроме того, любое снижение эффективности (из-за уменьшения дисперсии), вызываемое данным упрощением, на практике, скорее всего, будет не только не важно, но и вовсе незаметно. Если таблица большая и разреженная, сам размер таблицы не обязательно должен быть простым числом, поскольку для каждого поиска нужно будет лишь несколько проб (хотя было бы неплохо для предотвращения бесконечного цикла выполнять проверки на длинные последовательности проб и прерывать их — см. упражнение 14.38).

На рис 14.9 показан процесс построения небольшой таблицы методом двойного хеширования, а из рис 14.10 видно, что двойное хеширование приводит к образованию значительно меньшего количества кластеров (которые поэтому значительно короче), чем в результате линейного опробования.

(рис 14.9) Двойное хеширование

На этой диаграмме показан процесс вставки ключей , проверяемые позиции таблицы выделены белым цветом. Ключ A попадает в позицию 7, затем S попадает в позицию 3, E — в позицию 9, как и на рис 14.7. Но ключ R после коллизии в позиции 9 попадает в позицию 1; его второе хеш-значение, равное 5, используется в качестве шага последовательности проб после коллизии. Аналогично, ключ P окончательно попадает в позицию 6 после коллизий в позициях 8, 12, 3, 7, 11 и 2 при использовании в качестве шага его второго хеш-значения, равного 4.

(рис 14.10) Кластеризация

На этих диаграммах показано размещение записей при их вставке в хеш-таблицу с использованием линейного опробования (в центре) и двойного хеширования (внизу), при распределении ключей, показанном на верхней диаграмме. Каждая черточка показывает результат вставки 10 записей. По мере заполнения таблицы записи объединяются в кластеры, разделенные пустыми позициями таблицы. Длинные кластеры нежелательны, т.к. средние затраты на поиск одного ключа в кластере пропорциональны длине кластера. В случае линейного опробования чем длиннее кластеры, тем более вероятно их удлинение, поэтому по мере заполнения таблицы оказываются доминирующими несколько длинных кластеров. При использовании двойного хеширования этот эффект значительно менее выражен, и кластеры остаются сравнительно короткими.

Лемма 14.4. При разрешении коллизий с помощью двойного хеширования среднее количество проб, необходимых для выполнения поиска в хеш-таблице размером M, содержащей $$$N = \alpha M$$$ ключей, равно $$$\dfrac{1}{\alpha}\ln\left(\dfrac{1}{1-\alpha}\right)$$$ и $$$\dfrac{1}{1-\alpha}$$$

соответственно для успешного и неудачного поиска.

Эти формулы — результат глубокого математического анализа, выполненного Гиба (Guibas) и Шемереди (Szemeredi) (см. раздел ссылок). Доказательство основывается на том, что двойное хеширование почти эквивалентно более сложному алгоритму случайного хеширования, при котором используется зависящая от ключей последовательность позиций опробования, обеспечивающая равную вероятность попадания каждой пробы в каждую позицию таблицы. Этот алгоритм всего лишь аппроксимирует двойное хеширование, по многим причинам: например, очень трудно гарантировать, что при двойном хешировании каждая позиция таблицы проверяется хотя бы один раз, но при случайном хешировании одна и та же позиция таблицы может проверяться и более одного раза.

Однако для разреженных таблиц вероятность возникновения коллизий при использовании обоих методов одинакова. Интерес представляют оба метода: двойное хеширование легко реализовать, а случайное хеширование легко анализировать.

При случайном хешировании средние затраты на неудачный поиск определяются равенством $$$$1+\dfrac{N}{M}+\left(\dfrac{N}{M}\right)^{2}+\left(\dfrac{N}{M}\right)^{3}+\hdots =\dfrac{1}{1-(N/M)}=\dfrac{1}{1-\alpha }$$$$

Выражение слева — сумма вероятностей, что при неудачном поиске используются более к проб, при к = 0, 1, 2, ... (на основании элементарной теории вероятностей она равна средней вероятности). При поиске всегда используется одна проба, затем с вероятностью N/M требуется вторая проба, с вероятностью (N/M)² — третья проба и т.д. Эту же формулу можно использовать для вычисления следующего приближенного значения средней стоимости успешного поиска в таблице, содержащей N ключей:

$$$$\dfrac{1}{N}\left(1+\dfrac{1}{1-(1/M)}+\dfrac{1}{1-(2/M)}+\hdots +\dfrac{1}{1-((N-1)/M)}\right)$$$$

Вероятность успешного поиска одинакова для всех ключей в таблице; затраты на отыскание ключа равны затратам на его вставку, а затраты на вставку j-го ключа в таблицу равны затратам на неудачный поиск в таблице, содержащей j — 1 ключ, поэтому данная формула определяет среднее значение этих затрат.

Теперь эту сумму можно упростить и вычислить, умножив числители и знаменатели всех дробей на M: $$$$\dfrac{1}{N}\left(1+\dfrac{M}{M-1}+\dfrac{M}{M-2}+\hdots +\dfrac{M}{M-N+1}\right)$$$$ и, упрощая далее, получаем $$$$\dfrac{M}{N}(H_{M}+H_{M-N})\approx \dfrac{1}{\alpha}\ln\left(\dfrac{1}{1-\alpha}\right)$$$$ поскольку $$$H_{M}\approx \ln{M}$$$. $$$\blacksquare$$$

Точная природа взаимосвязи между производительностью двойного хеширования и идеальным случаем случайного хеширования, установленной Гиба и Шемереди — асимптотическое приближение, которое не обязательно должно быть справедливо для используемых на практике размеров таблиц. Кроме того, полученные результаты основываются на предположении, что хеш-функции возвращают случайные значения. Но все же асимптотические формулы из свойства 14.5 на практике позволяют достаточно точно предсказать производительность двойного хеширования, даже при использовании такой просто вычисляемой второй хеш-функции, как (v % 97)+1. Как и соответствующие формулы для линейного опробования, при приближении значения а к 1 эти формулы стремятся к бесконечности, но гораздо медленнее.

Различие между линейным опробованием и двойным хешированием хорошо видно на рис 14.11. В разреженных таблицах двойное хеширование и линейное опробование имеют схожую производительность, но при использовании двойного хеширования можно допустить значительно большую степень заполнения таблицы, чем при использовании линейного опробования, прежде чем производительность заметно снизится. В следующей таблице приведено ожидаемое количество проб для успешного и неудачного поиска при использовании двойного хеширования:

коэффициент загрузки ($$$\alpha$$$)	`1/2`	`2/3`	`3/4`	`9/10`
успешный поиск	`1,4`	`1,6`	`1,8`	`2,6`
неудачный поиск	`1,5`	`2,0`	`3,0`	`5,5`

Неудачный поиск всегда требует больших затрат, чем успешный, но и тому, и другому в среднем требуется лишь несколько проб, даже в таблице, заполненной на девять десятых.

Можно взглянуть на эти результаты и под другим углом: для получения такого же среднего времени поиска двойное хеширование позволяет использовать меньшие таблицы, чем нужно при использовании линейного опробования.

(рис 14.11) Затраты на выполнение поиска с открытой адресацией

На этих графиках показаны затраты на построение хеш-таблицы размером 1000 вставками ключей в первоначально пустую таблицу с помощью линейного опробования (вверху) и двойного хеширования (внизу). Каждый вертикальный столбец представляет затраты на вставку 20 ключей. Серые кривые — теоретически предсказанные затраты (см. леммы 14.4 и 14.5).

Лемма 14.5. Сохраняя коэффициент загрузки меньшим, чем $$$1 — 1/\sqrt{t}$$$ для линейного опробования и меньшим, чем $$$1 — 1/ t$$$ для двойного хеширования, можно обеспечить, что в среднем для выполнения всех поисков потребуется меньше t проб.

Установите значения выражений для неудачного поиска в свойствах 14.4 и 14.5 равными t и решите уравнения относительно $$$\alpha$$$. $$$\blacksquare$$$

Например, чтобы среднее количество проб при поиске было меньшим 10, при использовании линейного опробования необходимо сохранять таблицу пустой не менее чем на 32%, а при использовании двойного хеширования — лишь на 10%. Чтобы можно было выполнить неудачный поиск менее чем за 10 проб при обработке 10⁵ элементов, нужно свободное место лишь для 10⁴ дополнительных элементов. В то же время при использовании цепочек переполнения потребовалась бы дополнительная память для более чем 10⁵ ссылок, а при использовании деревьев бинарного поиска — еще вдвое больший объем памяти.

Метод реализации операции удалить, приведенный в программе 14.5 (повторное хеширование ключей, для которых путь поиска может содержать удаляемый элемент), для двойного хеширования не годится, т.к. удаленный элемент может присутствовать во многих различных последовательностях проб для ключей, разбросанных по всей таблице. Поэтому приходится применять другой метод, рассмотренный в конце : удаленный элемент заменяется сигнальным элементом, помечающим позицию таблицы как занятую, но не соответствующим ни одному из ключей (см. упражнение 14.33).

Подобно линейному опробованию, двойное хеширование не годится в качестве основы для реализации полнофункционального АТД таблицы символов, в котором необходимо поддерживать операции сортировать или выбрать.

Упражнения

14.31. Приведите содержимое хеш-таблицы, образованной вставками элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустую таблицу размером М = 16 при использовании двойного хеширования. Воспользуйтесь хеш-функцией 11k mod М для первой пробы и второй хеш-функцией (k mod 3) + 1 для шага поиска (если ключ является k-ой буквой алфавита).

14.32. Выполните упражнение 14.31 для М = 10.

14.33. Реализуйте удаление для двойного хеширования с использованием сигнального элемента.

14.34. Измените решение упражнения 14.27, чтобы в нем использовалось двойное хеширование.

14.35. Измените решение упражнения 14.28, чтобы в нем использовалось двойное хеширование.

14.36. Измените решение упражнения 14.29, чтобы в нем использовалось двойное хеширование.

14.37. Реализуйте алгоритм, который аппроксимирует случайное хеширование, используя ключ в качестве исходного значения для встроенного в программу генератора случайных чисел (как в программе 14.2).

14.38. Пусть таблица, размер которой равен 10⁶, заполнена наполовину, причем занятые позиции распределены случайным образом. Оцените вероятность того, что заняты все позиции, индексы которых кратны 100.

14.39. Допустим, что в коде реализации двойного хеширования присутствует ошибка, приводящая к тому, что одна или обе хеш-функции всегда возвращают одно и то же (ненулевое) значение. Опишите, что происходит в каждой из следующих ситуаций: (1) когда ошибочна первая функция, (2) когда ошибочна вторая функция, (3) когда ошибочны обе функции.

Динамические хеш-таблицы

С увеличением количества ключей в хеш-таблице скорость поиска снижается. При использовании цепочек переполнения время поиска увеличивается постепенно: если количество ключей в таблице удваивается, то и время поиска удваивается. Это же справедливо и для разреженных таблиц по отношению к таким методам с открытой адресацией, как линейное опробование и двойное хеширование, но по мере заполнения таблицы затраты существенно возрастают и, что гораздо хуже, наступает момент, когда невозможно вставить ни один ключ. Эта ситуация отличается от деревьев поиска, в которых рост происходит естественным образом. Например, в RB-дереве при каждом удвоении количества узлов затраты на поиск возрастают совсем ненамного (на одно сравнение).

Один из способов расширения хеш-таблиц — удвоение размера таблицы, когда она начинает заполняться. Удвоение размера таблицы — дорогостоящая операция, поскольку все элементы в таблице должны быть вставлены повторно, однако она выполняется нечасто. Программа 14.7 является реализацией увеличения таблицы с линейным опробованием путем ее удвоения. Пример таких удвоений показан на рис 14.12.

Программа 14.7. Динамическая вставка в хеш-таблицу (для линейного опробования)

Данная реализация операции insert для линейного опробования (см. программу 14.4) обрабатывает произвольное количество ключей, удваивая размер таблицы при каждом заполнении таблицы наполовину (этот же подход может быть использован для двойного хеширования или цепочек переполнения). Удвоение требует распределения памяти для новой таблицы и повторного хеширования в нее всех ключей, а затем освобождения памяти, занимаемой старой таблицей. Функция-член init используется для построения или повторного построения таблицы, заполненной пустыми элементами указанных размеров; она реализована так же, как конструктор ST в программе 14.4, поэтому ее код опущен.

  private:
    void expand()
      { Item *t = st;
        init(M+M);
        for (int i = 0; i < M/2; i++)
          if (!t[i].null()) insert(t[i]);
        delete t;
      }
  public:
    ST(int maxN)
      { init(4); }
    void insert(Item item)
      { int i = hash(item.key(), M);
        while (!st[i].null()) i = (i+1) % M;
        st[i] = item;
        if (N++ >= M/2) expand();
      }

(рис 14.12) Динамическое расширение хеш-таблицы

На этой диаграмме показан процесс вставки ключей A S E R C H I N G X M P L в динамическую хеш-таблицу, которая расширяется удвоением размера, с использованием хеш-значений, приведенных вверху, и разрешением коллизий с помощью линейного опробования. В четырех строках под ключами приводятся хеш-значения для размеров таблицы, равных 4, 8, 16 и 32. Начальный размер таблицы равен 4, затем, перед вставкой E, он удваивается до 8, перед вставкой C — до 16 и перед вставкой G — до 32. При каждом удвоении размера таблицы для всех ключей выполняются повторные хеширование и вставка. Все вставки выполняются в разреженные таблицы (заполненные менее чем на одну четверть для повторной вставки и от четверти до половины в остальных случаях), поэтому коллизий возникает мало.

Это же решение работает и для двойного хеширования, а основная идея применима и для цепочек переполнения (см. упражнение 14.46). Каждый раз, когда таблица заполняется более чем наполовину, она расширяется путем удвоения ее размера. После первого расширения степень заполнения таблицы всегда составляет от одной четвертой до одной второй, поэтому средние затраты на поиск составляют менее трех проб. И хотя операция повторного построения таблицы является дорогостоящей, она выполняется столь редко, что ее стоимость составляет лишь постоянную долю общих затрат на построение таблицы.

Эту концепцию можно выразить и по-другому, сказав, что средние затраты на одну вставку составляют меньше четырех проб. Это утверждение не равносильно утверждению, что для каждой вставки требуется менее четырех проб; и действительно, мы знаем, что вставки, которые приводят к удвоению размера таблицы, требуют большого количества проб. Это рассуждение — простой пример амортизационного анализа: нельзя гарантировать быстрое выполнение каждой операции этого алгоритма, но можно гарантировать, что будут низкими средние затраты на одну операцию.

Хотя общие затраты низки, профиль производительности вставок неравномерен: большинство операций выполняется исключительно быстро, но иногда для некоторых операций требуется почти столько же времени, сколько ранее было затрачено на построение всей таблицы. При увеличении размера таблицы от 1 тысячи до 1 миллиона ключей это замедление может случиться около 10 раз. Такое поведение приемлемо во многих приложениях, но может оказаться недопустимым, если желательны или обязательны абсолютные гарантии производительности. Например, если банк или авиакомпания могут допустить, что 10 из миллиона клиентов будут ожидать длительное время, то в таких приложениях, как онлайновая система обработки финансовых транзакций или система управления авиаполетами, долгое ожидание может повлечь катастрофические последствия.

При поддержке операции АТД удалить может иметь смысл сжимать таблицу, уменьшая вдвое ее размер при уменьшении количества ее ключей (см. упражнение 14.44). Но здесь требуется выполнение одного условия: границы уменьшения должны отличаться от границ увеличения, поскольку иначе небольшое количество операций вставить и удалить может привести даже для очень больших таблиц к серии операций увеличения и уменьшения размера вдвое.

Лемма 14.6. Последовательность t операций найти, вставить и удалить в таблицах символов может быть выполнена за время, пропорциональное t, при использовании объема памяти, не превышающего числа ключей в таблице, умноженного на некоторый постоянный коэффициент.

Линейное опробование с удвоением таблицы применяется тогда, когда операция вставить приводит к заполнению ключами половины таблицы; уменьшение размера таблицы вдвое используется тогда, когда операция удалить приводит к заполнению ключами таблицы на одну восьмую. В обоих случаях после изменения размера таблицы до значения N она содержит ), следовательно, по свойству 14.4, среднее количество проб для каждой операции меньше 3. $$$\blacksquare$$$

(рис 14.13) Динамическое хеширование

На данной диаграмме показано количество ключей в таблице (внизу) и размер таблицы (вверху) при вставках и удалениях ключей в динамической хеш-таблице, использующей следующий алгоритм:размер таблицы удваивается при заполнении ее наполовину и уменьшается в два раза, если заполненной остается лишь одна восьмая часть. Размер таблицы вначале равен 4 и всегда равен степени 2 (пунктирные линии на рисунке соответствуют степеням 2). Размер таблицы меняется тогда, когда кривая, отображающая количество ключей в таблице, пересекает пунктирную линию в первый раз после пересечения другой пунктирной линии. Доля заполнения таблицы всегда равна от одной четверти до одной восьмой.

Этот метод годится для использования в реализации таблицы символов, предназначенной для библиотеки программ общего назначения, когда последовательности операций непредсказуемы, поскольку позволяет приемлемым образом обрабатывать таблицы любых размеров. Основной его недостаток — затраты на повторное хеширование и распределение памяти при увеличении и уменьшении таблицы. В типичном случае, когда чаще выполняются операции поиска, гарантированная разреженность таблицы обеспечивает прекрасную производительность. В будет рассмотрен другой подход, позволяющий избежать повторного хеширования и подходящий для очень больших таблиц внешнего поиска.

Упражнения

14.40. Приведите содержимое хеш-таблицы, образованной вставками элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустую таблицу с начальным размером М = 4, которая удваивает размер при заполнении наполовину, с разрешением коллизий методом линейного опробования. Для преобразования k-ой буквы алфавита в индекс таблицы воспользуйтесь хеш-функцией 11k mod М.

14.41. Будет ли более экономичным увеличивать хеш-таблицу, утраивая (а не удваивая) ее размер при заполнении таблицы наполовину?

14.42. Будет ли более экономичным увеличивать хеш-таблицу, утраивая ее размер при заполнении таблицы на одну треть (вместо удвоения при заполнении наполовину)?

14.43. Будет ли более экономичным увеличивать хеш-таблицу, удваивая ее размер при заполнении таблицы на три четверти (а не наполовину)?

14.44. Добавьте в программу 14.7 функцию удалить, которая удаляет элемент, как в программе 14.4, но затем сжимает таблицу, вдвое уменьшая ее размер, если после удаления таблица остается пустой на семь восьмых.

14.45. Реализуйте версию программы 14.7 для цепочек переполнения, которая в 10 раз увеличивает размер таблицы каждый раз, когда средняя длина списка становится равной 10.

14.46. Измените программу 14.7 и реализацию из упражнения 14.44, чтобы в них использовалось двойное хеширование с " ленивым " удалением (см. упражнение 14.33). Нужно, чтобы программа подсчитывала количество фиктивных объектов и пустых позиций для принятия решения о необходимости расширения или сужения таблицы.

14.47. Разработайте реализацию таблицы символов с использованием линейного опробования в динамических таблицах, которая содержит деструктор, конструктор копирования и перегруженную операцию присваивания и поддерживает операции АТД первого класса таблицы символов создать, подсчитать, найти, вставить, удалить и объединить при поддержке клиентских дескрипторов (см. упражнения 12.6 и 12.7).

Перспективы

Как было показано при рассмотрении методов хеширования, выбор метода, который наиболее подходит для конкретного приложения, зависит от множества различных факторов. Все методы могут уменьшить время выполнения операций таблицы символов найти и вставить, сделав его постоянным, и все методы годятся для применения в широком множестве приложений. Можно грубо охарактеризовать три основных метода (линейное опробование, двойное хеширование и цепочки переполнения) следующим образом: линейное опробование является самым быстрым из этих трех методов (при наличии достаточного объема памяти, чтобы таблица была разреженной), двойное хеширование наиболее эффективно использует память (но тратит дополнительное время для вычисления второй хеш-функции), а цепочки переполнения проще всего реализовать и применять (при наличии хорошего механизма распределения памяти). Экспериментальные данные и комментарии, характеризующие производительность алгоритмов, приведены в таблица 14.1.

Экспериментальное сравнение реализаций хеш-таблиц
N	Создание					Неудачный поиск
N	R	H	P	h	P*	R	H	P	h	P*
1250	1	0	5	3	0	1	1	0	1	0
2500	3	1	3	4	2	1	1	0	0	0
5000	6	1	4	4	3	2	1	0	1	0
12500	14	6	5	5	5	6	1	2	2	1
25000	34	9	7	8	11	16	5	3	4	3
50000	74	18	11	12	22	36	15	8	8	8
100000	182	35	21	23	47	84	45	23	21	15
150000		54	40	36	138		99	89	52	21
160000		58	43	44	147		115	133	66	23
170000		68	55	45	136		121	226	85	25
180000		65	61	50	152		133	449	125	27
190000		79	10⁶	59	155		144	2194	261	30
200000	407	84			159	186	156			33

Обозначения:
R	RB-дерево бинарного поиска (программы 12.8 и 13.6)
H	Цепочки переполнения (программа 14.3 при размере таблицы 20000)
P	Линейное опробование (программа 14.4 при размере таблицы 200000)
D	Двойное хеширование (программа 14.6 при размере таблицы 200000)
P	Линейное опробование с расширением путем удвоения (программа 14.7)

Эти относительные значения времени построения таблиц символов из случайных последовательностей 32-битовых целых чисел и поиска в них подтверждают, что для легко хешируемых ключей хеширование работает значительно быстрее, чем поиск по дереву. Из всех методов хеширования двойное хеширование в разреженных таблицах работает медленнее, чем метод цепочек переполнения и линейное опробование (из-за затрат на вычисление второй хеш-функции), но значительно быстрее линейного опробования в почти заполненной таблице; кроме того, этот метод — единственный, который может обеспечить быстрый поиск с использованием лишь небольшого объема дополнительной памяти. Динамические хеш-таблицы, построенные с использованием линейного опробования и расширения удвоением, требуют больших затрат времени на создание, чем другие хеш-таблицы, из-за распределения памяти и повторного хеширования, но несомненно обеспечивают наиболее быстрый поиск. Этот метод удобен тогда, когда чаще всего выполняется поиск и заранее нельзя точно предвидеть количество ключей.

Выбор между линейным опробованием и двойным хешированием зависит прежде всего от затрат на вычисление хеш-функции и от коэффициента загрузки таблицы. Для разреженных таблиц (малых значений коэффициента $$$\alpha$$$) оба метода используют лишь несколько проб, но двойное хеширование может потребовать больше времени, если понадобится вычислять две хеш-функции для длинных ключей. По мере приближения а к 1 двойное хеширование начинает существенно превосходить по производительности линейное опробование (см. рис. 14.11 рис 14.11).

Сравнение линейного опробования и двойного хеширования с методом цепочек переполнения выполнить сложнее, поскольку необходимо точно учитывать использование памяти. Цепочки переполнения используют дополнительную память под ссылки; методы с открытой адресацией неявно используют дополнительную память внутри таблицы для завершения последовательностей проб. Следующий конкретный пример иллюстрирует эту ситуацию. Предположим, что имеется таблица М списков, построенная хешированием с цепочками переполнения, что средняя длина списков равна 4, и что каждый элемент и каждая ссылка занимают по одному машинному слову. Предположение, что элементы и ссылки занимают одинаковый объем памяти, оправданно во многих ситуациях, поскольку очень большие элементы обычно заменяются ссылками на них. В этом случае таблица занимает 9М слов памяти (4М для элементов и 5М для ссылок), и требует для выполнения поиска в среднем 2 пробы. Но при линейном опробовании для 4М элементов в таблице размером 9М требуется всего $$$(1 + 1/(1 — 4/9))/2 = 1,4$$$ пробы для успешного поиска, что на 30% меньше, чем с цепочками переполнения при том же объеме используемой памяти; а при линейном опробовании для 4М элементов в таблице размером 6М для успешного поиска требуется (в среднем) 2 пробы и, следовательно, используется на 33% меньше памяти, чем с цепочками переполнения при том же времени выполнения. Кроме того, можно использовать динамический метод, наподобие программы 14.7, для сохранения небольшого коэффициента загрузки таблицы с помощью увеличения ее размера.

Приведенные в предыдущем абзаце рассуждения показывают, что обычно выбор цепочек переполнения вместо открытой адресации по соображениям производительности не оправдан. Однако на практике цепочки переполнения с фиксированным значением М часто выбирают по ряду других причин: их легко реализовать (особенно операцию удалить); они требуют небольшого дополнительного объема памяти для элементов с уже выделенными полями ссылок, пригодными для использования таблицей символов и другими АТД, которые могут в них нуждаться. Хотя производительность этого метода снижается с увеличением количества элементов в таблице, это снижение вполне терпимо и происходит так, что вряд ли повредит приложению, поскольку производительность все равно в М раз выше, чем при последовательном поиске.

Существует много других методов хеширования, которые находят применение в особых ситуациях. Мы не можем останавливаться на этом подробно, но все же кратко рассмотрим три примера, иллюстрирующие сущность специальных методов хеширования.

Один класс методов перемещает элементы во время вставки при двойном хешировании, делая успешный поиск более эффективным. Так, Брент (Brent) разработал метод, при использовании которого даже в заполненной таблице среднее время успешного поиска ограничено константой (см. раздел ссылок). Такой метод может быть удобным в приложениях, в которых основной операцией является успешный поиск.

Другой метод, называемый упорядоченным хешированием (ordered hashing), использует упорядочение для уменьшения затрат на неудачный поиск при использовании линейного опробования, приближая их к затратам на успешный поиск. В стандартном линейном опробовании поиск прекращается при обнаружении пустой позиции таблицы или элемента, ключ которого равен искомому; в упорядоченном хешировании поиск прекращается при обнаружении ключа, который больше или равен искомому ключу (чтобы эта процедура работала, таблица должна быть построена специальным образом) (см. раздел ссылок). Это усовершенствование путем ввода упорядочения в таблицу аналогично эффекту от упорядочения цепочек переполнения. Данный метод предназначен для приложений, в которых преобладают неудачные поиски.

Таблица символов с быстрым неудачным поиском и несколько более медленным успешным поиском может использоваться для реализации словаря исключений (exception dictionary). Например, система текстовой обработки может содержать алгоритм для разбиения слов на слоги, который успешно работает для большинства слов, но не работает в отдельных случаях (вроде слова " безыскусный " ). Скорее всего, в словаре исключений будет найдено лишь небольшое количество слов очень большого документа, поэтому почти все поиски будут неудачными.

Это лишь некоторые примеры из множества алгоритмических усовершенствований, предложенных для хеширования. Многие из них представляют интерес и находят важные применения. Однако, как обычно, следует избегать неоправданного применения сложных методов, если только это не обусловлено серьезными причинами, а компромисс между производительностью и сложностью не проанализирован самым тщательным образом, поскольку цепочки переполнения, линейное опробование и двойное хеширование просты, эффективны и приемлемы для большинства приложений.

Задача реализации словаря исключений представляет собой пример приложения, в котором алгоритм можно слегка изменить для оптимизации производительности наиболее часто выполняемой операции — в данном случае неудачного поиска.

Например, предположим, что имеется словарь исключений, состоящий из 1000 элементов, и 1 миллион элементов, которые необходимо искать в словаре, поэтому почти все поиски должны быть неудачными. Такая ситуация может возникнуть, если все элементы были бы необычными словами или случайными 32-разрядными целыми числами. Один из подходов — хеширование всех слов, скажем, в 15-разрядные значения (размер таблицы будет около 2¹⁶). 1000 исключений занимают 1/64 часть таблицы, и большинство из 1 миллиона операций поиска сразу завершатся неудачей, обнаружив пустую позицию таблицы при первой же пробе. Но если таблица содержит 32-разрядные слова, задачу можно выполнить значительно эффективней, преобразовав ее в битовую таблицу исключений и используя 20-разрядные хеш-значения. При неудачном поиске (в большинстве случаев) поиск завершается проверкой одного бита; при удачном поиске требуется выполнение второй проверки в меньшей таблице. Исключения занимают 1/1000 часть таблицы; неудачный поиск — наиболее вероятная операция; и задача выполняется с помощью 1 миллиона битовых проверок с прямой индексацией. Это решение основывается на идее, что хеш-функция создает короткий сертификат, представляющий ключ — эта важная концепция полезна и в приложениях, отличных от реализаций таблиц символов.

Во многих приложениях хеширование предпочтительнее структур бинарных деревьев, рассмотренных в и для реализации таблиц символов, поскольку оно несколько проще и может обеспечить оптимальное (постоянное) время поиска, если ключи относятся к стандартному типу или достаточно просты, чтобы можно было уверенно разработать для них хорошую хеш-функцию. Преимущества структур бинарных деревьев по сравнению с хешированием заключается в том, что деревья основываются на более простом абстрактном интерфейсе (не требуется разработка хеш-функции);

деревья являются динамическими структурами (не требуется никакая предварительная информация о количестве вставок); деревья могут обеспечить гарантированную производительность в худшем случае (даже наилучшая хеш-функция может отобразить все элементы в одну и ту же позицию); и, наконец, деревья поддерживают более широкий диапазон операций (самое главное — операции сортировать и выбрать). Если эти факторы не важны, безусловно, следует выбирать хеширование, но с одной важной оговоркой: если ключи являются длинными строками, их можно встроить в структуры данных, которые обеспечивают методы поиска, работающие еще быстрее хеширования. Подобные структуры являются темой .

Упражнения

14.48. Для 1 миллиона целочисленных ключей вычислите размер хеш-таблицы, при которой каждый из трех методов хеширования (цепочки переполнения, линейное опробование и двойное хеширование) использует в среднем для неудачного поиска при вставке столько же сравнений с ключами, сколько и BST-деревья, если считать вычисление хеш-функции операцией сравнения.

14.49. Для 1 миллиона целочисленных ключей вычислите количество сравнений, выполняемых в среднем каждым из трех методов хеширования (цепочки переполнения, линейное опробование и двойное хеширование) при неудачном поиске, если они могут использовать 3 миллиона слов памяти (как было бы в случае BST-деревьев).

14.50. Реализуйте АТД таблицы символов с быстрым неудачным поиском, как описано в тексте, используя для второй проверки цепочки переполнения.

Страницы:

Хеш-функции

(рис 14.1) Мультипликативная хеш-функция для ключей с плавающей точкой

(рис 14.2) Модульная хеш-функция для целочисленных ключей

v % 97 (слева)

v % 100 (в центре) и

(int) (a * v) % 100 (справа),

(рис 14.3) Модульные хеш-функции для кодированных символов

(рис 14.4) Простые числа для хеш-таблиц

Программа 14.1. Хеш-функция для строковых ключей

  int hash(char *v, int M)
    { int h = 0, a = 127;
      for (; *v != 0; v++)
        h = (a*h + *v) % M;
      return h;
    }

(рис 14.5) Хеш-функции для символьных строк

M = 96 и a = 128 (вверху),

M = 97 и a = 128 (в центре) и

M = 96 и a = 127 (внизу)

Непосредственная реализация

  inline int hash(Key v, int M)
    { return (int) M*(v-s)/(t-s); }

  (int) (.616161 * (float) v) % M

или результат аналогичного целочисленного выражения, вроде

  (16161 * (unsigned) v) % M

Программа 14.2. Универсальная хеш-функция (для строковых ключей)

  int hashU(char *v, int M)
    { int h, a = 31415, b = 27183;
      for (h = 0; *v != 0; v++, a = a*b % (M-1))
        h = (a*h + *v) % M;
      return (h < 0) ? (h + M) : h;
    }

  inline int hash(Key v, int M)
    { return v  (M-1); }

Упражнения

14.10. Докажите, что (((ax) mod M) + b) mod M = (ax + b) mod M, при условии, что a, b, x и M — неотрицательные целые числа.

Цепочки переполнения

(рис 14.6) Хеширование с цепочками переполнения

Программа 14.3. Хеширование с цепочками переполнения

  private:
    link* heads;
    int N, M;
  public:
    ST(int maxN)
      { N = 0; M = maxN/5;
        heads = new link[M];
        for (int i = 0; i < M; i++) heads[i] = 0;
      }
    Item search(Key v)
      { return searchR(heads[hash(v, M)], v); }
    void insert(Item item)
      { int i = hash(item.key(), M);
        heads[i] = new node(item, heads[i]); N++;
      }

что, согласно классической аппроксимации Пуассона, меньше чем $$$$\dfrac{\alpha^{k}e^{-\alpha}}{k!}$$$$.

Упражнения

Линейное опробование

(рис 14.7) Хеширование методом линейного опробования

Программа 14.4. Линейное опробование

  private:
    Item *st;
    int N, M;
    Item nullItem;
  public:
    ST(int maxN)
      { N = 0; M = 2*maxN;
        st = new Item[M];
        for (int i = 0; i < M; i++) st[i] = nullItem;
      }
    int count() const
      { return N; }
    void insert(Item item)
      { int i = hash(item.key(), M);
        while (!st[i].null()) i = (i+1) % M;
        st[i] = item; N++;
      }
    Item search(Key v)
      { int i = hash(v, M);
        while (!st[i].null())
          if (v == st[i].key())
            return st[i];
          else
            i = (i+1) % M;
        return nullItem;
    }

в лучшем случае и 1 плюс $$$$(N + (N - 1) + (N - 2) + ...) / (2N) \approx N/4$$$$

в худшем случае.

$$$\dfrac{1}{2}\left(1+\dfrac{1}{1-\alpha }\right)$$$ и

$$$\dfrac{1}{2}\left(1+\dfrac{1}{(1-\alpha)^{2}}\right)$$$

соответственно для успешного и неудачного поиска.

коэффициент загрузки ($$$\alpha$$$ )	`1/2`	`2/3`	`3/4`	`9/10`
успешный поиск	`1,5`	`2,0`	`3,0`	`5,5`
неудачный поиск	`2,5`	`5,0`	`8,5`	`55,5`

(рис 14.8) Удаление в хеш-таблице с линейным опробованием

Программа 14.5. Удаление из хеш-таблицы с линейным опробованием

  void remove(Item x)
    { int i = hash(x.key(), M), j;
      while (!st[i].null())
        if (x.key() == st[i].key())
          break;
        else
          i = (i+1) % M;
      if (st[i].null()) return;
      st[i] = nullItem; N--;
      for (j = i+1; !st[j].null(); j = (j + 1) % M, N--)
        { Item v = st[j]; st[j] = nullItem; insert(v); }
    }

Упражнения

14.26. Выполните упражнение 14.25 для М = 10.

Двойное хеширование

Программа 14.6. Двойное хеширование

  void insert(Item item)
    { Key v = item.key();
      int i = hash(v, M), k = hashtwo(v, M);
      while (!st[i].null()) i = (i+k) % M;
      st[i] = item; N+ + ;
    }
  Item search(Key v)
    { int i = hash(v, M), k = hashtwo(v, M);
      while (!st[i].null())
      if (v == st[i].key())
        return st[i];
      else
        i = ( i+k) % M;
      return nullItem;
    }

  inline int hashtwo(Key v) { return (v % 97) + 1; }

(рис 14.9) Двойное хеширование

(рис 14.10) Кластеризация

соответственно для успешного и неудачного поиска.

$$$$\dfrac{1}{N}\left(1+\dfrac{1}{1-(1/M)}+\dfrac{1}{1-(2/M)}+\hdots +\dfrac{1}{1-((N-1)/M)}\right)$$$$

коэффициент загрузки ($$$\alpha$$$)	`1/2`	`2/3`	`3/4`	`9/10`
успешный поиск	`1,4`	`1,6`	`1,8`	`2,6`
неудачный поиск	`1,5`	`2,0`	`3,0`	`5,5`

(рис 14.11) Затраты на выполнение поиска с открытой адресацией

Упражнения

14.32. Выполните упражнение 14.31 для М = 10.

14.33. Реализуйте удаление для двойного хеширования с использованием сигнального элемента.

14.34. Измените решение упражнения 14.27, чтобы в нем использовалось двойное хеширование.

14.35. Измените решение упражнения 14.28, чтобы в нем использовалось двойное хеширование.

14.36. Измените решение упражнения 14.29, чтобы в нем использовалось двойное хеширование.

Динамические хеш-таблицы

Программа 14.7. Динамическая вставка в хеш-таблицу (для линейного опробования)

  private:
    void expand()
      { Item *t = st;
        init(M+M);
        for (int i = 0; i < M/2; i++)
          if (!t[i].null()) insert(t[i]);
        delete t;
      }
  public:
    ST(int maxN)
      { init(4); }
    void insert(Item item)
      { int i = hash(item.key(), M);
        while (!st[i].null()) i = (i+1) % M;
        st[i] = item;
        if (N++ >= M/2) expand();
      }

(рис 14.12) Динамическое расширение хеш-таблицы

(рис 14.13) Динамическое хеширование

Упражнения

Перспективы

Экспериментальное сравнение реализаций хеш-таблиц
N	Создание					Неудачный поиск
N	R	H	P	h	P*	R	H	P	h	P*
1250	1	0	5	3	0	1	1	0	1	0
2500	3	1	3	4	2	1	1	0	0	0
5000	6	1	4	4	3	2	1	0	1	0
12500	14	6	5	5	5	6	1	2	2	1
25000	34	9	7	8	11	16	5	3	4	3
50000	74	18	11	12	22	36	15	8	8	8
100000	182	35	21	23	47	84	45	23	21	15
150000		54	40	36	138		99	89	52	21
160000		58	43	44	147		115	133	66	23
170000		68	55	45	136		121	226	85	25
180000		65	61	50	152		133	449	125	27
190000		79	10⁶	59	155		144	2194	261	30
200000	407	84			159	186	156			33

Обозначения:
R	RB-дерево бинарного поиска (программы 12.8 и 13.6)
H	Цепочки переполнения (программа 14.3 при размере таблицы 20000)
P	Линейное опробование (программа 14.4 при размере таблицы 200000)
D	Двойное хеширование (программа 14.6 при размере таблицы 200000)
P	Линейное опробование с расширением путем удвоения (программа 14.7)

Упражнения

Занятие пройдено

Предыдущее занятие Занятие пройдено Следующее занятие

Вернуться к учебному плану

Хеш-функции

Цепочки переполнения

Линейное опробование

Двойное хеширование

Динамические хеш-таблицы

Перспективы

Хеш-функции

Цепочки переполнения

Линейное опробование

Двойное хеширование

Динамические хеш-таблицы

Перспективы

Купить дополнительную попытку

Вы действительно хотите купить ещё одну попытку для прохождения тестирования?

Успешно!

Напишите нам, если у вас есть вопросы

Уважаемые пользователи ИНТУИТ!

Уважаемые пользователи ИНТУИТ!

Добро пожаловать на обновлённый сайт НОУ «ИНТУИТ»!