Какая хорошая хэш-функция для английских слов?

17

У меня длинный список английских слов, и я хотел бы их хэш. Что было бы хорошей функцией хэширования? Пока моя функция хэширования суммирует значения ASCII букв, а затем по модулю размер таблицы. Я ищу что-то эффективное и простое.

    
задан Mike G 09.10.2011 в 01:20
источник
  • Отметьте здесь cse.yorku.ca/~oz/hash.html –  c-smile 09.10.2011 в 01:30
  • Возможный дубликат функции Good Hash для строк и что такое хорошая 64-битная хеш-функция в Java для текстовых строк? –  M.J. Rayburn 02.09.2017 в 03:00

4 ответа

15

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

Этот ( djb2 ) довольно популярен и прекрасно работает с строками ASCII.

unsigned long hashstring(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

Если вам нужно больше альтернатив и некоторые меры, прочитайте здесь .

Добавлено: Это общие хеширующие функции, где входной домен неизвестен заранее (за исключением, возможно, некоторых очень общих предположений: например, приведенное выше работает немного лучше с ascii ввод), что является самым обычным сценарием. Если у вас есть известный ограниченный домен (набор исправленных входов), вы можете сделать лучше, см. Ответ Фиона.

    
ответ дан leonbloy 09.10.2011 в 01:28
  • 5381 - размер таблицы? –  Mike G 09.10.2011 в 01:31
  • Нет, это просто «семя», довольно произвольное. –  leonbloy 09.10.2011 в 01:32
  • @MikeG: это «семя» или начальное значение. Этот широко известен как хэш «Times 33». –  user7116 09.10.2011 в 01:32
  • Он может возвращать любое действительное значение без знака в теории. Вам решать манипулировать хешем в соответствии с вашими ограничениями. –  Jonathan Grynspan 09.10.2011 в 01:43
  • @MikeG: в общем случае вы не указываете размер таблицы в хэш-алгоритме (и если вы не знаете об этом, используйте уже созданную таблицу ...). Таблица может увеличиваться или уменьшаться в зависимости от количества элементов (для хороших реализаций), поэтому вы просто вычисляете хеш и принимаете хэш по модулю текущего размера, чтобы знать, в каком ведре его вводить. –  Matthieu M. 09.10.2011 в 11:57
6

Возможно, что-то подобное вам поможет: Ссылка

Он генерирует оптимизированную хэш-функцию для входного домена.

    
ответ дан Fionn 09.10.2011 в 01:25
6

Если вам это не нужно, это будет криптографически безопасным, я бы предложил Murmur Hash. Это очень быстро и имеет высокую диффузию. Прост в использовании.

Ссылка

Ссылка

Если вам нужен криптографически безопасный хэш, я предлагаю SHA1 через OpenSSL.

Ссылка

    
ответ дан selbie 09.10.2011 в 01:29
  • +1 для MurmurHash, знаете ли вы, если сравнивать между CityHash и MurmurHash? Я слышал хорошие вещи обо всех, но никогда не видел всеобъемлющего сравнения, просто были некоторые анекдотические факты. –  Matthieu M. 09.10.2011 в 11:59
2

Немного поздно, но вот хеширующая функция с чрезвычайно низкой скоростью столкновения для 64-битной версии ниже и ~ почти ~ как хорошая для 32-разрядной версии:

uint64_t slash_hash(const char *s)
//uint32_t slash_hash(const char *s)
{
    union { uint64_t h; uint8_t u[8]; };
    int i=0; h=strlen(s);
    while (*s) { u[i%8] += *s + i + (*s >> ((h/(i+1)) % 5)); s++; i++; }
    return h; //64-bit
    //return (h+(h>>32)); //32-bit
}

Хэш-числа также очень равномерно распределены по всему диапазону, без комков, которые я мог обнаружить - это было проверено только с использованием случайных строк.
[edit]
Также проверено на слова, извлеченные из локальных текстовых файлов, в сочетании с словарем словаря / словаря LibreOffice (английский и французский - более 97000 слов и конструкций) с 0 столкновениями в 64-битном и 1 столкновении в 32 -бит:)

(Также по сравнению с FNV1A_Hash_Yorikke, djb2 и MurmurHash2 на одних и тех же наборах: Yorikke & amp; djb2 не преуспел, а slash_hash сделал несколько лучше, чем MurmurHash2 во всех тестах)

    
ответ дан slashmais 23.12.2012 в 12:16
  • Это разумная хэш-функция. Я предлагаю избегать неназванного союза. - >> union {uint64_t h; uint8_t u [8]; } uu; и аналогичные изменения в коде - >> uu.h = strlen (s); ... uu.u [i% 8] + = ... и т. д. –  joop 05.01.2017 в 12:13