Хеш-таблицы
Деревья поиска обладают не слишком высокой плотностью расположения данных в памяти: в лучшем случае они представляют собой набор массивов-уровней, но при этом в них проблематично добавлять новые элементы.
Наиболее же гибкие разновидности деревьев состоят из большого количества блоков маленького размера, расположенных в памяти где повезёт.
При этом архитектура современных ЭВМ не рассчитана на частые операции доступа к большому количеству различных участков памяти: если суммарная длина этих участков больше размера кэша процессора, приходится периодически перекладывать данные из оперативной памяти в кэш, что весьма временезатратно.
Поэтому чем локальнее расположены данные, тем быстрее можно с ними работать.
Идеальная с этой точки зрения структура данных — массив. Хеш-таблицы представляют собой некую модификацию идеи массива, позволяющую использовать массив в качестве эффективного ассоциативного контейнера для довольно широкого спектра видов ключей.
Хеш-функции
Массивы с точки зрения математики — модели для отображений [0,N)→X, где [0,N) — множество натуральных чисел от 0 до N.
Ассоциативные контейнеры — модели для отображений K→1+V.
Массив можно превратить в ассоциативный контейнер, выбрав некоторую функцию h:K→[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, а соответствующие этим элементам числа.
Полиномиальным хешем последовательности a1,a2,…an относительно параметров a0, d и N назовём значение выражения
H(a)=(a0dn+a1dn−1+a2dn−2+a3dn−3+…+and0)modN
Для N=232 очень популярны значения параметров d=31 и a0=7.
Главная особенность полиномиальных хешей — возможность быстрой их конкатенации: если a и b — две последовательности, то
H(ab)=((H(a)−a0)d|b|+H(b))modN
где |b| — длина последовательности b.
Нетрудно заметить, что сложность такой операции: логарифм длины последовательности b, поскольку возведение в степень по фиксированному модулю — как раз логарифмическая операция.
Хеш-таблицы со списками кандидатов
Появится после окончания срока сдачи домашнего задания.
Хеш-таблицы с неточным расположением данных
Появится после окончания срока сдачи домашнего задания.