Хеш-таблицы 2/2.
5. Пробинг при открытой адресации.
Пробинг -- то, как вы двигаетесь по таблице в поиске свободного места. Очевидно можно линейный:
offset[i] = i или i*k. Можно квадратический: offset[i] = i*i или даже alpha*i + beta*i*i. Или double hashing: offset[i] = i*hash2(key). Или cuckoo hashing (ну придумали конечно): для любого ключа проверяем две точки от двух хеш-функций; если есть место, вставляем, иначе выбираем одного из этих двух оккупантов и выселяем его, а на его место наш элемент; аналогично делаем с выселенным элементом; если такое повторяется некоторое количество раз, меняем хеш-функцию и рехеш. Прикольно, что такой приём гарантирует O(1) на поиск. 6. Доп. требования.
Иногда нужно хранить порядок вставки. Тогда давайте рядом хранить двусвязный лист, а в каждом бакете хранить итератор на начало подцепочки этого бакета в листе и размер подцепочки. Ещё кстати и перебор всех элементов за их количество.
А может ещё вы хотите на каком-то интервале читать значения, тогда вам не хеш-таблица нужна, но об этом попозже : )
7. И немного читов.
-- можно как в LRU-кеше при закрытой адресации найденный где-то в глубине листа элемент перемещать в самое начало, чтобы в следующий раз его поиск прошёл быстрее. В открытой адресации наверное тоже можно посвапать аккуратно с удалённым элементом например, но звучит как что-то, где легко споткнуться.
-- хешировать можно не просто пришедший элемент, а что угодно. Можете хешировать хеш от хеша от хеша. Или первые 8 байт объекта. Или для чисел сначала 228 добавить. Короче вертеть как хочешь, абы хорошо было.
-- вместо листа/вектора при закрытой адресации можете хранить что-то другое. В java например с какого-то момента лист превращается в bst.
[1]. Hash map analysis.
[2]. Extendible hashing.
[3]. Я написал самую быструю хеш-таблицу.
[4]. Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step [видео].
[5]. О хеш-таблицах в Clickhouse [видео].