Бесколлизионный хеш-алгоритм для строк длиной до 255 символов

Question

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

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

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

---

Ответ :

Один из вариантов FNV должен соответствовать вашим требованиям. Они быстрые и выдают довольно равномерно распределенные результаты. (Ответ Паукообразный )

---

Answer 1

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

Answer 2

Вчера Ронни Пфанншмидт провел тест с общими английскими словами и не столкнулся с какими-либо коллизиями для 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 3

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

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

Answer 4

Java String.hash () можно легко просмотреть здесь , его алгоритм

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

Answer 5

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

Статья MSDN о хэш-кодах