Java: liczba "pierwsza" czy "potęga dwóch" jako rozmiar Hashmapy?
Wiele książek i samouczków mówi, że rozmiar tabeli hash musi być prime, aby równomiernie rozłożyć klucze we wszystkich wiadrach. Ale HashMap Java zawsze używa rozmiaru, który jest potęgą dwóch. Nie powinno używać prime ' a? Co jest lepsze, "prime" lub "power of two"jako rozmiar tabeli hash?
5 answers
Użycie mocy dwóch skutecznie maskuje górne bity kodu hashowego. Tak więc słaba jakość funkcji skrótu może działać szczególnie źle w tym scenariuszu.
Java HashMap łagodzi to, nie ufając implementacji hashCode() obiektu i stosując drugi poziom hashowania do jego wyniku :
Stosuje dodatkową funkcję hash do danego hashCode, która chroni przed słabej jakości funkcjami hash. Jest to krytyczne, ponieważ HashMap używa mocy dwóch tabele długości skrótów, które w przeciwnym razie napotykają kolizje dla hashcodów, które nie różnią się niższymi bitami.
Jeśli masz dobrą funkcję hashową lub robisz coś podobnego do tego, co robi HashMap, nie ma znaczenia, czy używasz liczb pierwszych itp. jako rozmiaru tabeli.
Jeśli z drugiej strony funkcja hash jest nieznanej lub słabej jakości, użycie liczby pierwszej byłoby bezpieczniejsze. To jednak sprawi, że dynamiczne tabele będą trudniejsze do wdrożenia, ponieważ nagle musisz być w stanie produkować liczby pierwsze, zamiast po prostu pomnażać rozmiar przez Stały współczynnik.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-03-15 16:42:31
Standardowa implementacja HashMap posiada metodę hash, która powtarza hashcode Twojego obiektu, aby uniknąć tego pułapki. Komentarz przed Metoda hash() brzmi:
/**
* Retrieve object hash code and applies a supplemental hash function to the
* result hash, which defends against poor quality hash functions. This is
* critical because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-03-15 16:24:43
Jedynym sposobem, aby dowiedzieć się, która jest lepsza między Prime a power-of-two, jest porównanie jej.
Wiele lat temu, pisząc asembler, którego wydajność silnie zależała od symbolu talbe lookup, testowałem to przy użyciu dużego bloku wygenerowanych identyfikatorów. Nawet z naiwnym mapowaniem stwierdziłem, że moc dwóch, zgodnie z oczekiwaniami, miała mniej równomiernego rozkładu i dłuższe łańcuchy niż podobna liczba pierwszych wiader. Nadal działał szybciej, ze względu na szybkość wybierania łyżki bitem maskowanie.
Mocno podejrzewam Javę.Programiści utila nie uciekaliby się do dodatkowego hashowania i power-of-two bez porównywania go z użyciem pierwszej liczby bucketów. Jest to bardzo oczywiste podczas projektowania zaszyfrowanej struktury danych.
Z tego powodu jestem pewien, że rozmiar rehash i power-of-two daje lepszą wydajność dla typowych map hashowych Javy niż pierwsza liczba bucketów.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-03-15 16:36:30
Z punktu widzenia wydajności / czasu obliczeń moc dwóch rozmiarów może być obliczona za pomocą maskowania bitowego, które jest szybsze niż dzielenie liczb całkowitych, które byłoby wymagane w przeciwnym razie.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-03-15 16:27:47
Prawdopodobnie powinieneś użyć tabel hashowych o rozmiarze pierwszym, jeśli używasz sondy kwadratowej do rozwiązywania kolizji. Jeśli masz tabelę wielkości pierwszej, sonda kwadratowa trafi połowę wpisów, mniej, jeśli nie jest prime. Możesz więc nie znaleźć odpowiedniego miejsca do przechowywania wpisów, nawet jeśli twoja tabela hash jest mniej niż w połowie pełna. Ponieważ mapy hashowe Javy nie używają sondy kwadratowej, nie ma potrzeby używania primes jako rozmiaru.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-04-08 14:41:22