Хеширование std :: string для чего-то другого, кроме std :: size_t

Question

В качестве части проекта, над которым я сейчас работаю, мне нужно использовать несколько относительно коротких строк (например, «ABCD1234») в качестве ключей для пользовательского контейнера. Проблема в том, что объекты в этом контейнере имеют тип, чей «первичный ключ», так сказать, является числовым. Поэтому мне нужно взять уникальные строки, предоставленные мне, перевести их в нечто числовое и убедиться, что я сохраню уникальность.

Я пытался использовать boost::hash, и, хотя я думаю, что это сработает, меня раздражает то, насколько велика хеш-ценность, особенно учитывая, что я знаю, что собираюсь начать с коротких строк.

Есть ли другая библиотека, родная или сторонняя, я мог бы использовать? Это, безусловно, удобная вещь, поэтому я не слишком волнуюсь об этом, но подумал, что могу спросить.

Answer 1

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

Здесь я приспособлен для возврата коротких/16 бит. Может потребоваться какая-то настройка.

unsigned short hash(std::string const& s) { 
    short results = 3; 
    for (auto current = s.begin(); current != s.end(); ++ current) { 
     unsigned char c = static_cast<unsigned char>(*current); 
     results = results + ((results) << 5) + *(c + i) + ((*(c + i)) << 7); 
     i++; 
    } 
    return ((results)^(results >> 16)) & 0xffff; 
} 

Кроме того, если вы знаете, что ваши ключи опережают время и там не так много из них, вы можете посмотреть в совершенный хэш

Answer 2

Вы можете использовать правильный криптографический сильные хэш (дайджестов).

Они обладают прекрасным свойством, что их можно усекать без удаления их случайных свойств распределения (это не так, поскольку значения хэша общего назначения, а также не UUID).

Говоря, что сырой SHA-1 намного длиннее (160 бит), а также не так быстро, вы можете усекать его слишком большими значениями, если вы можете обеспечить полезную небольшую вероятность столкновения.

Это подход, который Darcs, Mercurial, Git и т. Д. Принимают с их идентификаторами фиксации.

Замечание относительно скорости, SHA-2 работает быстрее и дает дайджест на 512 бит, поэтому существует специальный подход, известный как SHA-512/64, например. для обрезания 512 бит SHA-2 в 64-й дайджест. Кроме того, вы можете посмотреть более быстрые хэши, такие как BLAKE или BLAKE2.

Если вы ищете идеальный хэш для известных строк, вот старый мой ответ, что дает полный пример этого:

• Is it possible to map string to int faster than using hashmap?

Answer 3

Оказывается, ни решение жизнеспособно для меня. Мне просто нужно работать с size_t. Спасибо хоть.