Хештаблицы, можно ли мешать open addressing и chaining(решено)?

Question

[Catmengi]

Я уже пытался делать хеш таблицу, она даже работала нормально, но с одной загвоздкой, в каждом бакете хеш таблицы был массив указателей на коллизии ключей, а этот массив был нужен чтобы решать коллизии между хешами. Можно ли использовать такой подход но если бакет в который мы попали уже полон просто использовать метод open addressing для поиска следующего пустого бакета и потом в начальном в который мы попали бакете хранить указатель на ячейку которую мы нашли.Сможет ли такой подход эффективнее использовать память и быть достаточно быстрым?(старая хештаблица ела ±3 Гб памяти на 15милионнов ключей)

Comments

[Wataru]

Как у вас 75млн ключей жрут 3 гб? Какой у вас там размер таблицы-то? Сам ключи со всеми указателями едва 200мб сожрут.

[mayton2019]

А ко всем ключам идет доступ одинаково? Или есть горячие и холодные ключи?

[Catmengi]

mayton2019, идёт ко всем одинаково

[mayton2019]

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

Пересмотри задание. Быть может тебе надо проверять только contains ключей, тогда посмотри как работает
фильтр Блума. Или если у тебя длинные строковые ключи - то посмотри в сторону Trie (RadixTree).

Answer 1

[Wataru]

Мешать можно. Особо память это не сократит, а реализацию сильно усложнит.