Result := Inx;
Exit;
end;
end;
end;
{на этот раз ключ или пустая ячейка не были найдены, поэтому необходимо увеличить значение индекса (при необходимости выполнив циклический возврат) и осуществить выход в случае возврата к начальной ячейке}
inc(Inx);
if (Inx = FTable.Count) then
Inx := 0;
if (Inx = First Inx) then begin
aSlot :=nil;
{это сигнализирует о том, что таблица заполнена}
Result := -1;
Exit;
end;
end;
{бесконечный цикл}
end;
После выполнения простой инициализации метод htlIndexOf вычисляет хеш-значение (т.е. значение индекса) для переданного ему ключа. Метод сохраняет это значение, чтобы можно было определить ситуацию, когда необходимо выполнить полный циклический возврат в хеш-таблице.
Метод определяет указатель на начальную ячейку. Мы просматриваем ячейку и выполняем различные операции, зависящие от состояния ячейки. Первый случай - когда ячейка пуста. Достижение этой точки означает, что ключ не был найден, поэтому метод возвращает указатель именно на эту ячейку. Естественно, в этом случае возвращаемое значение функции равно -1, что означает "ключ не найден".
Второй случай - когда ячейка используется. Для выяснения того, совпадают ли ключи, мы сравниваем ключ, хранящийся в ячейке, с ключом, переданным методу (обратите внимание, что мы выполняем поиск точного совпадения, т.е. сравнение с учетом регистра; если хотите выполнить сравнение без учета регистра, нужно использовать ключи, преобразованные в прописные буквы). Совпадение ключей свидетельствует об обнаружении искомого элемента. Поэтому программа возвращает указатель ячейки и устанавливает результат функции равным индексу ячейки.
Если в результате выполнения описанных операций сравнения выход из метода не был осуществлен, необходимо проверить следующую ячейку. Поэтому значение индекса Inx увеличивается, гарантируя циклический возврат и повторное выполнение цикла.
Обратите внимание, что проверка того, была ли посещена каждая отдельная ячейка, является несколько излишней. Хеш-таблица является динамической, и значение коэффициента загрузки будет поддерживаться между одной шестой и одной третей. То есть, в таблице всегда должны существовать ячейки, которые не используются. Однако, выполнение проверки - хорошая практика программирования, которая учитывает возможность изменения хеш-таблицы в будущем и того, что какой-либо код может привести к возникновению подобной ситуации.
Полный вариант кода класса TtdHashTableLinear можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHshLnP.pas.
Хотя описанный класс хеш-таблиц был разработан для решения основной проблемы, возникающей при использовании схемы с открытой адресацией линейного зондирования (тенденции к кластеризации занятых ячеек), мы кратко рассмотрим несколько других схем с открытой адресацией.
Первая из таких схем - квадратичное зондирование (quadratic probing). При использовании этого алгоритма контроль и предотвращение создания кластеров осуществляется путем проверки не следующей по порядку ячейки, а ячеек, которые расположены все дальше от исходной. Если первое зондирование оказывается безрезультатным, мы проверяем следующую ячейку. В случае неудачи этой попытки мы проверяем ячейку, которая расположена через четыре ячейки. Если и эта попытка неудачна, мы проверяем ячейку, расположенную через девять ячеек - и т.д., причем последующие зондирования выполняются для ячеек, расположенных через 16, 25, 36 и так далее ячеек. Этот алгоритм позволяет предотвратить образование кластеров, которые могут появляться в результате применения линейного зондирования, однако он может приводить и к ряду нежелательных проблем. Во-первых, если для многих ключей хеширование генерирует один и тот же индекс, все их последовательности зондирования должны будут выполняться вдоль одного и того же пути. В результате они образуют кластер, но такой, который кажется распределенным по хеш-таблице. Однако вторая проблема значительно серьезнее: квадратичное зондирование не гарантирует посещение всех ячеек. Максимум в чем можно быть уверенным, если размер таблицы равен простому числу, это в том, что квадратичное зондирование обеспечит посещение, по меньшей мере, половины ячеек хеш-таблицы. Таким образом, образом, можно говорить о выполнении задачи-минимум, но не задачи-максимум.
В этом легко убедиться. Начнем квадратичное зондирование с 0-й ячейки хеш-таблицы, содержащей 11 ячеек, и посмотрим, какие ячейки будут посещены при этом. Последовательность посещений выглядит следующим образом: 0, 1, 5, 3, 8, после чего зондирование снова начинается с ячейки 0. Мы никогда не посещаем ячейки 2, 4, 7, 9. По-моему, одной этой проблемы достаточно, чтобы в любом случае избегать применения квадратичного зондирования, хотя ее можно было бы избегнуть, не позволяя хеш-таблице заполняться более чем на половину.
Следующая возможность - применение псевдослучайного зондирования (pseudorandom probing). Этот алгоритм требует использования генератора случайных чисел, который можно сбрасывать в определенный момент. Применительно к рассматриваемому алгоритму, из числа рассмотренных в 6 главе генераторов наиболее подошел бы минимальный стандартный генератор случайных чисел, поскольку его состояние однозначно определяется одним характеристическим значением - начальным числом. Алгоритм определяет следующую последовательность действий. Выполните хеширование ключа для получения хеш-значения, но не выполняйте деление по модулю на размер таблицы. Установите начальное значение генератора равным этому хеш-значению. Сгенерируйте первое случайное число с плавающей точкой (в диапазоне от 0 до 1) и умножьте его на размер таблицы для получения целочисленного значения в диапазоне от 0 до размера таблицы минус 1. Эта точка будет точкой первого зондирования. Если ячейка занята, сгенерируйте следующее случайное число, умножьте его на размер таблицы и снова выполните зондирование. Продолжайте выполнять упомянутые действия до тех пор, пока не найдете свободную ячейку. Поскольку при одном и том же заданном начальном значении генератор случайных чисел будет генерировать одни и те же случайные числа в одной и той же последовательности, для одного и того же хеш-значения всегда будет создаваться одна и та же последовательность зондирования.
Все это звучит достаточно обнадеживающе. Ценой ряда сложных и продолжительных вычислений, необходимых для получения случайного числа, этот алгоритм предотвратит образование кластеров, возникающих в результате линейного зондирования. Однако при этом возникает одна небольшая проблема: нет никакой гарантии, что рандомизированная последовательность обеспечит посещение каждой ячейки таблицы.
Нельзя не согласиться, что вероятность постоянного пропуска пустой ячейки достаточно низка, но это возможно, если таблица заполнена в значительной степени. Еще хуже то, что последовательность зондирований может стать очень большой до попадания в пустую ячейку. Следовательно, имеет смысл обеспечить невозможность значительного заполнения таблицы и изменение ее размера, если это происходит. С этого момента можно также продолжить использовать линейное зондирование с применением автоматически расширяемой хеш-таблицы. Это проще и быстрее.
В заключение рассмотрим двойное хеширование (double hashing). На практике эта схема оказывается наиболее удачной из всех альтернативных схем с открытой адресацией. Итак, выполним хеширование ключа элемента в значение индекса. Назовем его h(_1_). Выполним зондирование этой ячейки. Если она занята, выполним хеширование ключа путем применения совершенно иного и независимого алгоритма хеширования для получения другого значения индекса. Назовем его h(_2_). Выполним зондирование ячейки h(_1_) + h(_2_). Если она занята, выполним зондирование ячейки h(_1_) + 2h(_2_), затем h(_1_) + 3h(_2_) и так далее (понятно, что все вычисления выполняются с делением по модулю на размер таблицы). Обоснование этого алгоритма следующее: если первая функция хеширования для двух ключей генерирует один и тот же индекс, очень маловероятно, что вторая функция хеширования сгенерирует для них то же самое значение. Таким образом, два ключа, которые первоначально хешируются в одну и ту же ячейку, затем не будут соответствовать одной и той же последовательности зондирования. В результате мы можем ликвидировать "неизбежную" кластеризацию, сопряженную с линейным зондированием. Если размер таблицы равен простому числу, последовательность зондирования обеспечит посещение всех ячеек, прежде чем начнется сначала, что позволит избежать проблем, связных с квадратичным и псевдослучайным зондированием. Единственная реальная проблема, возникающая при использовании двойного хеширования, - если не принимать во внимание необходимость вычисления дополнительного хеш-значения - состоит в том, что вторая функция хеширования по понятным причинам никогда не должна возвращать значение, равное 0. На практике эту проблему легко решить, выполняя деление по модулю на размер таблицы минус 1 (в результате мы получим значение в диапазоне от 0 до TableSize-2), а затем добавляя к результату единицу.
Например, при использовании строковых ключей можно было бы вызвать функцию хеширования Вайнбергера TDPJWHash для вычисления основных хеш-значений, а затем вызвать простую функцию хеширования TDSimpleHash для вычисления хеш-значений, которые будут использоваться для пропуска ячеек. Я предлагаю читателям самостоятельно выполнить это простое упражнение по реализации такой хеш-таблицы двойного хеширования.
Если мы готовы использовать дополнительные ячейки, кроме тех, которые требуются самой хеш-таблице, можно воспользоваться другой эффективной схемой разрешения конфликтов - схемой с закрытой адресацией. Этот метод называется связыванием (chaining). В его основе лежит очень простой принцип: хеширование ключа элемента для получения значения индекса. Но вместо того, чтобы хранить элемент в ячейке, которая определяется значением индекса, мы сохраняем его в односвязном списке, помещенном в эту ячейку.
Поиск элемента достаточно прост. Мы хешируем ключ с целью получения соответствующего индекса, а затем выполняем поиск требуемого элемента в связном списке, помещенном в этой ячейке.
При выборе места вставки элемента в связный список доступно несколько возможностей. Его можно сохранить в начале связного списка или в конце, или же можно обеспечить, чтобы связные списки были упорядочены, и сохранить элемент в соответствующей позиции сортировки. Все три варианта имеют свои преимущества. Первый вариант означает, что недавно вставленные элементы будут найдены первыми в случае их поиска (имеет место своего рода эффект стека). Следовательно, этот метод наиболее подходит для тех приложений, в которых, скорее всего, поиск новых элементов будет выполняться чаще, нежели поиск старых. Второй вариант означает противоположное: первыми будут найдены "наиболее старые" элементы (имеет место эффект типа очереди). Следовательно, он больше подходит для тех случаев, когда вероятность поиска более старых элементов больше вероятности поиска новых. Третий вариант предназначен для тех случаев, когда не существует предпочтений в отношении поиска более старых или новых элементов, но любой элемент нужно найти максимально быстро. В этом случае для облегчения поиска в связном списке можно прибегнуть к бинарному поиску. В действительности, если верить результатам выполненных мною тестов, третий вариант обеспечивает заметное преимущество только при наличии большого количества элементов в каждом связном списке. На практике лучше ограничить среднюю длину связных списков, при необходимости расширяя хеш-таблицу. Некоторые программисты экспериментировали, применяя деревья бинарного поиска к каждой ячейке (см. главу 8), а не к связным спискам. Однако полученные при этом преимущества оказались не особенно большими.
Первый упомянутый выше вариант вставки элемента в связный список имеет одно замечательное следствие. При успешном поиске элемента его можно переместить в начало связного списка, исходя из предположения, что если мы искали элемент, то, вероятно, довольно скоро будем искать его снова. Таким образом, элементы, поиск которых выполняется наиболее часто, будут перемещаться в верхнюю часть соответствующих связных списков.
Удаление элемента до смешного просто, если сравнить его с бегом по кругу, имевшим место при удалении элемента из хеш-таблицы с линейным зондированием. Достаточно найти элемент в соответствующем связном списке и разорвать связь с ним. Выполнение этих действий для односвязного списка описано в главе 3.
Преимущества связывания достаточно очевидны. Во-первых, в таблице, использующей связывание, никогда не возникнет ситуация нехватки места. Мы сколько угодно можем продолжать добавлять элементы в хеш-таблицу, и при этом будет происходить только увеличение связных списков. Реализация вставки и удаления крайне проста - действительно, большая часть работы была проделана в главе 3.
Несмотря на простоту, связывание имеет один важный недостаток. Он заключается в том, что никогда не возникает ситуация нехватки места! Проблема в том, что длина связных списков все больше и больше увеличивается. При этом время поиска в связных списках также увеличивается, а поскольку любая имеющая смысл операция, которую можно выполнять с хеш-таблицами, предполагает поиск элемента (вспомните пресловутый метод htlIndexOf класса хеш-таблиц с линейным зондированием), большая часть рабочего времени будет тратиться на поиск в связных списках.
Стоит отметить еще ряд обстоятельств. При использовании алгоритма разрешения конфликтов линейного зондирования мы сознательно старались минимизировать количество выполняемых зондирований, расширяя хеш-таблицу, когда ее коэффициент загрузки начинал превышать две третьих. Как следует из результатов анализа, в этой ситуации для успешного поиска должно в среднем требоваться два зондирования, а для безрезультатного - пять. Подумайте, что означает зондирование. По существу, это сравнение ключей. Весь смысл применения хеш-таблицы заключался в уменьшении количества сравнений ключей до одного или двух. В противном случае вполне можно было бы выполнить бинарный поиск в отсортированном массиве строк. Что ж, при использовании связывания для разрешения конфликтов каждый раз, когда мы спускаемся по связному списку, пытаясь найти конкретный ключ, для этого мы используем сравнение. Если прибегнуть к терминологии метода с открытой адресацией, то каждое сравнение можно сравнить с "зондированием". Так сколько же зондирований в среднем требуется для успешного поиска при использовании связывания? Для алгоритма связывания коэффициент загрузки по-прежнему вычисляется как число элементов, деленное на число ячеек (хотя на этот раз оно может иметь значение больше 1.0), и его можно представить средней длиной связных списков, присоединенных к ячейкам хеш-таблицы. Если коэффициент загрузки равен F, то среднее число зондирований для успешного поиска составит F/2. Для безрезультатного поиска среднее число зондирований равно F. (Эти результаты справедливы для несортированных связных списков. Если бы связные списки были отсортированы, значения были бы меньше - исходя из теории, оба значения нужно разделить на log(_2_)(F))
- Как это ни удивительно, хотя на первый взгляд связывание кажется более удачным решением, нежели открытая адресация, при более внимательном рассмотрении этот метод оказывается не столь уж хорошим.
Суть всех выше приведенных рассуждений состоит в том, что в идеале необходимо увеличивать также хеш-таблицу, которая использует метод связывания для разрешения конфликтов. Использование методологии перемещения наиболее недавно использованных элементов в верхнюю часть соответствующих связных списков также обеспечивает существенный выигрыш в производительности.
Теперь пора рассмотреть какой-нибудь код. Общедоступный интерфейс к классу TtdHashTableChained в общих чертах не отличается от такового для класса TtdHashTableLinear. Различия между двумя этими классами проявляются в разделах private и protected.
Листинг 7.11. Класс TtdHashTableChained
type
TtdHashChainUsage = ( {Применение цепочек хеш-таблицы-}
hcuFirst, {..вставка в начало}
hcuLast);
{..вставка в конец}