Сравнение данных с помощью хеш-функции

Обновлено: 21.11.2024

Хэш-таблицы — это популярные структуры данных для хранения пар "ключ-значение". Хэш-функция используется для сопоставления значения ключа (обычно строки) с индексом массива. Эти функции отличаются от криптографических хеш-функций, потому что они должны быть намного быстрее и не должны быть устойчивыми к атаке с прообразом. В этой статье также не упоминается хеширование в больших базах данных; тест включает хеш-таблицы среднего размера, такие как:

таблица символов в парсере,
Таблица IP-адресов для фильтрации сетевого трафика,
словарь в программе подсчета слов или программе проверки орфографии.

мультипликативные хеш-функции, простые и быстрые, но с большим количеством конфликтов;
более сложные функции, которые имеют лучшее качество, но требуют больше времени для расчета.

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

Вопрос в том, ускоряет ли программа использование сложных функций. Сложные функции требуют больше операций на одну клавишу, поэтому они могут работать медленнее. Достаточно ли высока цена коллизий, чтобы оправдать дополнительные операции?

Мультипликативные хеш-функции

Любая мультипликативная хэш-функция является частным случаем следующего алгоритма:

(Иногда вместо сложения используется операция XOR, но это не имеет большого значения.) Хеш-функции различаются только значениями INITIAL_VALUE и множителя (M). Например, популярная функция Бернштейна использует INITIAL_VALUE, равное 5381, и M, равное 33; Функция Кернигана и Ритчи использует INITIAL_VALUE, равное 0, и M, равное 31.

Мультипликативная функция работает путем сложения букв, взвешенных по степени множителя. Например, хэш для слова TONE будет таким:

Давайте введем несколько похожих строк и посмотрим на вывод функций:

Too и top различаются только последней буквой. Буква P следующая за O, поэтому значения хэш-функции отличаются на 1 (1c154 и 1c155, b88af17 и b88af18). То же самое для a000..a009.

Теперь сравним top с tpp. Их хэши будут такими:

Хэши будут отличаться на M * ('P' - 'O') = M . Точно так же, когда первые буквы отличаются на x, их хэши будут отличаться на x * M^2 .

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

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

Точных правил выбора множителя нет, есть только некоторые эвристики:

Реализация открытой адресации или раздельного связывания

При открытой адресации большинство хеш-функций демонстрируют неудобное кластерное поведение в тесте "Числа":

< td>[3158]

Bernst.	K&R	развернуть x17	x65599	FNV	Унив	Weinb.	Hsieh	One-at	Lookup3	Partow	CRC
ОА	426	81	84	207	88	91	273	110	103	92	1042	79
ОА	[8030]	[20810]< /td>	[340]	[3158]	[207]	[480]	[4360]	[342]	[267]	[205]	[20860]	[96]
32-bit	179< /td>	69	74	114	86	80	125	105	99	92	347	82
32-bit	[8030]	[20810]	[340]	[207]	[480]	[4360]	[342]	[267]	[205]< /td>	[20860]	[96]
цепь	92	68	73	82	88	84	73	107	99	95	149	84< /td>
цепь	[500]	[500]	[24]	[258]	[124]	[48]	[100]	[138]	< small>[131]	[108]	[1530]	[64]

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

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

Об авторе

Питер — разработчик Aba Search and Replace, инструмента для замены текста в нескольких файлах. Ему нравится программировать на C с небольшим количеством C++, а также на языке ассемблера x86, Python и PHP.

Создано 14 лет назад Петером Канковски
Последнее изменение 1 год назад
Соавторы: Нильс, Эйс, Вон, Эндрю М. и Георгий 'Санмайце'

213 комментариев

Ниже показаны десять последних комментариев. Показать все комментарии

рад поделиться последним и самым быстрым вариантом FNV1A.

Долгое время я знал, сколько всего еще существует, многие кодеры поделились очень хорошими этюдами, но в моем «Йорикке» есть что-то особенное, . Встроен дзенский подход :P

В настоящее время я пишу безумный поиск совпадений, используя B-деревья, хэшируя миллионы ключей порядка 4,6,8,10,12,14,16,18,36,64, таким образом, хэш сверхвысокой скорости (ДЛЯ МАЛЕНЬКИХ KEYS) необходим, поскольку B-деревья строятся в несколько проходов и должны использоваться миллиарды хеш-вызовов Yorikke. Задержка имеет решающее значение, а пропускная способность невелика.

1024 элемента в таблице (10 бит)

13408 строк прочитано

32768 элементов в таблице (15 бит)

прочитано 3925 строк

8192 элемента в таблице (13 бит)

1024 элемента в таблице (10 бит)

Прочитано 3228 строк

8192 элемента в таблице (13 бит)

1842 строки прочитано

4096 элементов в таблице (12 бит)

Пустыня, надо было исправить v2, теперь все ок, извините - вчера весь день отвлекся.

Итак, третья версия:

Питер, я не вижу способов улучшить хеширование 32-битного кода, поэтому самый быстрый из известных мне 32-битных хэшеров в 64-битном коде:

Какой размер Bucket используется во всех хеш-функциях, упомянутых на графике (качество хэш-функции с использованием книги Red Dragon) в этом блоге? Просьба ответить на запрос пожалуйста.

Здравствуйте, Мохит, спасибо, это хороший вопрос. Количество сегментов (слотов) было равно 2 * количество элементов, округленное до следующего числа, кратного двум. Например, в тесте "числа" в таблице 500 элементов, поэтому количество сегментов (размер хеш-таблицы) равно 2 * 512 = 1024. Надеюсь, это поможет

Спасибо за ответ

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

Это было бы очень полезно с вашей стороны.

Можете ли вы предоставить мне точное значение на графике качества хеш-функции только для набора данных чисел? Это было бы очень полезно с вашей стороны.

Заранее спасибо, @Peter Kankowski.

Где находится список слов Википедии (или откуда его взять) и, что более важно, тестовый код открытого доступа?

Я ищу хорошую комбинацию распространения/лавины OA, которая была бы достаточно дешевой, но не вызывала бы UB или IB в C и была бы чрезвычайно переносимой (поэтому она должна считывать побайтно, что делает CRC на удивление дорогой, от 2,39 до по одному 2.21 в моей тестовой заимствованной системе Windows (обычно ее нет, но ваш источник для нее…))

Вот несколько интересных хеш-функций, которые можно добавить в набор для сравнения:

Читайте также: