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

Question

Каков более эффективный подход к использованию hashmaps?

А) Использование нескольких меньших HashMaps или

В) хранить все объекты в один гигантский HashMap?

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

ПОЯСНЕНИЯ: Вариант B подразумевает разделение по первичному ключу - т.е. никакого дополнительного поиска не требуется, чтобы определить, какие фактические HashMap использовать , (Например, если ключи поиска являются буквенно-цифровыми, в Hashmap 1 хранятся хранилища A, Hashmap 2 и т. Д.)

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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