Эффективное использование Hashmap

Question

Каков более эффективный подход для использования хэш-карт?

A) Используйте несколько меньших хэш-карт или

B) хранить все объекты в одной гигантской хэш-карте?

(Предположим, что алгоритм хеширования для ключей достаточно эффективен, что приводит к нескольким коллизиям)

УТОЧНЕНИЕ: Опция B подразумевает сегрегацию по первичному ключу, т. е. не требуется никакого дополнительного поиска, чтобы определить, какую фактическую хэш-карту использовать. (Например, если ключи поиска являются буквенно-цифровыми, Hashmap 1 хранит A, Hashmap 2 хранит B и т. Д.)

Answer 1

Определенно B. Преимущество хеш-таблиц состоит в том, что среднее число сравнений на поиск не зависит от размера.

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

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

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

Answer 2

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

Сохраняйте одну хэш-карту для каждого логического отображения от ключа к значению.

Answer 3

В дополнение к ответу @ Jon, могут быть практические причины, по которым вы хотите поддерживать отдельные хеш-таблицы.

Если у вас есть отдельные таблицы для разных сопоставлений, вы можете «очистить» каждое сопоставление независимо; например вызвав 'clear' или избавившись от ссылки на соответствующую таблицу.

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

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