Хеш-функция для строки
Я работаю над хэш-таблицей на языке Си и тестирую хеш-функцию для строки.
Первая функция, которую я попробовал, - добавить код ascii и использовать модуль (%100), но у меня плохие результаты с первым тестом данных: 40 столкновений для 130 слов.
Конечные входные данные будут содержать 8 000 слов (это словари хранятся в файле). Хеш-таблица объявлена как int table[10000] и содержит позицию слова в текстовом файле.
Первый вопрос: какой алгоритм хеширования строк лучший? а как определить размер хеш-таблицы?
заранее спасибо!
:-)
11 ответов
У меня были хорошие результаты с djb2 Дэн Бернштейн.
unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
Во-первых, вы обычно не хотите использовать криптографический хеш для хеш-таблицы. Алгоритм, который очень быстр по криптографическим стандартам, все еще мучительно медленен по стандартам хеш-таблиц.
Во-вторых, вы хотите убедиться, что каждый бит ввода может / повлияет на результат. Один простой способ сделать это - повернуть текущий результат на некоторое количество битов, а затем XOR текущего хеш-кода с текущим байтом. Повторяйте, пока не дойдете до конца строки. Обратите внимание, что вы обычно не хотите, чтобы вращение было даже кратным размеру байта.
Например, предполагая общий случай 8-битных байтов, вы можете повернуть на 5 битов:
int hash(char const *input) {
int result = 0x55555555;
while (*input) {
result ^= *input++;
result = rol(result, 5);
}
}
Изменить: Также обратите внимание, что 10000 слотов редко является хорошим выбором для размера хэш-таблицы. Обычно вам требуется одна из двух вещей: либо вы хотите использовать простое число в качестве размера (необходимого для обеспечения корректности при некоторых типах разрешения хеша), либо степень 2 (поэтому уменьшение значения до правильного диапазона можно сделать с помощью простого битовая маска).
Я хотел проверить ответ Сяонин Бянь, но, к сожалению, он не опубликовал свой код. Поэтому я реализовал небольшой набор тестов и запустил разные маленькие хеш-функции для списка из 466К английских слов, чтобы увидеть количество конфликтов для каждого из них:
Hash function | Collisions | Time (words) | Time (file)
=================================================================
crc32b | 23 (0.005%) | 112 ms | 38 ms
MurmurOAAT | 26 (0.006%) | 86 ms | 10 ms
FNV hash | 32 (0.007%) | 87 ms | 7 ms
Jenkins OAAT | 36 (0.008%) | 90 ms | 8 ms
DJB2 hash | 344 (0.074%) | 87 ms | 5 ms
K&R V2 | 356 (0.076%) | 86 ms | 5 ms
Coffin | 763 (0.164%) | 86 ms | 4 ms
x17 hash | 2242 (0.481%) | 87 ms | 7 ms
-----------------------------------------------------------------
MurmurHash3_x86_32 | 19 (0.004%) | 90 ms | 3 ms
Я включил время для обоих: на хеширование всех слов по отдельности и хеширование всего файла со всеми английскими словами один раз. Я также включил более сложный
MurmurHash3_x86_32 в мой тест для справки.
Заключение:
- Практически нет смысла использовать популярную хеш-функцию DJB2 для строк на архитектуре Intel x86-64. Потому что у него гораздо больше конфликтов, чем у аналогичных функций (MurmurOAAT, FNV и Jenkins OAAT), при очень схожей пропускной способности.
Код теста:
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#define MAXLINE 2048
#define SEED 0x12345678
uint32_t DJB2_hash(const uint8_t *str)
{
uint32_t hash = 5381;
uint8_t c;
while ((c = *str++))
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
uint32_t FNV(const void* key, int len, uint32_t h)
{
// Source: https://github.com/aappleby/smhasher/blob/master/src/Hashes.cpp
h ^= 2166136261UL;
const uint8_t* data = (const uint8_t*)key;
for(int i = 0; i < len; i++)
{
h ^= data[i];
h *= 16777619;
}
return h;
}
uint32_t MurmurOAAT_32(const char* str, uint32_t h)
{
// One-byte-at-a-time hash based on Murmur's mix
// Source: https://github.com/aappleby/smhasher/blob/master/src/Hashes.cpp
for (; *str; ++str) {
h ^= *str;
h *= 0x5bd1e995;
h ^= h >> 15;
}
return h;
}
uint32_t KR_v2_hash(const char *s)
{
// Source: https://stackoverflow.com/a/45641002/5407270
uint32_t hashval = 0;
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31*hashval;
return hashval;
}
uint32_t Jenkins_one_at_a_time_hash(const char *str, size_t len)
{
uint32_t hash, i;
for(hash = i = 0; i < len; ++i)
{
hash += str[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
uint32_t crc32b(const uint8_t *str) {
// Source: https://stackoverflow.com/a/21001712
unsigned int byte, crc, mask;
int i = 0, j;
crc = 0xFFFFFFFF;
while (str[i] != 0) {
byte = str[i];
crc = crc ^ byte;
for (j = 7; j >= 0; j--) {
mask = -(crc & 1);
crc = (crc >> 1) ^ (0xEDB88320 & mask);
}
i = i + 1;
}
return ~crc;
}
inline uint32_t _rotl32(uint32_t x, int32_t bits)
{
return x<<bits | x>>(32-bits); // C idiom: will be optimized to a single operation
}
uint32_t Coffin_hash(char const *input) {
// Source: https://stackoverflow.com/a/7666668/5407270
uint32_t result = 0x55555555;
while (*input) {
result ^= *input++;
result = _rotl32(result, 5);
}
return result;
}
uint32_t x17(const void * key, int len, uint32_t h)
{
// Source: https://github.com/aappleby/smhasher/blob/master/src/Hashes.cpp
const uint8_t * data = (const uint8_t*)key;
for (int i = 0; i < len; ++i)
{
h = 17 * h + (data[i] - ' ');
}
return h ^ (h >> 16);
}
uint32_t apply_hash(int hash, const char* line)
{
switch (hash) {
case 1: return crc32b((const uint8_t*)line);
case 2: return MurmurOAAT_32(line, SEED);
case 3: return FNV(line, strlen(line), SEED);
case 4: return Jenkins_one_at_a_time_hash(line, strlen(line));
case 5: return DJB2_hash((const uint8_t*)line);
case 6: return KR_v2_hash(line);
case 7: return Coffin_hash(line);
case 8: return x17(line, strlen(line), SEED);
default: break;
}
return 0;
}
int main(int argc, char* argv[])
{
// Read arguments
const int hash_choice = atoi(argv[1]);
char const* const fn = argv[2];
// Read file
FILE* f = fopen(fn, "r");
// Read file line by line, calculate hash
char line[MAXLINE];
while (fgets(line, sizeof(line), f)) {
line[strcspn(line, "\n")] = '\0'; // strip newline
uint32_t hash = apply_hash(hash_choice, line);
printf("%08x\n", hash);
}
fclose(f);
return 0;
}
Википедия демонстрирует красивую строковую хеш-функцию под названием Jenkins One At A Time Hash. Он также цитирует улучшенные версии этого хэша.
uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
uint32_t hash, i;
for(hash = i = 0; i < len; ++i)
{
hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
Djb 2 имеет 317 коллизий для этого 466k английского словаря, в то время как MurmurHash не имеет ни одного для 64-битных хэшей и 21 для 32-битных хэшей (около 25 следует ожидать для 466k случайных 32-битных хэшей). Я рекомендую использовать MurmurHash, если он доступен, это очень быстро, потому что занимает несколько байтов за раз. Но если вам нужна простая и короткая хэш-функция для копирования и вставки в ваш проект, я бы рекомендовал использовать пошаговую версию по одному байту:
uint32_t inline MurmurOAAT32 ( const char * key)
{
uint32_t h(3323198485ul);
for (;*key;++key) {
h ^= *key;
h *= 0x5bd1e995;
h ^= h >> 15;
}
return h;
}
uint64_t inline MurmurOAAT64 ( const char * key)
{
uint64_t h(525201411107845655ull);
for (;*key;++key) {
h ^= *key;
h *= 0x5bd1e9955bd1e995;
h ^= h >> 47;
}
return h;
}
Короче говоря, оптимальный размер хэш-таблицы - это как можно больший размер, но при этом он умещается в памяти. Поскольку обычно мы не знаем или не хотим узнать, сколько памяти у нас доступно, и это может даже измениться, оптимальный размер хеш-таблицы примерно в 2 раза больше ожидаемого количества элементов, которые будут храниться в таблице. Выделение гораздо большего количества сделает вашу хеш-таблицу быстрее, но с быстро убывающей отдачей, сделав вашу хеш-таблицу меньше, чем это, сделает ее экспоненциально медленнее. Это связано с тем, что существует нелинейный компромисс между пространственной и временной сложностью для хеш-таблиц с оптимальным коэффициентом загрузки 2-sqrt(2) = 0,58... очевидно.
Существует ряд существующих реализаций хеш-таблиц для C, от стандартной библиотеки C hcreate/hdestroy/hsearch до тех, что в APR и glib, которые также предоставляют встроенные хэш-функции. Я настоятельно рекомендую использовать их, а не изобретать собственную хеш-таблицу или хеш-функцию; они были сильно оптимизированы для общих случаев использования.
Однако, если ваш набор данных статичен, лучшим решением будет, вероятно, использование идеального хэша. gperf сгенерирует для вас идеальный хеш для данного набора данных.
Хоть djb2, как представлено на stackru cnicutar, почти наверняка лучше, я думаю, что стоит также показать хеши K&R:
1) Очевидноужасный алгоритм хеширования, представленный в K&R 1st edition ( source)
unsigned long hash(unsigned char *str)
{
unsigned int hash = 0;
int c;
while (c = *str++)
hash += c;
return hash;
}
2) Вероятно, довольно приличный алгоритм хеширования, представленный в версии 2 K&R(проверено мной на стр. 144 книги); NB: обязательно удалите% HASHSIZEиз оператора return, если вы планируете делать модуль sizing-to-your-array-length вне алгоритма хеширования. Кроме того, я рекомендую вам сделать возврат и тип "hashval"unsigned long вместо простого unsigned (INT).
unsigned hash(char *s)
{
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31*hashval;
return hashval % HASHSIZE;
}
Обратите внимание, что из двух алгоритмов ясно, что одна из причин, по которой хэш 1-го издания настолько ужасен, состоит в том, что он НЕ учитываетпорядок символов в строках, поэтому hash("ab") поэтому будет возвращать то же значение, что и hash("ba"), Однако это не так с хешем 2-го издания, который (намного лучше!) Вернул бы два разных значения для этих строк.
GCC C++11 хэш-функции, используемые дляunordered_map(шаблон хеш-таблицы) иunordered_set(шаблон хеш-набора) выглядит следующим образом.
- Это частичный ответ на вопрос о том, какие используются хеш-функции GCC C++11, в котором говорится, что GCC использует реализацию MurmurHashUnaligned2 от Austin Appleby ( http://murmurhash.googlepages.com/).
- В файле "gcc/libstdC++-v3/libsupC++/hash_bytes.cc", здесь ( https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/libsupc++/hash_bytes.cc) я нашел реализации. Вот пример для возвращаемого значения "32-bit size_t", например (от 11 августа 2017 года):
Код:
// Implementation of Murmur hash for 32-bit size_t.
size_t _Hash_bytes(const void* ptr, size_t len, size_t seed)
{
const size_t m = 0x5bd1e995;
size_t hash = seed ^ len;
const char* buf = static_cast<const char*>(ptr);
// Mix 4 bytes at a time into the hash.
while (len >= 4)
{
size_t k = unaligned_load(buf);
k *= m;
k ^= k >> 24;
k *= m;
hash *= m;
hash ^= k;
buf += 4;
len -= 4;
}
// Handle the last few bytes of the input array.
switch (len)
{
case 3:
hash ^= static_cast<unsigned char>(buf[2]) << 16;
[[gnu::fallthrough]];
case 2:
hash ^= static_cast<unsigned char>(buf[1]) << 8;
[[gnu::fallthrough]];
case 1:
hash ^= static_cast<unsigned char>(buf[0]);
hash *= m;
};
// Do a few final mixes of the hash.
hash ^= hash >> 13;
hash *= m;
hash ^= hash >> 15;
return hash;
}
Я попробовал эти хэш-функции и получил следующий результат. У меня около 960^3 записей, каждая длиной 64 байта, 64 символа в другом порядке, хэш-значение 32 бита. Коды отсюда.
Hash function | collision rate | how many minutes to finish
MurmurHash3 | 6.?% | 4m15s
Jenkins One.. | 6.1% | 6m54s
Bob, 1st in link| 6.16% | 5m34s
SuperFastHash | 10% | 4m58s
bernstein | 20% | 14s only finish 1/20
one_at_a_time | 6.16% | 7m5s
crc | 6.16% | 7m56s
Одна странная вещь состоит в том, что почти все хеш-функции имеют частоту столкновений 6% для моих данных.
Во-первых, 40 коллизий для 130 слов хэшируются до 0..99 плохо? Вы не можете ожидать идеального хеширования, если не предпринимаете шагов специально для того, чтобы это произошло. Обычная хэш-функция в большинстве случаев не будет иметь меньше коллизий, чем случайный генератор.
Хеш-функция с хорошей репутацией - MurmurHash3.
Наконец, что касается размера хеш-таблицы, это действительно зависит от того, какой тип хеш-таблицы вы имеете в виду, особенно от того, являются ли сегменты расширяемыми или однослотовыми. Если сегменты расширяемы, снова есть выбор: вы выбираете среднюю длину сегментов для ограничений памяти / скорости, которые у вас есть.
Я хочу подвести итог для новичков в C, таких как я. По словам точных усилий Андрея Макухи,MurmurHash3лучший:
unsigned long hash(const char* str){
unsigned int h = 0x12345678;
for (; *str; ++str) {
h ^= *str;
h *= 0x5bd1e995;
h ^= h >> 15;
}
return h;
}
Одна вещь, которую я использовал с хорошими результатами, заключается в следующем (я не знаю, упоминалось ли оно уже, потому что я не могу вспомнить его название).
Вы предварительно вычисляете таблицу T со случайным числом для каждого символа в алфавите вашей клавиши [0,255]. Вы хешируете свой ключ 'k0 k1 k2 ... kN', взяв T[k0] xor T[k1] xor ... xor T[kN]. Вы можете легко показать, что это так же случайно, как ваш генератор случайных чисел, и его вычислительно очень выполнимо, и если вы действительно столкнетесь с очень плохим экземпляром с множеством коллизий, вы можете просто повторить все это, используя новую партию случайных чисел.