Хеш-таблицы 1/2.
1. load factor.
Часто говорят, что важно следить за ним. Ведутся жоские споры (у агрошкольников) о том, какие значения норм, а какие нет. В умных книжках часто пишут, что норм 0.5-0.7. В жизни вам может зайти и 0.99, и может больше единицы, и в районе 0.005. Важно понимать, что важен не сам LF, а средняя глубина поиска. Потому что у вас есть коллизии, которые в одном бакете делают 10 элементов, когда вся таблица на 100. Вроде LF 0.1, а работает медленно. И есть удаления. Которые например при открытой адресации просто помечают элементы удалёнными, не ускоряя поиск. Короче за этим надо следить (в случае открытой адресации видимо вас ждут k костылей, в случае закрытой можно считать LF как максимальное кол-во элементов в бакете делить на размер таблицы).
2. Хеш-функция.
Легко можно выбрать хеш-функцию, посмотрев на её бенчмарки (которые где-то там делали авторы и она всё и вся разносит). Но очевидно, что не будет понятно норм/нет, пока вы не померяете на ваших данных. Ну это ладно. Это известный тезис.
А вот какую выбрать? Может я коллизий поменьше хочу. Тогда может что-то из sha-2 или md5? У них, говорят, коллизий мало. Вон они по 128+ бит хеши выдают. ... А ключи же у нас в районе 64х. Получается надо обрезать. И тут уже ничего не понятно, норм оно будет или нет. Ещё и считается долго. Долго это плохо. Надо помнить, что хеш-функция это на каждую операцию. Потому может лучше "плохо" и быстро с помощью crc32, DJB или fnv (главное чтобы не LoseLose). Хотя можно что-то среднее: SuperFastHash, Murmur, CityHash или Robin-hood (или Hopscotch). Вообще про тему скорости хеш-функций можно вспомнить SMHasher, который считает, сколько функция умеет хешировать в секунду и ещё какие-то характеристики. Но тут тоже стоит помнить, что неважно, сколько она хеширует в секунду, если вы собираетесь её юзать для восьмисимвольных строк (надо мерять).
Бывают ли идеальные хеши? Да! Но надо бы знать ключи заранее и делать предпосчёт, зато юзается быстро и без коллизий :) Тут можно взглянуть на gperf и cmph.
Можно вообще выбрать какое-то семейство функций, и время от времени брать функцию из него.
3. Размер.
Можно зафиксировать вашу таблицу на всю жизнь (и жить с открытой адресацией):
std::pair<K, V> data[1024];Но что-то подсказывает, что такого хватит ненадолго (хотя мб и хватит). Стандартный путь это как вектор (просто элементов для открытой адресации или например листов для закрытой): реаллокация в k раз, чтобы LF получше стал. Как выбирать k смотрите два поста назад. Можно размеры только степенями двойки. Или можно делать статику снаружи и динамику внутри:
std::vector<std::pair<K, V>> data[1024];Может быть полезно в случае параллельной таблички или если вы локальность цепочки при закрытой адресации хотите.
4. Ключи.
Иногда нужно хранить какую-то мету, само значение (для сравнений каких-нибудь) или значение хеша. В зависимости от того, насколько много занимает ваша структурка, можно выбирать, хранить например всё в одном массивчике или может ключи/значения отдельно, чтобы в кеши хорошо попадало что надо. Тут конечно всё зависит от вашего паттерна доступа.
Кстати забавно, что если объект жирный, можно попробовать хранить первые k байт его представления и сравнивать их. Или можно вообще не сравнивать изначальные ключи с одинаковыми значениями хеша, если вы уверены в хеш-функции или готовы иногда ошибаться.