Быстрый алгоритм хеширования строк с низкой частотой коллизий с 32-битным целым числом [закрыт]
https://stackoverflow.com/questions/114085
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
У меня есть много несвязанных именованных объектов, по которым я хотел бы выполнить быстрый поиск."Трубкозуб" всегда и везде является "муравьедом", поэтому хеширование строки и повторное использование целого числа было бы неплохо для ускорения сравнений.Весь набор имен неизвестен (и меняется с течением времени).Что такое быстрый алгоритм хеширования строк, который будет генерировать небольшие (32 или 16) битные значения и иметь низкую частоту столкновений?
Я хотел бы видеть оптимизированную реализацию, специфичную для C / C ++.
Решение
Один из самых Варианты FNV должен соответствовать вашим требованиям.Они быстры и производят довольно равномерно распределенную продукцию.
Другие советы
Бормочущий Гашиш это довольно мило.
Для фиксированного набора строк используйте gperf.
Если ваш набор строк изменится, вам нужно выбрать одну хэш-функцию.Эта тема уже обсуждалась ранее:
Какой алгоритм хеширования лучше всего использовать для строки stl при использовании hash_map?
Там также есть хорошая статья в 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;
}
Другим решением, которое может быть еще лучше в зависимости от вашего варианта использования, является интернированные строки.Вот как работают символы, напримерна лиспе.
Интернированная строка - это строковый объект, значением которого является адрес фактических строковых байтов.Итак, вы создаете интернированный строковый объект, проверяя глобальную таблицу:если строка находится там, вы инициализируете интернированную строку по адресу этой строки.Если нет, вы вставляете его, а затем инициализируете свою интернированную строку.
Это означает, что две интернированные строки, построенные из одной и той же строки, будут иметь одинаковое значение, которое является адресом.Таким образом, если N - количество интернированных строк в вашей системе, то характеристики следующие:
- Медленное построение (требуется поиск и, возможно, выделение памяти)
- Требуются глобальные данные и синхронизация в случае параллельных потоков
- Compare - это 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 по адресу 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;
}
Этот вариант хэширует строки, игнорируя регистр, что соответствует моей потребности в хэшировании учетных данных для входа пользователей."клаве" по-испански означает "ключ".Прошу прощения за испанский, но это мой родной язык, и программа написана на нем.
Ну, я написал программу, которая будет генерировать имена пользователей от '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 (вставка 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 коллизий в коде, которые, судя по результатам тестирования, было бы практически невозможно сгенерировать.
Надеюсь, это кому-то пригодится.
Редактировать:
Как и в случае с тестовым полем AIX, я запускаю его, используя LDR_CNTRL=MAXDATA = 0x20000000, чтобы предоставить ему больше памяти и работать дольше, результаты здесь:
Buscando Colisiones...Total de Colisiones:2908 Total de Palabras :5366384
Это 2908 после 5 366 384 попыток!!
ОЧЕНЬ ВАЖНЫЙ:При компиляции программы с использованием -maix64 (таким образом, длина без знака равна 64 битам) количество коллизий равно 0 для всех случаев!!!
Взгляните на GNU gperf.
У Боба Дженкинса есть множество доступных хэш-функций, все из которых быстры и имеют низкую частоту столкновений.
Вы можете посмотреть, что .NET использует в строке.Метод 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 на это есть около триллиона ссылок.
