unicità del codice hash

Question

È possibile che due istanze di Object abbiano lo stesso codice hash?

In teoria l'hashcode di un oggetto deriva dal suo indirizzo di memoria, quindi tutti gli hashcode dovrebbero essere univoci, ma cosa succede se gli oggetti vengono spostati durante il GC?

Answer 1

Data una ragionevole raccolta di oggetti, è molto probabile avere due con lo stesso codice hash. Nel migliore dei casi diventa il problema del compleanno, con uno scontro con decine di migliaia di oggetti. In pratica gli oggetti sono creati con un pool relativamente piccolo di probabili codici hash e le collisioni possono facilmente verificarsi con solo migliaia di oggetti.

L'utilizzo dell'indirizzo di memoria è solo un modo per ottenere un numero leggermente casuale. L'origine Sun JDK ha un interruttore per abilitare l'uso di un generatore di numeri casuali sicuro o una costante. Credo che IBM (usato per?) Usasse un generatore di numeri casuali veloce, ma non era affatto sicuro. La menzione nei documenti di indirizzo di memoria sembra essere di natura storica (circa dieci anni fa non era raro avere maniglie di oggetti con posizioni fisse).

Ecco alcuni codice che ho scritto qualche anno fa per dimostrare scontri:

class HashClash { 
    public static void main(String[] args) { 
     final Object obj = new Object(); 
     final int target = obj.hashCode(); 
     Object clash; 
     long ct = 0; 
     do { 
      clash = new Object(); 
      ++ct; 
     } while (clash.hashCode() != target && ct<10L*1000*1000*1000L); 
     if (clash.hashCode() == target) { 
      System.out.println(ct+": "+obj+" - "+clash); 
     } else { 
      System.out.println("No clashes found"); 
     } 
    } 
} 

RFE per chiarire i documenti, perché questo viene su troppo di frequente: CR 6321873

Answer 2

Penso che lo docs for object's hashCode method indichi la risposta.

"Per quanto è ragionevolmente pratico, il metodo hashCode definito dalla classe Object non ritorno interi distinti per oggetti distinti. (Questo è tipicamente attuato convertendo l'indirizzo interno dell'oggetto in un non intero, ma questa tecnica implementazione è richiesto dal JavaTM programmando lingua.)"

Answer 3

è possibile?

Sì.

Accade con qualsiasi ragionevole grado di frequenza?

No.

Answer 4

Pensaci. Esistono un numero infinito di oggetti potenziali e solo 4 miliardi di codici hash. Chiaramente, un'infinità di potenziali oggetti condividono ogni codice hash.

Sun JVM basa il codice hash Object su un handle stabile sull'oggetto o memorizza nella cache il codice hash iniziale. La compattazione durante il GC non altera lo hashCode(). Tutto si spezzerebbe se lo facesse.

Answer 5

Se non ci fossero tante codici hash come memoria indirizzi, quindi sarebbe stata necessaria la memoria intera per memorizzare l'hash stesso. :-)

Quindi, sì, i codici di hash dovrebbero talvolta coincidere.

Answer 6

Stai parlando della classe attuale Object o di oggetti in generale? Tu usi entrambi nella domanda.(E nel mondo reale applicazioni in genere non creare un sacco di istanze di Object)

per gli oggetti in genere, è comune per scrivere una classe per la quale si desidera ignorare equals(); e se lo fai, devi anche sostituire lo hashCode() in modo che due diverse istanze di quella classe che sono "uguali" debbano avere anche lo stesso codice hash. È probabile che si ottenga un codice hash "duplicato" in questo caso, tra istanze della stessa classe.

Inoltre, in sede di attuazione hashCode() in classi diverse, sono spesso basati su qualcosa in oggetto, così si finisce con i valori meno "casuali", con conseguente "duplicato" codici hash tra le istanze di classi diverse (anche quegli oggetti sono "uguali").

In qualsiasi app del mondo reale, non è raro trovare oggetti diversi con lo stesso codice hash.

Answer 7

Suppongo che la domanda originale riguardi solo i codici hash generati dall'implementazione predefinita Object. Il fatto è che i codici hash non devono essere fatti valere per i test di uguaglianza e vengono utilizzati solo in alcune specifiche operazioni di mappatura hash (come quelle implementate dall'implementazione molto utile HashMap).

Come tali non hanno bisogno di essere davvero unici - devono essere abbastanza unici da non generare molti conflitti (il che renderà l'implementazione HashMap inefficiente).

Inoltre, quando lo sviluppatore implementa le classi che devono essere memorizzate in HashMaps, implementerà un algoritmo di codice hash che ha una bassa probabilità di conflitti per oggetti della stessa classe (supponendo che si memorizzino solo oggetti dello stesso classe nell'applicazione HashMaps), e conoscere i dati rende molto più semplice implementare hashing robusto.

Vedere anche la risposta di Ken sull'eguaglianza che richiede codici hash identici.