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

Ответ 1

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

Этот (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), что является наиболее обычным сценарием. Если у вас есть известный ограниченный домен (набор исправленных входов), вы можете сделать лучше, см. Ответ Fionn.

Ответ 2

Возможно, что-то подобное вам поможет: http://www.gnu.org/s/gperf/

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

Ответ 3

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

http://en.wikipedia.org/wiki/MurmurHash

http://code.google.com/p/smhasher/wiki/MurmurHash3

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

http://www.openssl.org/docs/crypto/sha.html

Ответ 4

Немного поздно, но вот хеширующая функция с чрезвычайно низкой скоростью столкновения для 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 и djb2 не преуспели, а slash_hash во всех тестах немного лучше, чем MurmurHash2)