(h = key.hashCode()) ^ (h >>> 16);
Jestem głąbem, czytam doca tej metody któryś raz i ciągle tego nie łapie, po co.
hash = key.hashCode() % długośćTablicy . Czy jest to jakaś poprzednia implementacja?
- 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))
- 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/
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