Jak działa funkcja hash w HashMapie.

Jak działa funkcja hash w HashMapie.
GigaBajt
  • Rejestracja:ponad 9 lat
  • Ostatnio:ponad 3 lata
  • Postów:37
0
  1. Czy mógłby mi ktoś w miarę prostym językiem wytłumaczyć po co nam te przesunięcia bitowe i XOR w funkcji HashMap.hash() ?
Kopiuj
(h = key.hashCode()) ^ (h >>> 16);

Jestem głąbem, czytam doca tej metody któryś raz i ciągle tego nie łapie, po co.

  1. Dosyć często na necie, gdy są artyukuły o hashmapie, przewija się taka implementacja tej metody: hash = key.hashCode() % długośćTablicy . Czy jest to jakaś poprzednia implementacja?
SL
  • Rejestracja:około 7 lat
  • Ostatnio:około 6 godzin
  • Postów:901
0
  1. Czy mógłby mi ktoś w miarę prostym językiem wytłumaczyć po co nam te przesunięcia bitowe i XOR w funkcji HashMap.hash() ?

Co do XORa: https://stackoverflow.com/questions/5889238/why-is-xor-the-default-way-to-combine-hashes .
Jeśli chodzi o przesunięcie bitowe, to jego zadaniem jest wzięcie pod uwagę kolejności argumentów. Pamietaj, że XOR jest przemienny więc XOR(hash(1), hash(2) == XOR(hash(2), hash(1))

  1. Dosyć często na necie, gdy są artyukuły o hashmapie, przewija się taka implementacja tej metody: hash = key.hashCode() % długośćTablicy . Czy jest to jakaś poprzednia implementacja?

To inny rodzaj hasha. Pierwszy o którym wspominałeś służy do zmapowania dowolnej wartości do skróconej wartości, której rozkład powinien być jak najbardziej równomierny. % długośćTablicy służy do dostosowania policznego hashu do długości twojej hashmapy. Innym algorytmem jest np. fibonacci hashing, więcej o tym algorytmie a także o różnicy pomiędzy tymi dwoma hashami możesz poczytać w tym artykule: https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/

gk1982
  • Rejestracja:prawie 14 lat
  • Ostatnio:około 2 miesiące
  • Lokalizacja:Łódź
  • Postów:541
0

Don't give up learning JavaScript!
It is enjoyable to make things visible which are invisible.
Każdy programista przybywający z innego miasta jest fachowcem.
Anyone who stops learning is old, whether at twenty or eighty.
Anyone who keeps learning stays young.
The greatest thing in life is to keep your mind young.
AK
  • Rejestracja:prawie 7 lat
  • Ostatnio:około 2 miesiące
  • Postów:3561
1

Nie jesteś zobowiązany używać takiej czy innej arytmetyki. Możesz zaproponować swoją, byle była dobra

Proponuję poszukać informacji o matematyce stojącej za hashami.
Odwzorowując wartość V na hash (klucz) K
V -> K

ma być powtarzalne, tzn wielokrotne poszukiwanie hasha z V ma dawać tą samą wartość
K nie musi być unikalne (trudno, żeby było jak K jest krótsze od V)
ma być jak najlepiej rozrzucone, tzn mała zmiana V ma dać mocno różniący się K
rozsadek mówi, że powinno być wydajne, tzn nie półgodzinne algorytmy, a sprawdzone triki liczbowe

PS. warto dobrze przetrawić w głowie DLACZEGO hash, wtedy się lepiej rozumie JAK.

Piszę z głowy, pewnie znajdziesz to lepiej wyłożone.
Jest rozważane w każdej książce do Javy "na drugi etap", Eckel, Blosh, Horstman dla zaawansowanych


Bo C to najlepszy język, każdy uczeń ci to powie
edytowany 2x, ostatnio: AnyKtokolwiek

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.