Perché un negozio HashTable il valore hash della chiave nella tabella in java

Question

stavo attraversando implementazione di Java del metodo put per una tabella hash e sono imbattuto in questo:

// 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; 
     } 
    } 

pur comprendendo che una chiave è richiesto per verificare la presenza di collisioni, perché Java sta memorizzando il valore hash della chiave e anche controllandola?

Answer 1

Poiché lo stesso bucket (tab) può contenere elementi con hash diversi a causa dell'operazione % tab.length. Il controllo dell'hash prima è probabilmente un po 'di ottimizzazione delle prestazioni per evitare di chiamare equals() se gli hash sono diversi.

Per mettere questo in un esempio: si supponga di avere due oggetti complessi con il costoso metodo equals(). Un oggetto ha hash uguale a 1 mentre l'altro oggetto ha hash di 32. Se si mettono entrambi gli oggetti in una tabella hash con 31 bucket, finiranno nello stesso bucket (tab). Quando aggiungi un secondo (oggetto diverso) devi assicurarti che non sia ancora nella tabella. È possibile utilizzare immediatamente equals(), ma potrebbe essere più lento. Invece prima confronta gli hash, evitando costosi equals() se non necessario. In questo esempio gli hash sono diversi (nonostante siano nello stesso bucket) quindi non è necessario equals().

Answer 2

Rende l'accesso più veloce, poiché il valore hash non deve essere ricalcolato per ogni accesso. Questo è importante non solo per le ricerche esplicite (dove l'hash è controllato prima di fare equals) ma anche per il rehash.