хеширование словаря в C ++

Question

привет Я хочу использовать хэш-карту для слов в словаре и индексов слов в словаре.

Какой самый быстрый алгоритм хеширования для этого?

Спасибо!

Answer 1

Внизу этой страницы есть раздел Замечание о хэш-функциях с некоторой информацией, которая может оказаться полезной.

Для удобства я просто скопирую здесь несколько ссылок:

• Боб Дженкинс
• Пол Се
• Фаулер / Нолл / Во (FNV)
• MurmurHash

Answer 2

Вы пробовали просто использовать STL hash_map и посмотреть, удовлетворяет ли он вашим потребностям, прежде чем переходить к более сложным задачам?

http://www.sgi.com/tech/stl/hash_map.html

Answer 3

Самая быстрая хеш-функция будет

template <class T>
size_t hash(T key) {
    return 0;
}

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

Answer 4

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

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

Answer 5

Какой у вас вариант использования? radix search tree (trie) может быть более подходящим, чем хеш, если вы отображаете строку в целое число. Преимущество попыток заключается в уменьшении сравнения ключей для ключей переменной длины. (например, строки)

Даже двоичное дерево поиска (например, карта STL) может превосходить контейнер на основе хеша с точки зрения использования памяти и количества сравнений ключей. Хэш более эффективен, только если у вас очень мало коллизий.

Answer 6

boost имеет функцию hash , которую вы можете использовать для своих собственных данных (предопределено для распространенных типов). Это, вероятно, будет работать хорошо и достаточно быстро, если ваши потребности не будут особенными.