Каков наилучший способ хеширования строкового вектора не очень длинного (URL)?

Question

Я сейчас занимаюсь классификацией URL.Я делю URL с помощью "/?" И т. Д., Создавая кучу частей.В процессе, мне нужно хешировать первую часть к k-й части, скажем, k = 2, затем для «http://stackoverflow.com/questions/ask", ключом является строковый вектор« stackoverflow.com questions ». В настоящее время хеш похож на Hash. Ноон потребляет много памяти. Интересно, может ли MD5 помочь или есть другие альтернативы. По сути, мне не нужно точно восстанавливать ключ, если различаются разные ключи. Спасибо!

Answer 1

MD5 - хороший хеш-код для вещей, где безопасность не является проблемой.Он быстрый и достаточно длинный (для большинства приложений достаточно 128 бит).Кроме того, распределение очень хорошее.

Adler32 будет возможной альтернативой.Это очень легко реализовать, всего несколько строк кода.Это даже быстрее, чем MD5.И это достаточно долго / достаточно хорошо для многих приложений (хотя для многих это не так).(Я знаю, что Adler32 строго не является хеш-кодом, но он все равно подойдет для многих приложений)

Однако, если хранение хеш-кода занимает много памяти, вы всегда можете урезать хеш-код.код или используйте XOR, чтобы «сжать» его.Например,

uint8_t md5[16];
GetMD5(md5, ...);

// use XOR to shrink the MD5 to 32 bits
for (size_t i = 4; i < 16; i++)
    md5[i % 4] ^= md5[i];

// assemble the parts into one uint32_t
uint32_t const hash = md5[0] + (md5[1] << 8) + (md5[2] << 16) + (md5[3] << 24);

Лично я думаю, что MD5 будет излишним.Посмотрите на Adler32 , я думаю, что это подойдет.

---

EDIT

Я должен исправить себя: Adler23 довольноплохой выбор для коротких строк (менее нескольких тысяч байт).Я полностью забыл об этом.Но всегда есть очевидное: CRC32.Не так быстро, как Adler23 (примерно с той же скоростью, что и MD5), но все еще приемлемо прост в реализации, а также существует масса существующих реализаций со всеми видами лицензий.

Answer 2

Он занимает много памяти

Если ваш код уже работает, вы можете оставить его как есть.Если у вас нет цели, вы не будете знать, когда закончите.Вы уверены, что «много» является синонимом «слишком много» в вашем случае?

Если вы решите, что вам действительно нужно изменить свой рабочий код, вам следует рассмотреть большое разнообразие вариантов, которые у вас есть, скореечем взять чье-то слово для конкретного алгоритма:

• http://en.wikipedia.org/wiki/List_of_hash_functions
• http://en.wikipedia.org/wiki/Comparison_of_cryptographic_hash_functions
• http://www.strchr.com/hash_functions

и т. д.

Не уверен насчет последствий для памяти, и это наверняка изменит ваш профиль перфекта, но вы также можете посмотреть на использование Tries:

http://en.wikipedia.org/wiki/Trie

Answer 3

Если вы пытаетесь выяснить, совпадают ли два URL-адреса, рассматривали ли вы возможность хранения двоичной версии IP-адреса сервера?Если два имени сервера соответствуют одному и тому же адресу, это неправильно или является преимуществом для вашего приложения?