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

Question

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

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

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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