Алгоритм быстрого хеширования строк с низкой частотой конфликтов с 32-битным целым числом

Почему бы вам просто не использовать библиотеки Boost? Их функция хеширования проста в использовании, и большая часть вещей в Boost скоро станет частью стандарта C ++. Некоторые из них уже есть.

Boost hash так же просто, как

#include <boost/functional/hash.hpp>

int main()
{
    boost::hash<std::string> string_hash;

    std::size_t h = string_hash("Hash me");
}

Вы можете найти повышение на boost.org

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

I needed a hash function and after reading this post and doing a bit of research on the links given here, I came up with this variation of Daniel J Bernstein's algorithm, which I used to do an interesting test:

unsigned long djb_hashl(const char *clave)
{
    unsigned long c,i,h;

    for(i=h=0;clave[i];i++)
    {
        c = toupper(clave[i]);
        h = ((h << 5) + h) ^ c;
    }
    return h;
}

Этот вариант хеширует строки без учета регистра, что соответствует моей потребности в хешировании учетных данных пользователей. «clave» - это «ключ» на испанском языке. Прошу прощения за испанский, но это мой родной язык, и программа написана на нем.

Что ж, я написал программу, которая будет генерировать имена пользователей от test_aaaa до test_zzzz и, чтобы сделать строки длиннее, я добавил к ним случайный домен в этом списке: cloud-nueve.com, yahoo.com ',' gmail.com 'и' hotmail.com '. Поэтому каждый из них будет выглядеть так:

[email protected], [email protected], 
[email protected], [email protected] and so on.

Вот результат теста: «Столкновение между ХХХ и ХХХ» означает «Столкновение ХХХ и ХХХ». "palabras" означает "слова", а "Total" одинаково на обоих языках.

    Buscando Colisiones...
    Colision entre '[email protected]' y '[email protected]' (1DB903B7)
    Colision entre '[email protected]' y '[email protected]' (2F5BC088)
    Colision entre '[email protected]' y '[email protected]' (51FD09CC)
    Colision entre '[email protected]' y '[email protected]' (52F5480E)
    Colision entre '[email protected]' y '[email protected]' (74FF72E2)
    Colision entre '[email protected]' y '[email protected]' (7FD70008)
    Colision entre '[email protected]' y '[email protected]' (9BD351C4)
    Colision entre '[email protected]' y '[email protected]' (A86953E1)
    Colision entre '[email protected]' y '[email protected]' (BA6B0718)
    Colision entre '[email protected]' y '[email protected]' (D0523F88)
    Colision entre '[email protected]' y '[email protected]' (DEE08108)
    Total de Colisiones: 11
    Total de Palabras  : 456976

Это неплохо, 11 коллизий из 456 976 (конечно, с использованием полных 32 бита в качестве длины таблицы).

При запуске программы с использованием 5 символов, то есть от «test_aaaaa» до «test_zzzzz», на самом деле не хватает памяти для построения таблицы. Ниже представлен результат. «No hay memoria para insertar XXXX (insertadas XXX)» означает «Не осталось памяти для вставки XXX (вставлено XXX)». В основном malloc () потерпел неудачу в этот момент.

    No hay memoria para insertar 'test_epjcv' (insertadas 2097701).

    Buscando Colisiones...

    ...451 'colision' strings...

    Total de Colisiones: 451
    Total de Palabras  : 2097701

Это означает всего 451 коллизию на 2 097 701 струнах. Обратите внимание, что ни в одном из случаев не было более двух коллизий на код. Я подтверждаю, что это отличный хеш для меня, так как мне нужно преобразовать идентификатор входа в 40-битный уникальный идентификатор для индексации. Поэтому я использую это для преобразования учетных данных для входа в 32-битный хэш и использую дополнительные 8 бит для обработки до 255 коллизий на код, которые, глядя на результаты теста, было бы почти невозможно сгенерировать.

Надеюсь, это кому-то будет полезно.

РЕДАКТИРОВАТЬ:

Как и в случае с тестовым блоком AIX, я запускаю его, используя LDR_CNTRL = MAXDATA = 0x20000000, чтобы получить больше памяти и он работал дольше, результаты здесь:

Buscando Colisiones ... Всего коллизий: 2908 Всего мест: 5366384

Это 2908 после 5366384 попыток !!

ОЧЕНЬ ВАЖНО: при компиляции программы с параметром -maix64 (таким образом, длина без знака составляет 64 бита), количество коллизий равно 0 для всех случаев !!!

Хеш-функция Hsieh довольно хороша и имеет несколько тестов / сравнений в качестве общего хэш-функция в C. В зависимости от того, что вы хотите (это не совсем очевидно), вы можете рассмотреть что-то вроде cdb.

У Боба Дженкинса доступно множество хеш-функций, все из которых работают быстро и с низким уровнем коллизий. .

Взгляните на GNU gperf.

Вы можете увидеть, что .NET использует в методе String.GetHashCode (), используя Reflector.

Рискну предположить, что Microsoft потратила много времени на оптимизацию этого. Они также напечатали во всей документации MSDN, что она может постоянно меняться. Так ясно, что это на их «радаре настройки производительности» ;-)

Я бы подумал, что было бы довольно просто перенести на C ++.

В этом предыдущем вопросе есть хорошее обсуждение. >

И хороший обзор того, как выбирать хэш-функции, а также статистику распределения нескольких распространенных здесь

Здесь описан простой способ его самостоятельной реализации: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html

Отрывок из поста:

если, скажем, у нас есть набор символов заглавных английских букв, то длина набора символов равна 26, где A может быть представлено числом 0, B числом 1, C числом 2 и так далее до Z числом 25. Теперь, когда мы хотим сопоставить строку этого набора символов с уникальным числом, мы выполняем то же преобразование, что и в случае двоичного формата.

CRC-32. На это есть около триллиона ссылок в Google.