Processing math: 100%

Хеш-таблицы

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

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

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

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

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

Хеш-функции

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

Ассоциативные контейнеры — модели для отображений K1+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+a1dn1+a2dn2+a3dn3++and0)modN

Для N=232 очень популярны значения параметров d=31 и a0=7.

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

H(ab)=((H(a)a0)d|b|+H(b))modN

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

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

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

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

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

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