Хэш-алгоритм

Question

Я ищу хэш-алгоритм, чтобы создать как можно ближе к уникальному хэшу строки (max len = 255), который создает длинное целое число (DWORD).

Я понимаю, что 26^255 >> 2^32, но также знаю, что число слов на английском языке намного меньше, чем 2^32.

Строки, которые мне нужны для 'hash', будут в основном одиночными словами или некоторой простой конструкцией с использованием двух или трех слов.

---

Ответ:

Один из FNV variants должен соответствовать вашим требованиям. Они быстрые и производят довольно равномерно распределенные выходы. (Ответил Arachnid)

---

Answer 1

См here для предыдущей итерации этого вопроса (и ответ).

Answer 2

Один из методов заключается в использовании известного алгоритма хеширования (скажем, MD5 или SHA-1) и использования только первых 32 бит результата.

Помните, что риск столкновения хэшей увеличивается быстрее, чем вы могли ожидать. Для получения информации об этом, читайте о Birthday Paradox.

Answer 3

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

Здесь реализация:

static long 
string_hash(PyStringObject *a) 
{ 
    register Py_ssize_t len; 
    register unsigned char *p; 
    register long x; 

    if (a->ob_shash != -1) 
     return a->ob_shash; 
    len = Py_SIZE(a); 
    p = (unsigned char *) a->ob_sval; 
    x = *p << 7; 
    while (--len >= 0) 
     x = (1000003*x)^*p++; 
    x ^= Py_SIZE(a); 
    if (x == -1) 
     x = -2; 
    a->ob_shash = x; 
    return x; 
} 

Answer 4

Н (ключ) = [GetHash (ключ) + 1 + (((GetHash (ключ) >> 5) + 1),% (hashsize - 1))] % hashsize

MSDN article on HashCodes

Answer 5

String.hash в Java() может быть легко просмотрены here, его алгоритм

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]