Dlaczego hashtable przechowywania wartości hash klucza w tabeli w java

Question

ja jechałem poprzez wdrożenie Java metody put na hashtable i natknąłem się na to:

// Makes sure the key is not already in the hashtable. 
    Entry tab[] = table; 
    int hash = key.hashCode(); 
    int index = (hash & 0x7FFFFFFF) % tab.length; 
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 
     if ((e.hash == hash) && e.key.equals(key)) { 
      V old = e.value; 
      e.value = value; 
      return old; 
     } 
    } 

Choć rozumiem, że kluczowym jest wymagany do sprawdzenia kolizji, dlaczego Java przechowuje wartość mieszania klucza, a także sprawdza to?

Answer 1

Ponieważ ta sama łyżka (tab) może przechowywać przedmioty o różnych hasłach ze względu na operację % tab.length. Sprawdzanie hash w pierwszej kolejności jest prawdopodobnie pewną optymalizacją wydajności, aby uniknąć wywoływania equals(), jeśli skróty są różne.

Aby umieścić to w przykładzie: Załóżmy, że masz dwa złożone obiekty o kosztownej metodzie equals(). Jeden obiekt ma wartość mieszania równą 1, podczas gdy drugi obiekt ma wartość mieszania równą 32. Jeśli umieścisz oba obiekty w tabeli mieszania mającej 31 segmentów, staną one w tym samym wiadrze (tab). Dodając drugi (inny obiekt), upewnij się, że nie ma go jeszcze w tabeli. Możesz natychmiast użyć equals(), ale może to być wolniejsze. Zamiast tego najpierw porównuj hasze, unikając kosztownych equals(), jeśli nie jest to konieczne. W tym przykładzie skróty są różne (pomimo tego, że znajdują się w tym samym segmencie), więc equals() nie jest konieczne.

Answer 2

Umożliwia szybszy dostęp, ponieważ wartość skrótu nie musi być obliczana dla każdego dostępu. Jest to ważne nie tylko dla jawnych wyszukiwań (gdzie hash jest sprawdzany przed wykonaniem equals), ale także dla rehash.