Efektywna mapa Hash Użyj

Question

Jakie jest bardziej efektywne podejście do używania hashmap?

A) Używaj wielu mniejszych hashmaps lub

B) przechowywać wszystkie obiekty w jeden olbrzymi hashmap?

(Załóżmy, że algorytm mieszania dla klawiszy jest dość wydajny, w wyniku kilku kolizji)

Wyjaśnienie: Wariant B zakłada segregacji według klucza podstawowego - czyli brak dodatkowych odnośników jest konieczne do ustalenia, które rzeczywista HashMap używać . (Na przykład, jeśli klawisze wyszukiwania są alfanumeryczne, Hashmap 1 przechowuje A, Hashmap 2 przechowuje B i tak dalej.)

Answer 1

Zdecydowanie B. Zaletą tabel mieszania jest to, że średnia liczba porównań na wyszukiwanie jest niezależna wielkości.

Jeśli podzielisz mapę na N mniejszych haczyków, będziesz musiał przeszukać połowę z nich dla każdego wyszukiwania. Jeśli mniejsza mahm ma taki sam współczynnik obciążenia, jaki miałaby większa mapa, zwiększysz całkowitą liczbę porównań o współczynnik około N/2.

A jeśli mniejsza mahmaps ma mniejszy współczynnik obciążenia, marnujesz pamięć.

Wszystko to zakłada, że ​​rozsyłasz klucze losowo między mniejszymi hashmapami. Jeśli rozpowszechniasz je zgodnie z pewną funkcją klucza (np. Prefiks ciągu), to utworzona przez ciebie jest trie, która jest wydajna dla niektórych aplikacji (np. Autouzupełnianie w formularzach internetowych).

Answer 2

Czy te mapy są używane w logicznie różnych miejscach? Na przykład, nie miałbym jednej mapy zawierającej użytkowników, wyniki zapytań z pamięci podręcznej, rejestratory itp., Tylko dlatego, że wiesz, że klucze się nie kolidują. Ja jednak nie podzieliłbym jednej mapy na wiele map.

Zachowaj jedną hashmap dla każdego mapowania logicznego z klucza na wartość.

Answer 3

Oprócz odpowiedzi Jona, mogą istnieć praktyczne powody, dla których chcesz zachować oddzielne tabele mieszania.

Jeśli masz oddzielne tabele dla różnych odwzorowań, możesz "wyczyścić" każde z odwzorowań niezależnie; na przykład przez wywołanie "wyczyść" lub pozbycie się odniesienia do odpowiedniej tabeli.

Jeśli oddzielne tabele zawierają odwzorowania do zapisów w pamięci podręcznej, można użyć różnych strategii, aby "zestarzeć" odpowiednie wpisy.

Jeśli aplikacja jest wielowątkowa, użycie oddzielnych tabel może zmniejszyć rywalizację o blokady i może (w przypadku niektórych architektur procesorów) zwiększyć współczynniki trafień pamięci podręcznej pamięci procesora.