Функция по умолчанию - это std :: hash. Интересно, есть ли лучшие хэш-функции для экономии вычислительного времени? для целых ключей, а также для строковых ключей.Существуют ли более быстрые хэш-функции для unordered_map/set в C++?
Я попробовал City Hash из Google как для целых, так и для строковых ключей, но его производительность немного хуже, чем std :: hash.
Вам нужно объяснить «лучше» в каком смысле? Самая быстрая хеш-функция будет просто использовать значение, но это бесполезно. Более конкретный ответ будет зависеть от ваших ограничений памяти и от того, какие вероятности столкновения вы готовы принять.
отметить также, что встроенные хэш-функции строятся по-разному для разных типов, и в результате, я ожидаю, что хэш-функцию для int и string к уже оптимизированными в общем смысле для временной сложности и вероятности столкновения.
Моя цель - уменьшить общий процессор. Итак, я полагаю, что (1) сам расчет хэша выполняется быстро; (2) столкновение низкое. Не уверен, что я на правильном пути. – SuperBald
@superbald: вопрос в том, почему вы думаете, что можете сделать лучше? Стандартные функции библиотеки были написаны чрезвычайно умными программистами, целью которых является создание лучших библиотечных функций. Если вы можете сделать лучше, возможно, потому, что вы знаете что-то о своих данных, которые могут быть использованы ro, повышают производительность для этого конкретного набора данных. Но вы не указали, что может сделать ваши ключи более легкими для хэша. Стандартная реализация библиотеки должна хорошо работать с широким спектром данных, и если ничто не делает вас особенным, оно будет хорошо работать и с вашим. – rici
Быть в STL не означает, что это лучшее. например, Google open source hash map и tree map, которые часто лучше, чем std. Я не уверен в хэш-функции. Итак, задал этот вопрос. – SuperBald
std :: hash функции уже хороши в производительности. Я думаю, вам следует попробовать хеш-функции с открытым исходным кодом.
Проверьте это https://github.com/Cyan4973/xxHash. Я процитирую его описание: «xxHash - это чрезвычайно быстрый алгоритм хэширования, работающий с ограничениями скорости ОЗУ. Он успешно завершает набор тестов SMHasher, который оценивает характеристики хеш-функций, связанных с столкновением, дисперсией и случайностью. Код очень переносимый, а хэши идентичны по все платформы (маленькие/большие endian) ».
Также эта тема из другого вопроса на этом сайте: Fast Cross-Platform C/C++ Hashing Library. Известно, что FNV, Jenkins и MurmurHash работают быстро.
Вообще говоря, вы можете написать более быструю хэш-функцию, если знаете что-то конкретное о данных, которые вы хешируете. Как глупый пример, если вы имеете дело только с двумя целыми значениями 17 и 535, вы можете сделать их равными 0 и 1 тривиально, и это будет быстрее, чем любая хеш-функция, которая имеет дело с полным диапазоном целочисленных значений. Итак, что особенного в отношении значений, которые вы хешируете? –
Закрытие вопроса, если проблема решена, всегда является хорошей идеей :) –