Pytanie Dlaczego tabela mieszania jest zmieniana, podwajając ją?


Sprawdzanie w java i przeglądanie w trybie online przykładów z hashtable wydaje się, że zmiana rozmiaru tabeli odbywa się poprzez jej podwojenie.
Ale większość podręczników twierdzi, że najlepszy rozmiar dla stołu jest liczbą pierwszą.
Moje pytanie brzmi:
Czy podejście podwaja się, ponieważ:

  1. Jest łatwy do wdrożenia, lub
  2. Czy znalezienie liczby pierwszej jest zbyt nieefektywne (ale myślę, że to stwierdzenie następna premiera n+=2 i testowanie pod względem pierwotności za pomocą modulo to O (loglogN), które jest tanie)
  3. Lub to jest moje nieporozumienie i tylko niektóre warianty hashtable wymaga tylko głównego rozmiaru stołu?

Aktualizacja:
Sposób prezentowany w podręcznikach używających liczby pierwszej jest wymagany, aby pewne właściwości działały (np. Kwadratowe sondowanie wymaga tabeli o rozmiarze pierwszym, aby udowodnić, że np. Jeśli tabela nie jest pełnym elementem X zostanie wstawiony).
Link opublikowany jako duplikat prosi ogólnie o zwiększenie o dowolną liczbę, np. 25% lub następny główny, a zaakceptowana odpowiedź stwierdza, że ​​podwoimy się, aby operacja zmiany rozmiaru była "rzadka", abyśmy mogli zagwarantować zamortyzowany czas.
Nie odpowiada to na pytanie o rozmiar stołu, który jest główny i użycie liczby pierwotnej do zmiany rozmiaru, która jest nawet większa niż podwójna. Chodzi o to, aby zachować właściwości rozmiaru pierwotnego, biorąc pod uwagę zmiany rozmiaru narzutów


11
2018-05-21 19:33


pochodzenie


Jest też dobra dyskusja na ten temat stackoverflow.com/a/1147232/1076640. Skoncentruj się szczególnie na części, która obejmuje: "Więc polegasz na funkcji haszującej, aby nie używać nawet mnożników." - yshavit
stackoverflow.com/a/2386132/139010 - Matt Ball
Wyszukiwania, gdy twój stół ma wielkość 2, są szybsze, ponieważ resztę można wykonać za pomocą maski bitowej, ale to raczej mikrooptymalizacja. - David Ehrmann
Tabela mieszania java jest zaimplementowana jako zewnętrzne łańcuchy, więc nie ma problemu. Nie podążam za pytaniem. - amit
Powinniśmy pamiętać, że wbudowane kolekcje Java są w pewnym stopniu oparte na kompromisie: muszą działać dość dobrze, aby uzyskać niezwykle szerokie spektrum wzorców użytkowania. W aplikacji można uniknąć ponownego wdrażania zbiorów przy użyciu algorytmów, które są lepiej dopasowane do konkretnego przypadku użycia, kosztem pogorszenia w innych sytuacjach. Tak właśnie zrobiło wiele osób. - biziclop


Odpowiedzi:


P: Ale większość podręczników twierdzi, że najlepszy rozmiar dla stołu jest liczbą pierwszą.

Odnośnie wielkości:

Co ma pierwszorzędne znaczenie, zależy od wybranego przez Ciebie algorytmu kolizji. Niektóre algorytmy wymagają wielkości tabeli pierwszej (podwójne mieszanie, kwadratowe mieszanie), inne nie, i mogą korzystać z wielkości stołu o wartości 2, ponieważ pozwala to na bardzo tanie operacje modulo. Jednakże, gdy najbliższe "dostępne rozmiary tabel" różnią się 2 razy, użycie pamięci tablicy mieszającej może być niewiarygodne. Tak więc, nawet przy użyciu liniowego mieszania lub oddzielnego łączenia, możesz wybrać brak mocy o 2 rozmiarach. W tym przypadku warto wybrać konkretny rozmiar pierwotny, ponieważ:

  Jeśli wybierzesz wielkość tabeli prime (albo dlatego, że algorytm tego wymaga, albo ponieważ nie jesteś zadowolony z niewiarygodności użycia pamięci implikowanej przez rozmiar potęgi-2), obliczenia na stole (modulo według rozmiaru tabeli) mogą być łączone z mieszaniem. Widzieć ta odpowiedź więcej.

Punkt, w którym wielkość tabeli wynosząca 2 jest niepożądana, gdy rozkład funkcji hash jest zły (z odpowiedzi Neila Coffeya) jest niepraktyczny, ponieważ nawet jeśli masz złą funkcję skrótu, avalanching ją i wciąż używającą wielkości 2-mocy będzie szybsze niż przełączanie na wielkość tabeli pierwszej, ponieważ pojedynczy współczesny podział jest wciąż wolniejszy w nowoczesnych procesorach, a wiele z wielu aplikacji i operacji zmiany, wymaganych przez dobre funkcje lawinowe, np. sol. z MurmurHash3.


P: Szczerze mówiąc, zgubiłem się trochę, jeśli faktycznie polecasz premie, czy nie. Wydaje się, że zależy to od wariantu tablicy hash i jakości funkcji skrótu?

  1. Jakość funkcji skrótu nie ma znaczenia, zawsze możesz "poprawić" funkcję haszującą za pomocą funkcji MurMur3, która jest tańsza niż przejście do wielkości stołu głównego od wielkości stołu o wielkości 2, patrz wyżej.

  2. Polecam wybór rozmiaru pierwotnego, z QHash lub algorytmem mieszania kwadratów (nie są takie same), tylko kiedy potrzebujesz precyzyjna kontrola nad współczynnikiem obciążenia stołu mieszającego i przewidywalnie wysokie rzeczywiste obciążenia. Przy wielkości stołu o wielkości 2, minimalny współczynnik zmiany rozmiaru wynosi 2 i generalnie nie możemy zagwarantować, że tabela mieszania będzie miała faktyczny współczynnik obciążenia wyższy niż 0,5. Zobacz tę odpowiedź.

    W przeciwnym razie, polecam pójść z tabelą skrótów o mocy 2 wielkości z liniowym sondowaniem.

P: Czy podejście podwaja się, ponieważ:
  Jest łatwy do wdrożenia, lub

Zasadniczo w wielu przypadkach tak. Widzieć ta duża odpowiedź dotycząca czynników obciążenia:

Współczynnik obciążenia nie jest istotną częścią struktury danych tabel mieszania - jest to sposób definiowania reguł zachowania dla systemu dymamicznego (rosnąca / malejąca tabela mieszania jest systemem dynamicznym).

  Ponadto, moim zdaniem, w 95% nowoczesnych przypadków tablic asocjacyjnych w ten sposób uprościło się, systemy dynamiczne zachowują się suboptymalnie.

Co jest podwojenie? To tylko najprostsza strategia zmiany rozmiaru. Strategia może być dowolnie złożona, optymalnie wykorzystując Twoje przypadki użycia. Może uwzględniać obecny rozmiar tablicy hash, intensywność wzrostu (ile operacji wykonano od poprzedniej zmiany rozmiaru), itp. Nikt nie zabrania implementacji takiej niestandardowej logiki zmiany rozmiaru.

P: Znalezienie liczby pierwszej jest zbyt nieefektywne (ale myślę, że znalezienie następnej liczby głównej przekraczającej n + = 2 i testowanie pod względem pierwotności za pomocą modulo to O (loglogN), która jest tania)

Dobrą praktyką jest wstępne obliczanie niektórych podzbiorów głównych tabel mieszających, aby można było wybierać między nimi za pomocą wyszukiwania binarnego w środowisku wykonawczym. Widzieć lista podwójnych pojemności hasłowych i wyjaśnienia, Pojemności QHash. Lub nawet za pomocą bezpośrednie wyszukiwanie, to bardzo szybko.

P: Czy to jest moje nieporozumienie i tylko niektóre warianty hashtable wymagają tylko wielkości stołu głównego?

Tak, tylko niektóre typy wymagają, patrz wyżej.


6
2018-05-22 02:00



Dziękuję za Twoją odpowiedź. Przede wszystkim co robi when closest "available table sizes" differ in 2 times memory usage of hash table might be unreliable oznaczać? - Jim
Szczerze mówiąc, zgubiłem się trochę, jeśli faktycznie polecasz premie, czy nie. Wydaje się, że zależy to od wariantu tablicy hash i jakość funkcji skrótu? - Jim
@Jim oznacza to samo co "z wielkością stołu o wielkości 2, minimalny współczynnik zmiany rozmiaru wynosi 2, i ogólnie nie możemy zagwarantować, że tabela mieszania będzie miała faktyczny współczynnik obciążenia wyższy niż 0.5." - leventov
@ Jim dla rekomendacji - patrz aktualizacja odpowiedzi. - leventov
I recommend choosing prime size, with QHash or quadratic hash algorithm (aren't same), only when you need precise control over hash table load factor and predictably high actual loads ale dla kwadratowej wersji tabela obciążenia powinna być mniejsza niż 50%, aby była skuteczna - Jim


Java HashMap (java.util.HashMap) kolizje kubków łańcuchów na liście połączonej (lub drzewo [jak w JDK8] w zależności od rozmiaru i przepełnienia pojemników).

W związku z tym teorie dotyczące funkcji wtórnego sondowania nie mają zastosowania. Wygląda na to, że komunikat "używaj wielkości liczb pierwszych dla tabel mieszających" oddzielił się od okoliczności, które stosuje z biegiem lat ...

Korzystanie z uprawnień dwojakich ma tę zaletę (jak zauważono w innych odpowiedziach), że zmniejszenie wartości hash do wpisu w tabeli można osiągnąć za pomocą maski bitowej. Podział całkowity jest relatywnie drogi iw sytuacjach wysokiej wydajności może to pomóc.

Mam zamiar zaobserwować, że "redystrybucja łańcuchów zderzeniowych przy ponownym szyciu jest chwytem do stołów, które są potęgą dwóch potęg dwóch".

Zauważ, że przy użyciu mocy dwóch ponownych prób do dwukrotnego rozmiaru "dzieli" każde wiadro pomiędzy dwoma zasobnikami na podstawie "następnego" fragmentu kodu skrótu. To znaczy, jeśli tablica hash-table ma 256 segmentów, a zatem użycie najniższego 8 bitów ponownego łączenia wartości mieszającej dzieli każdy łańcuch kolizji na podstawie 9-tego bitu i albo pozostaje w tym samym segmencie B (9 bit to 0) lub przechodzi do wiadro B + 256 (9 bit to 1). Takie dzielenie może zachować / wykorzystać podejście do przenoszenia łyżek. Na przykład, java.util.HashMap utrzymuje małe segmenty posortowane w kolejności odwrotnej do wstawienia, a następnie dzieli je na dwie podstruktury przestrzegające tej kolejności. Utrzymuje duże wiadra w drzewie binarnym posortowane według kodu hash i podobnie dzieli drzewo, aby zachować tę kolejność.

NB: Te sztuczki nie zostały wdrożone do czasu JDK8.

(Jestem pewny) Java.util.HashMap tylko rozmiary w górę (nigdy w dół). Ale są podobne wydajności do zmniejszenia o połowę tabeli mieszania, jako podwojenie jej.

Jedną z "wad" tej strategii jest to Object implementatorzy nie są jednoznacznie zobowiązani do upewnienia się, że bity niskiego rzędu z skrótów są dobrze rozmieszczone. Całkowicie poprawny kod hash może być dobrze dystrybuowany ogólnie, ale słabo dystrybuowany w swoich niewielkich bitach. Tak więc obiekt spełniający generalny kontrakt dla hashCode() może nadal tankować, gdy faktycznie jest używany w HashMap! Java.util.HashMap łagodzi to przez zastosowanie dodatkowego skrótu "spread" na dostarczone hashCode() realizacja. To "rozprzestrzenianie" jest naprawdę szybkie (xors 16 wysokich bitów z niskim poziomem).

Implementery obiektów powinny być świadome (jeśli nie), że odchylenie w ich haśle (lub jego brak) może mieć znaczący wpływ na wydajność struktur danych za pomocą skrótów.

Dla zapisu oparłem tę analizę na tej kopii źródła:

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java


3
2018-05-22 13:37



Bardzo interesująca analiza. Ale JDK zmienia rozmiar tabeli poprzez podwojenie. I zakładam, że wybrali zewnętrzny kanał, ponieważ jest on łatwy do wdrożenia. Ale zastanawiałem się, czy nie można użyć doskonałego stołu z tymi samymi "sztuczkami", o których wspomniałeś - Jim
Także o zmniejszeniu o połowę tabeli mieszania, o której wspomniałeś. Nigdy nie czytałem żadnego podręcznika, nawet sugerującego tę technikę. Czy to faktycznie jest używane w jakiejkolwiek implementacji? - Jim
@Jim Tak, zmienia rozmiar poprzez podwojenie. "Podstęp" polegał na uproszczeniu podwojenia, gdy zdał sobie sprawę, że wiadra zderzeniowe są starannie pomniejszone o połowę. Przed JDK8 kod wyraźnie nie używa że sztuczka. Przekroczenie jest często pomijaną operacją. Jednak w przypadku złożonych lub długotrwałych aplikacji może być konieczne. Zauważyłem Java.util.HashMap nie przejmuje się. Czy zauważyłeś, jak serwery korzystają z okresowego ponownego uruchamiania? Zanieczyszczenia, takie jak nieumieszczanie klas rozładowczych i wewnętrzne "bufory", ale coraz mniejsze, to powód, dla którego system, który nigdy nie wycieknie, niepotrzebnie trzyma bezczynne zasoby. - Persixty
Nie jestem pewien, czy to rozwiąże twój punkt widzenia. Nawet w C ++, gdy zwolnisz pamięć, nie przechodzi do systemu do ponownego użycia, ale jest zarezerwowany do ponownego użycia przez ten sam proces w przyszłym żądaniu. W rezultacie pamięć o procesie jako całości nigdy nie spada. Jest to bardzo zauważalne w przypadku aplikacji takich jak firefox lub chrome, które były otwarte przez długi czas. W końcu zużywają większość twojego systemu. Nie jestem więc pewien, czy próba zmniejszenia o połowę tabeli pozwoli nam zaoszczędzić na ponownym uruchomieniu okresu, który prawidłowo wskazujesz. Czy mam sens? - Jim
@ Jim. Standard C ++ nie przewiduje takiej klauzuli. Jest to dyskusja na temat tego, co dzieje się pod maską new i delete. W Visual Studio na przykład dzwonią do malloc(.) i free(). Tutaj to zauważysz free(.) może skutkować przekazaniem zasobów. msdn.microsoft.com/en-us/library/we1whae7.aspx. Byłaby to bardzo zła platforma / czas pracy nigdy oddał zasoby. Zobacz system Windows 95/98, aby udowodnić, o co chodzi! Nie zrobili tego, ale byli tak samo uważani za "najgorsze systemy operacyjne." - Persixty