ці. p align="justify"> Послідовність дій при знаходженні або додаванні елемента в хеш-таблицю називається послідовністю перевірки (probe sequence).
Для реалізації хешування необхідні три речі:
В· структура даних, звана хеш-таблицею, для зберігання даних;
В· хеш-функція для відображення ключових значень на клітинки таблиці;
В· алгоритм вирішення конфліктних ситуацій, який визначає порядок дій в ситуації, якщо ключі відображаються на одну й ту ж позицію.
ПРАКТИЧНА ЧАСТИНА
Зв'язування
Один з методів вирішення конфліктів полягає в тому, щоб зберігати записи, які відображаються на одну позицію таблиці, в пов'язаних списках. Для вставки нового запису за допомогою хеш-функції вибирається зв'язаний список, в якому буде знаходитися цей запис. Потім запис додається до цього списку. p align="justify"> На рис. 1 показаний приклад зв'язування хеш-таблиці, яка містить 10 осередків. Хеш-функція відображає ключ К на позицію масиву До mod 10. Кожна позиція масиву містить покажчик на перший елемент пов'язаного списку. Щоб вставити елемент в таблицю, ви додаєте його у відповідний список. br/>В
Рисунок 1 - Зв'язування
Щоб створити хеш-таблицю в Delphi, потрібно оголосити масив комірок, що починається з нуля. Цей масив і буде списком тегів. Якщо хеш-таблиця буде містити NumChains списків, оголосіть масив з межами від 0 до Num-Chains - 1. Встановіть кожне значення NextCell осередків у nil. p align="justify"> Щоб знайти в хеш-таблиці елемент з ключем К, необхідно обчислити До mod NumChains. Таким чином ви отримаєте індекс мітки зв'язаного списку, в якому може міститися елемент. Потім потрібно переглядати список, поки не знайдеться шуканий елемент або не буде досягнутий кінець списку. p align="justify">: PChainCell;
begin
// Визначення ланцюга, що містить значення.
cell: = ListTci ^ [value mod NumChains]. NextCell;
while (cellonil) do
if (се! 1Л.value = value) then break;: = cellA.NextCell;; (cellonil ) then
begin
// Які-небудь дії з осередком.
end;
Щоб вставити в таблицю елемент з ключем К, спочатку обчислимо До mod Num-Chains, визначивши таким чином, який список повинен містити да...
