Che cosa è un numero primo ragionevole per il calcolo codice hash?

Question

Eclipse 3.5 ha una caratteristica molto piacevole per generare funzioni Java hashCode (). Si genererebbe per esempio (leggermente accorciato:)

class HashTest {
    int i;
    int j;        
    public int hashCode() {
        final int prime = 31;
        int result = prime + i;
        result = prime * result + j;
        return result;
    }
}

(Se si dispone di più attributi nella classe, result = prime * result + attribute.hashCode(); viene ripetuto per ogni attributo aggiuntivo. Per interi .hashCode () può essere omesso.)

Questo sembra bene, ma per la scelta 31 per il primo. Probabilmente è preso dalla realizzazione hashCode di Java String , che è stato utilizzato per motivi di prestazioni che sono ormai lontani dopo l'introduzione dei moltiplicatori hardware. Qui si hanno molte collisioni hashCode per piccoli valori di i e j: per esempio (0,0) e (pari al -1,31) hanno lo stesso valore. Penso che è una brutta cosa (TM), dal momento che i piccoli valori si verificano spesso. Per String.hashCode troverete anche molte stringhe brevi con lo stesso codice hash, per esempio "Ca" e "DB". Se si prende una grande serata, questo problema scompare se si sceglie il primo a destra.

Quindi la mia domanda: che cosa è un buon primo a scegliere? Quali criteri si applicano a trovarlo?

Questa è intesa come una questione generale - quindi non voglio dare un intervallo per i e j. Ma suppongo che nella maggior parte delle applicazioni relativamente piccoli valori si verificano più spesso di quanto i valori di grandi dimensioni. (Se si dispone di valori di grandi dimensioni la scelta del primo è probabilmente irrilevante.) Potrebbe non fa molta differenza, ma una scelta migliore è un modo semplice e ovvio per migliorare questo - quindi perché non farlo? Commons Lang HashCodeBuilder suggerisce anche stranamente piccoli valori.

( Chiarimento : questo è non un duplicato di Perché hashCode di Java () nella stringa di utilizzare 31 come moltiplicatore? dato che la mia domanda non riguarda la storia del 31 nel JDK, ma su ciò che sarebbe un valore migliore in nuovo codice utilizzando lo stesso modello di base. Nessuna delle risposte lì cercare di rispondere a questa.)

Answer 1

Mi consiglia di utilizzare 92821 . Ecco perché.

Per dare una risposta significativa a questo si deve sapere qualcosa circa i possibili valori di i e j. L'unica cosa che posso pensare in generale è, che in molti casi piccoli valori saranno più comune di quanto i valori di grandi dimensioni. (Le probabilità di 15 che appaiono come un valore nel programma sono molto meglio di, diciamo, 438281923.) così sembra una buona idea per fare la più piccola collisione hashcode il più grande possibile, scegliendo un primo adeguato. Per 31 questo piuttosto male - già per i=-1 e j=31 avete lo stesso valore di hash che per i=0 e j=0

.

Dal momento che questo è interessante, ho scritto un piccolo programma che ha cercato l'intera gamma int per il miglior primo in questo senso. Cioè, per ogni primo ho cercato per il valore minimo di Math.abs(i) + Math.abs(j) su tutti i valori di i,j che hanno lo stesso codice hash come 0,0, e poi ha preso il primo in cui questo valore minimo è il più grande possibile.

Rullo di tamburi : il miglior primo in questo senso è 486.187.739 (con la più piccola collisione essere i=-25486, j=67194). Quasi come buono e molto più facile da ricordare è 92821 con la più piccola collisione essendo i=-46272 and j=46016.

Se si dà "piccolo" un altro significato e vuole essere il minimo di Math.sqrt(i*i+j*j) per la collisione più grande possibile, i risultati sono un po 'diversa: la cosa migliore sarebbe 1.322.837,333 mila con i=-6815 and j=70091, ma il mio preferito 92821 (più piccola collisione -46272,46016 ) è di nuovo quasi buono come il miglior valore.

Io riconosco che è abbastanza discutibile se questi calcoli molto senso nella pratica. Ma credo che l'assunzione di 92821 come primo rende molto più senso oltre il 31, a meno che non si hanno buone ragioni per non farlo.

Answer 2

In realtà, se si prende un primo così grande che si avvicina a INT_MAX, avete lo stesso problema a causa del modulo aritmetica. Se vi aspettate di hash per lo più stringhe di lunghezza 2, forse un primo nei pressi della radice quadrata di INT_MAX sarebbe meglio, se le stringhe si hash sono più lunghi non importa così tanto e le collisioni sono inevitabili in ogni caso ...

Answer 3

Le collisioni non può essere un grosso problema ... L'obiettivo primario del hash è quello di evitare l'uso di pari per 1: 1 confronti. Se si dispone di un'implementazione in cui è uguale è "generalmente" estremamente a buon mercato per gli oggetti che si sono scontrati hashs, allora questo non è un problema (a tutti).

Alla fine, qual è il modo migliore di hashing dipende da ciò che si sta confrontando. Nel caso di una coppia int (come nel tuo esempio), utilizzando operatori bit per bit di base potrebbe essere sufficiente (come usando & o ^).

Answer 4

È necessario definire la vostra gamma per i e j. Si potrebbe utilizzare un numero primo per entrambi.

public int hashCode() {
   http://primes.utm.edu/curios/ ;)
   return 97654321 * i ^ 12356789 * j;
}

Answer 5

sceglierei 7243. Grande abbastanza per evitare collisioni con piccoli numeri. non trabocchi di piccoli numeri rapidamente.

Answer 6

Voglio solo sottolineare che codice hash non ha nulla a che fare con il primo. In attuazione JDK

for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }

Ho trovato se si sostituisce 31 con 27 , il risultato sono molto simili.