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

Ропот Хэш очень приятно.

для фиксированного набора строк используйте gperf.

Если ваш набор строк изменяется, вы должны выбрать одну хэш-функцию. Эта тема обсуждалась ранее:

каков наилучший алгоритм хэширования для использования в строке stl при использовании hash_map?

есть еще и хорошая статья at eternallyconfuzzled.com.

хэш Дженкинса по одному для строк должен выглядеть примерно так:

#include <stdint.h>

uint32_t hash_string(const char * s)
{
    uint32_t hash = 0;

    for(; *s; ++s)
    {
        hash += *s;
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }

    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);

    return hash;
}

другое решение, которое может быть еще лучше в зависимости от вашего варианта использования является интернированы строки. Вот как работают символы, например, в Lisp.

интернированная строка-это строковый объект, значение которого является адресом фактических строковых байтов. Таким образом, вы создаете объект интернированной строки, проверяя глобальную таблицу: если строка находится там, вы инициализируете интернированную строку по адресу этой строки. Если нет, вы вставляете его, а затем инициализируете свой интернированная строка.

Это означает, что две интернированные строки, построенные из одной строки, будут иметь одно и то же значение, которое является адресом. Поэтому, если N-количество интернированных строк в вашей системе, характеристики:

• медленное построение (требуется поиск и, возможно, выделение памяти)
• требует глобальных данных и синхронизации в случае параллельных потоков
• сравнить это O(1), потому что вы сравниваете адреса, а не фактического строковые байты (это означает, что сортировка работает хорошо, но это не будет алфавитная сортировка).

спасибо,

Карл

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

повысить хэш так же просто, как

#include <boost/functional/hash.hpp>

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

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

вы можете найти импульс на boost.org

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

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

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 поэтому каждый из них будет выглядеть так:

test_aaaa@cloud-nueve.com, test_aaab@yahoo.com, 
test_aaac@gmail.com, test_aaad@hotmail.com and so on.

вот результат теста- 'Colision entre XXX y XXX' означает 'Столкновение XXX и XXX'. "палабра" означает "слова", а "тотал" -то же самое в обоих языках.

    Buscando Colisiones...
    Colision entre 'test_phiz@hotmail.com' y 'test_juxg@cloud-nueve.com' (1DB903B7)
    Colision entre 'test_rfhh@hotmail.com' y 'test_fpgo@yahoo.com' (2F5BC088)
    Colision entre 'test_wxuj@hotmail.com' y 'test_pugy@cloud-nueve.com' (51FD09CC)
    Colision entre 'test_sctb@gmail.com' y 'test_iohw@cloud-nueve.com' (52F5480E)
    Colision entre 'test_wpgu@cloud-nueve.com' y 'test_seik@yahoo.com' (74FF72E2)
    Colision entre 'test_rfll@hotmail.com' y 'test_btgo@yahoo.com' (7FD70008)
    Colision entre 'test_wcho@cloud-nueve.com' y 'test_scfz@gmail.com' (9BD351C4)
    Colision entre 'test_swky@cloud-nueve.com' y 'test_fqpn@gmail.com' (A86953E1)
    Colision entre 'test_rftd@hotmail.com' y 'test_jlgo@yahoo.com' (BA6B0718)
    Colision entre 'test_rfpp@hotmail.com' y 'test_nxgo@yahoo.com' (D0523F88)
    Colision entre 'test_zlgo@yahoo.com' y 'test_rfdd@hotmail.com' (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 строк. Обратите внимание, что ни в одном из случаев не было более 2 коллизий на код. Что я подтверждаю, это отличный хэш для меня, так как мне нужно преобразовать идентификатор входа в 40-битный уникальный идентификатор для индексирования. Поэтому я использую это, чтобы преобразовать учетные данные для входа в 32-битный хэш и использовать дополнительные 8 бит для обработки до 255 коллизий на код, которые lookign на тесте результаты было бы почти невозможно получить.

надеюсь, что это полезно для кого-то.

EDIT:

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

Buscando Colisiones... Всего de Colisiones: 2908 Всего Де Палабрас: 5366384

это 2908 после 5,366,384 попыток!!

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

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

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

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

вы можете увидеть, что .NET использует в строке.Метод GetHashCode () с использованием рефлектора.

Я бы рискнул предположить, что 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 для этого.