Хеш-таблицы

Деревья поиска обладают не слишком высокой плотностью расположения данных в памяти: в лучшем случае они представляют собой набор массивов-уровней, но при этом в них проблематично добавлять новые элементы.

Наиболее же гибкие разновидности деревьев состоят из большого количества блоков маленького размера, расположенных в памяти где повезёт.

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

Поэтому чем локальнее расположены данные, тем быстрее можно с ними работать.

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

Хеш-функции

Массивы с точки зрения математики — модели для отображений \([0,N) \rightarrow X\), где \([0,N)\) — множество натуральных чисел от \(0\) до \(N\).

Ассоциативные контейнеры — модели для отображений \(K \rightarrow 1+V\).

Массив можно превратить в ассоциативный контейнер, выбрав некоторую функцию \(h: K \rightarrow [0, N)\) и взяв \(X = 1+V\):

def new(size): return [None]*size

def put(array, key, value):
  array[h(key)] = [value]

def get(array, key):
  result = array[h(key)]

  if result == None: raise KeyError  ## тот самый элемент множества 1

  return result[0]

Это — наиболее примитивная версия хеш-таблицы. Та самая функция \(h\), преобразующая ключи в индексы массива, традиционно называется хеш-функцией. Обычно от хеш-функции (в аспекте реализации хеш-таблиц) требуются две вещи:

высокая скорость работы
относительно равномерное распределение значений

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

Сначала мы обсудим один из способов эффективного хеширования, а затем — способы разрешения конфликтов.

Полиномиальные хеши последовательностей

Допустим, что мы умеем каким-то образом элементам множества \(A\) сопоставлять целые числа. Научимся сопоставлять целые числа последовательностям таких элементов так, чтобы наиболее распространённые операции над последовательностями соответствовали каким-то простым операциям над соответствующими этим последовательностям числами.

Для простоты будем считать, что в последовательности находятся не элементы множества \(A\), а соответствующие этим элементам числа.

Полиномиальным хешем последовательности \(a_1, a_2, \ldots a_n\) относительно параметров \(a_0\), \(d\) и \(N\) назовём значение выражения

\[ H(a) = (a_0 d^{n} + a_1 d^{n-1} + a_2 d^{n-2} + a_3 d^{n-3} + \ldots + a_n d^{0}) \bmod N \]

Для \(N=2^{32}\) очень популярны значения параметров \(d=31\) и \(a_0=7\).

Главная особенность полиномиальных хешей — возможность быстрой их конкатенации: если \(a\) и \(b\) — две последовательности, то

\[ H(ab) = ((H(a) - a_0)d^{|b|} + H(b)) \bmod N \]

где \(|b|\) — длина последовательности \(b\).

Нетрудно заметить, что сложность такой операции: логарифм длины последовательности \(b\), поскольку возведение в степень по фиксированному модулю — как раз логарифмическая операция.

Хеш-таблицы со списками кандидатов

Появится после окончания срока сдачи домашнего задания.

Хеш-таблицы с неточным расположением данных

Появится после окончания срока сдачи домашнего задания.