Упорядоченная линейная проверка

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

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

 

Public Function LocateItem(Value As Long, pos As Integer, _

probes As Integer) As Integer

Dim new_value As Long

 

probes = 1

pos = (Value Mod m_NumEntries)

Do

   new_value = m_HashTable(pos)

       

   ' Элемента в таблице нет.

   If new_value = UNUSED Or probes > NumEntries Then

      LocateItem = HASH_NOT_FOUND

      pos = -1

      Exit Function

   End If

       

   ' Элемент найден или его нет в таблице.

   If new_value >= Value Then Exit Do

       

   pos = (pos + 1) Mod NumEntries

   probes = probes + 1

Loop

 

If Value = new_value Then

   LocateItem = HASH_FOUND

Else

   LocateItem = HASH_NOT_FOUND

End If

End Function

 

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

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

 

========299-300

 

 

Public Function InsertItem(ByVal Value As Long, pos As Integer,_ probes As Integer) As Integer

Dim new_value As Long

Dim status As Integer

 

' Проверить, заполнена ли таблица.

If m_NumUnused < 1 Then

   ' Поиск элемента.

   status = LocateItem(Value, pos, probes)

   If status = HASH_FOUND Then

      InsertItem = HASH_FOUND

   Else

      InsertItem = HASH_TABLE_FULL

      pos = -1

   End If

   Exit Function

End If

 

probes = 1

pos = (Value Mod m_NumEntries)

Do

   new_value = m_HashTable(pos)

 

   ' Если значение найдено, поиск завершен.

   If new_value = Value Then

      InsertItem = HASH_FOUND

      Exit Function

   End If

 

   ' Если ячейка свободна, элемент должен находиться в ней.

   If new_value = UNUSED Then

      m_HashTable(pos) = Value

      HashForm.TableControl(pos).Caption = Format$(Value)

      InsertItem = HASH_INSERTED

      m_NumUnused = m_NumUnused - 1

      Exit Function

   End If

       

   ' Если значение в ячейке таблицы больше значения

   ' элемента, поменять их местами и продолжить.

   If new_value > Value Then

      m_HashTable(pos) = Value

      Value = new_value

   End If

       

   pos = (pos + 1) Mod NumEntries

   probes = probes + 1

Loop

End Function

 

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

В табл. 11.2 приведена средняя длина успешной и безуспешной тестовых последовательностей при использовании линейной и упорядоченной линейной проверок. Средняя длина успешной проверки для обоих методов почти одинакова, но в случае неуспеха упорядоченная линейная проверка выполняется намного быстрее. Разница в особенности заметна, если хеш‑таблица заполнена более, чем на 70 процентов.

 

=========301

 

@Таблица 11.2. Длина поиска при использовании линейной и упорядоченной линейной проверки

 

В обоих методах для вставки нового элемента требуется примерно одинаковое число шагов. Чтобы вставить элемент K в таблицу, каждый из методов начинает с позиции (K Mod NumEntries) и перемещается по таблице до тех пор, пока не найдет свободную ячейку. Во время упорядоченного хеширования может потребоваться поменять вставляемый элемент на другие в его тестовой последовательности. Если элементы представляют собой записи большого размера, то на это может потребоваться больше времени, особенно если записи находятся на диске или каком‑либо другом медленном запоминающем устройстве.

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

Квадратичная проверка

Один из способов уменьшить первичную кластеризацию состоит в том, чтобы использовать хеш‑функцию следующего вида:

 

Hash(K, P) = (K + P2) Mod N        где P = 0, 1, 2, ...

 

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

 

=======302

 

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

Следующий код демонстрирует поиск элемента с использованием квадратичной проверки (quadratic probing):

 

Public Function LocateItem(Value As Long, pos As Integer, probes As Integer) As Integer

Dim new_value As Long

 

probes = 1

pos = (Value Mod m_NumEntries)

Do

   new_value = m_HashTable(pos)

       

   ' Элемент найден.

   If new_value = Value Then

      LocateItem = HASH_FOUND

      Exit Function

   End If

       

   ' Элемента нет в таблице.

   If new_value = UNUSED Or probes > NumEntries Then

      LocateItem = HASH_NOT_FOUND

      pos = -1

      Exit Function

   End If

 

   pos = (Value + probes * probes) Mod NumEntries

   probes = probes + 1

Loop

End Function

 

Программа Quad демонстрирует открытую адресацию с использованием квадратичной проверки. Она аналогична программе Linear, но использует квадратичную, а не линейную проверку.

В табл. 11.3 приведена средняя длина тестовых последовательностей, полученных в программах Linear и Quad для хеш‑таблицы со 100 ячейками, значения элементов в которой находятся в диапазоне от 1 до 999. Квадратичная проверка обычно дает лучшие результаты.

 

@Рис. 11.8. Квадратичная проверка

 

======303

 

@Таблица 11.3. Длина поиска при использовании линейной и квадратичной проверки

 

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

Например, рассмотрим небольшую хеш‑таблицу, состоящую всего из шести ячеек. Тестовая последовательность для числа 3 будет следующей:

 

3

3 + 1² =  4 = 4 (Mod 6)

3 + 2² =  7 = 1 (Mod 6)

3 + 3² = 12 = 0 (Mod 6)

3 + 4² = 19 = 1 (Mod 6)

3 + 5² = 28 = 4 (Mod 6)

3 + 6² = 39 = 3 (Mod 6)

3 + 7² = 52 = 4 (Mod 6)

3 + 8² = 67 = 1 (Mod 6)

3 + 9² = 84 = 0 (Mod 6)

3 + 10² = 103 = 1 (Mod 6)

и так далее.

 

Эта тестовая последовательность обращается к позициям 1 и 4 дважды перед тем, как обратиться к позиции 3, и никогда не попадает в позиции 2 и 5. Чтобы пронаблюдать этот эффект, создайте в программе Quad хеш‑таблицу с шестью ячейками, а затем вставьте элементы 1, 3, 4, 6 и 9. Программа определит, что таблица заполнена целиком, хотя две ячейки и остались неиспользованными. Тестовая последовательность для элемента 9 не обращается к элементам 2 и 5, поэтому программа не может вставить в таблицу новый элемент.

 

=======304

 

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

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

На рис. 11.9 показана хеш‑таблица, которая может содержать 10 ячеек. В таблице находятся элементы 2, 12, 22 и 32, которые все изначально отображаются в позицию 2. Если попытаться вставить в таблицу элемент 42, то нужно будет выполнить длительную тестовую последовательность, которая обойдет все эти элементы, прежде чем найдет свободную ячейку.