Dlaczego program HashMap.put zarówno porównuje hasze, jak i testuje równość?

Question

Analizuję kod źródłowy HashMap w Javie i otrzymuję pytanie dotyczące metody put.

Poniżej jest metoda put w JDK1.6:

public V put(K key, V value) { 
    if (key == null) 
     return putForNullKey(value); 
    int hash = hash(key.hashCode()); 
    int i = indexFor(hash, table.length); 
    for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
     Object k; 
     if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
      V oldValue = e.value; 
      e.value = value; 
      e.recordAccess(this); 
      return oldValue; 
     } 
    } 

    modCount++; 
    addEntry(hash, key, value, i); 
    return null; 
} 

mogę się mylić o if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

Dlaczego warunek ten sposób?

Ponieważ w super klasy Java Object istnieje contract z hashCode i equals: metoda

Jeśli dwa obiekty są równe według równych (Object), a następnie wywołanie metody hashCode na każdym z dwóch obiekty muszą generować ten sam wynik całkowity.

Tak więc key.equals(k) implikuje key.hashCode() == k.hashCode().

hash() jest poniżej:

static int hash(int h) { 
    // This function ensures that hashCodes that differ only by 
    // constant multiples at each bit position have a bounded 
    // number of collisions (approximately 8 at default load factor). 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
} 

key.hashCode() == k.hashCode() zatem implikuje e.hash == hash.

Dlaczego więc nie jest taki stan jak if ((k = e.key) == key || key.equals(k))?

Answer 1

To jest po prostu unikanie wywołanie metody kiedy można: Jeśli hash (co nie hashCode() jest to mapa własnego skrótu) różni się od haszyszu przez wpisu za to wie to nie trzeba zadzwonić equals na wszystko. Po prostu trochę optymalizuję.

Answer 2

To tylko optymalizacja: porównywanie dwóch liczb całkowitych jest szybsze niż wywoływanie equals().

Jeśli oba kody skrótu różnią się, wówczas na podstawie umowy equals i hashCode mapa wie, że istniejący klucz nie jest równy podanemu kluczowi i może przejść szybciej do następnego.

Answer 3

wartość zmiennej "hash" może być różna od kodu klucza. Zmienna "hash" jest wynikiem wywołania metody "hash (key.hashCode())". Dlatego wymagane jest porównanie wartości mieszania, a także równości kluczy.