Разрешение конфликтов посредством связывания
Разрешение конфликтов посредством связывания
Если мы готовы использовать дополнительные ячейки, кроме тех, которые требуются самой хеш-таблице, можно воспользоваться другой эффективной схемой разрешения конфликтов - схемой с закрытой адресацией. Этот метод называется связыванием (chaining). В его основе лежит очень простой принцип: хеширование ключа элемента для получения значения индекса. Но вместо того, чтобы хранить элемент в ячейке, которая определяется значением индекса, мы сохраняем его в односвязном списке, помещенном в эту ячейку.
Поиск элемента достаточно прост. Мы хешируем ключ с целью получения соответствующего индекса, а затем выполняем поиск требуемого элемента в связном списке, помещенном в этой ячейке.
При выборе места вставки элемента в связный список доступно несколько возможностей. Его можно сохранить в начале связного списка или в конце, или же можно обеспечить, чтобы связные списки были упорядочены, и сохранить элемент в соответствующей позиции сортировки. Все три варианта имеют свои преимущества. Первый вариант означает, что недавно вставленные элементы будут найдены первыми в случае их поиска (имеет место своего рода эффект стека). Следовательно, этот метод наиболее подходит для тех приложений, в которых, скорее всего, поиск новых элементов будет выполняться чаще, нежели поиск старых. Второй вариант означает противоположное: первыми будут найдены "наиболее старые" элементы (имеет место эффект типа очереди). Следовательно, он больше подходит для тех случаев, когда вероятность поиска более старых элементов больше вероятности поиска новых. Третий вариант предназначен для тех случаев, когда не существует предпочтений в отношении поиска более старых или новых элементов, но любой элемент нужно найти максимально быстро. В этом случае для облегчения поиска в связном списке можно прибегнуть к бинарному поиску. В действительности, если верить результатам выполненных мною тестов, третий вариант обеспечивает заметное преимущество только при наличии большого количества элементов в каждом связном списке. На практике лучше ограничить среднюю длину связных списков, при необходимости расширяя хеш-таблицу. Некоторые программисты экспериментировали, применяя деревья бинарного поиска к каждой ячейке (см. главу 8), а не к связным спискам. Однако полученные при этом преимущества оказались не особенно большими.
Первый упомянутый выше вариант вставки элемента в связный список имеет одно замечательное следствие. При успешном поиске элемента его можно переместить в начало связного списка, исходя из предположения, что если мы искали элемент, то, вероятно, довольно скоро будем искать его снова. Таким образом, элементы, поиск которых выполняется наиболее часто, будут перемещаться в верхнюю часть соответствующих связных списков.
Удаление элемента до смешного просто, если сравнить его с бегом по кругу, имевшим место при удалении элемента из хеш-таблицы с линейным зондированием. Достаточно найти элемент в соответствующем связном списке и разорвать связь с ним. Выполнение этих действий для односвязного списка описано в главе 3.
Преимущества и недостатки связывания
Преимущества связывания достаточно очевидны. Во-первых, в таблице, использующей связывание, никогда не возникнет ситуация нехватки места. Мы сколько угодно можем продолжать добавлять элементы в хеш-таблицу, и при этом будет происходить только увеличение связных списков. Реализация вставки и удаления крайне проста - действительно, большая часть работы была проделана в главе 3.
Несмотря на простоту, связывание имеет один важный недостаток. Он заключается в том, что никогда не возникает ситуация нехватки места! Проблема в том, что длина связных списков все больше и больше увеличивается. При этом время поиска в связных списках также увеличивается, а поскольку любая имеющая смысл операция, которую можно выполнять с хеш-таблицами, предполагает поиск элемента (вспомните пресловутый метод htlIndexOf класса хеш-таблиц с линейным зондированием), большая часть рабочего времени будет тратиться на поиск в связных списках.
Стоит отметить еще ряд обстоятельств. При использовании алгоритма разрешения конфликтов линейного зондирования мы сознательно старались минимизировать количество выполняемых зондирований, расширяя хеш-таблицу, когда ее коэффициент загрузки начинал превышать две третьих. Как следует из результатов анализа, в этой ситуации для успешного поиска должно в среднем требоваться два зондирования, а для безрезультатного - пять. Подумайте, что означает зондирование. По существу, это сравнение ключей. Весь смысл применения хеш-таблицы заключался в уменьшении количества сравнений ключей до одного или двух. В противном случае вполне можно было бы выполнить бинарный поиск в отсортированном массиве строк. Что ж, при использовании связывания для разрешения конфликтов каждый раз, когда мы спускаемся по связному списку, пытаясь найти конкретный ключ, для этого мы используем сравнение. Если прибегнуть к терминологии метода с открытой адресацией, то каждое сравнение можно сравнить с "зондированием". Так сколько же зондирований в среднем требуется для успешного поиска при использовании связывания? Для алгоритма связывания коэффициент загрузки по-прежнему вычисляется как число элементов, деленное на число ячеек (хотя на этот раз оно может иметь значение больше 1.0), и его можно представить средней длиной связных списков, присоединенных к ячейкам хеш-таблицы. Если коэффициент загрузки равен F, то среднее число зондирований для успешного поиска составит F/2. Для безрезультатного поиска среднее число зондирований равно F. (Эти результаты справедливы для несортированных связных списков. Если бы связные списки были отсортированы, значения были бы меньше - исходя из теории, оба значения нужно разделить на log(_2_)(F))
- Как это ни удивительно, хотя на первый взгляд связывание кажется более удачным решением, нежели открытая адресация, при более внимательном рассмотрении этот метод оказывается не столь уж хорошим.
Суть всех выше приведенных рассуждений состоит в том, что в идеале необходимо увеличивать также хеш-таблицу, которая использует метод связывания для разрешения конфликтов. Использование методологии перемещения наиболее недавно использованных элементов в верхнюю часть соответствующих связных списков также обеспечивает существенный выигрыш в производительности.