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

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

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

Один из Варианты FNV должен соответствовать вашим требованиям. Они быстрые и производят довольно равномерно распределяемые результаты.

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

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

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

Шепот хеша довольно хорош.

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

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

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

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

Ваше здоровье,

Карл

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

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

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

Почему бы вам просто не использовать Библиотеки 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

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

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

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

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

Также есть хорошая статья в eternalconfuzzled.com.

Хеш-код Jenkins для строк должен выглядеть примерно так:

#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;
}

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

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

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 для всех случаев !!!

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

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

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