На главную   ::   Содержание



Алгоритм поиска в хеш-таблице с цепочками

Пусть есть множество ключей $ \mathcal K$.

Определение 1.   Хэш-функцией называется отображение $ h: \mathcal K \rightarrow
[1,N]\subset \mathbb{Z}$.

То есть каждому ключу $ k\in \mathcal K$ ставится в соответствие число $ 1\leqslant h(k) \leqslant N$. Не обязательно взаимно однозначно. Поэтому вводится определение коллизии.

Определение 2.   Коллизией называют случай равенства $ h(k_1)=h(k_2)$ при $ k_1, k_2\in \mathcal
K,   k_1\neq k_2$.

Для чего это нужно? Если элементы множества $ \mathcal K$ -- некоторые большие структуры, то для их сравнения (для двух элементов мы хотим понять, равны они или нет) можно сравнить их хэш-функции, которые подсчитаны заранее, и если равны хэш-функции, то, может быть, равны и сами элементы. Однако, если хэш-функции не равны, то сами элементы уже можно не сравнивать. Например, пусть $ \mathcal K$ -- множество всех строк из строчных латинских букв длиной $ 100$ символов. Всего таких строк $ \vert\mathcal K\vert=26^{100}$. Пусть в нашей базе данных хранится несколько (пусть до $ 1000$) таких строк вместе со своими хэш-функциями. Мы хотим добавить новую строку, но только в

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

Еще вариант -- в базе данных хранятся не пароли пользователей, а только хэш-функции от них (кодирование md$ 5$). Это нужно, чтобы при взломе базы данных пароли не попали в руки злоумышленников.

При выборе хэш-функции обычно выбирают такую функцию, чтобы:

Укажем некоторые хэш-функции:

Пусть мы имеем базу данных, которая хранит информацию в блоках, номера которых -- значения хэш-функции. То есть в блоке с номером $ x$ хранится информация об объекте $ k\in \mathcal K$, таком, что $ h(k)=x$. Добавляя информацию о другом объекте мы можем столкнуться с коллизией (блок уже занят). Из этой ситуации есть следующие выходы:

Рассмотрим алгоритм поиска со вставкой по таблице с цепочками. Пусть есть таблица размерности $ M>N$ из ячеек, в которых два поля (ссылка на сам объект и ссылка в область переполнения). Пусть есть указатель свободной ячейки области переполнения $ r$. Сначала $ r=N+1$

$\displaystyle \begin{tabular}{l\vert l\vert\vert l\vert r\vert}
\cline{2-4}
&...
...\vdots&&\\
\cline{2-4}
&M&$\bullet$&$\circ$\\
\cline{2-4}
\end{tabular}
$

Пусть мы получили объект $ k$ и вычислили его хэш $ h(k)=x$. Вызываем функцию поиска, реализованную, например, так:

  1. Смотрим в ячейку номер $ x$. Если она пуста, то переходими к шагу $ 2$, иначе, полагаем $ y=x$ и переходим к шагу $ 3$.

  2. Нет такого объекта, добавляем его. Записываем в ячейку $ x$ на месте $ \bullet$, что она ссылается на объект $ k$, а на месте $ \circ$ ничего не ставим. Завершаем алгоритм.

  3. Ячейка $ y$ уже занята некоторым объектом $ l$. Сверяем объект $ k$ с $ l$. Если они равны, переходим к шагу $ 4$. Иначе, если в ячейке на месте $ \circ$ есть ссылка на другую ячейку (с номером $ z$), то полагаем $ y=z$ и переходим к шагу $ 3$, в противном случае -- к шагу $ 5$.

  4. Объект уже есть в базе данных и добавлять его не нужно. Завершаем алгоритм.

  5. Если $ r=M+1$ то наша таблица переполнена и можно выдать ошибку. Если это еще не так, то $ r$ указывает на свободную ячейку области переполнения. Заносим туда информацию об объекте $ k$ (на месте $ \bullet$). На месте $ \circ$ в ячейке $ y$ заносим ссылку на ячейку $ r$. На месте $ \circ$ в ячейке $ r$ ничего не пишем. Увеличиваем $ r$ на единицу. Завершаем алгоритм.



На главную   ::   Содержание