Per la moltiplicazione di interi, l'overflow e la perdita di informazioni

Question

Sto leggendo tramite Chapter 3 di di Joshua Bloch Java efficace. In Articolo 8: ignorare sempre hashCode quando si modifica uguale, l'autore utilizza il passo seguente che unisce nella sua funzione di hashing:

result = 37 * result + c; 

Poi spiega perché 37 è stato scelto (enfasi aggiunta):

Il moltiplicatore 37 è stato scelto perché è un numero primo dispari. Se fosse pari e la moltiplicazione traboccava, le informazioni andrebbero perse perché la moltiplicazione di due equivaleva allo spostamento. I vantaggi dell'utilizzo di un numero primo sono inferiori a , ma è normale utilizzare i numeri primi a questo scopo.

La mia domanda è perché è importante che il fattore che unisce (37) è strano? Il superamento della moltiplicazione non determinerebbe una perdita di informazioni indipendentemente dal fatto che il fattore fosse pari o dispari?

Answer 1

Considerate cosa succede quando un valore positivo viene ripetutamente moltiplicato per due in una rappresentazione in base 2 - tutti i bit impostati alla fine si allontanano dalla fine, lasciandovi zero.

Un moltiplicatore pari risulterebbe in codici hash con meno diversità.

I numeri dispari, d'altro canto, possono causare eccessi, ma senza perdita di diversità.

Answer 2

Lo scopo di un hashCode è quello di avere bit casuali in base ai contributi (in particolare i bit inferiori come questi vengono spesso utilizzati più)

Quando si multipla per 2 il bit più basso può essere solo 0, che manca di casualità . Se diventi multiplo per un numero dispari, il bit più basso può essere pari o dispari.

---

Una domanda simile è quello che si ottiene qui

public static void main(String... args) { 
    System.out.println(factorial(66)); 
} 

public static long factorial(int n) { 
    long product = 1; 
    for (; n > 1; n--) 
     product *= n; 
    return product; 
} 

stampe

0 

Ogni secondo numero è un ancora ed ogni via un multiplo di 4, ecc

Answer 3

La soluzione si trova in Number Theory e nello Lowest common denominator del moltiplicatore e del numero del modulo.

Un esempio può essere d'aiuto. Diciamo invece che a 32 bit hai solo 2 bit per rappresentare un numero. Quindi hai 4 numeri (classi). 0, 1, 2 e 3

Un overflow nella CPU è la stessa come un'operazione di modulo

Class - x2 - mod 4 - x2 - mod 4 

0  0  0  0  0 

1  2  2  4  0 

2  4  0  0  0 

3  6  2  4  0 

Dopo 2 operazioni Hai solo 1 possibilità numero (classe) sinistra. Quindi hai informazioni "perse".

Class - x3 - mod 4 - x3 - mod 4 ... 

0  0  0  0  0 

1  3  3  9  1 

2  6  2  6  2 

3  9  1  3  3 

Questo può andare avanti all'infinito e hai ancora tutte e 4 le classi. Quindi non perdi informazioni.

La chiave è che l'LCD del muliplier e della classe modulo è 1. Questo vale per tutti i numeri dispari perché il numero del modulo è attualmente sempre un potere di 2. Non devono essere numeri primi e non hanno essere 37 nello specifico. Ma la perdita di informazioni è solo uno criteri Perchè 37 viene raccolto altri criteri sono la distribuzione dei valori ecc

Answer 4

non-matematica semplice versione del perché ...

I numeri primi sono utilizzati per l'hashing per mantenere la diversità.

Forse la diversità è più importante a causa dell'impostazione Set e Mappa. Queste implementazioni utilizzano gli ultimi bit di numeri hash dell'oggetto per indicizzare le matrici interne di voci.

Ad esempio, in una HashMap con tabella interna (array) per voci con dimensione 8 verranno utilizzati gli ultimi 3 bit di numeri hash per l'inserimento della tabella di indirizzo.

 

    static int indexFor(int h, int length) { 
     return h & (length-1); 
    } 

Infatti non è ma se oggetto Integer avrebbe

 

    hash = 4 * number; 

maggior parte di elementi della tabella sarà vuoto ma comunque contiene troppe voci. Ciò porterebbe a ulteriori iterazioni e operazioni di confronto durante la ricerca di una particolare voce.

Immagino che la preoccupazione principale di Joshua Bloch fosse quella di distribuire gli hash interi il più possibile per ottimizzare le prestazioni delle collezioni distribuendo gli oggetti in modo uniforme in Maps e Sets. I numeri primi intuitivamente sembrano essere un buon fattore di distribuzione.

Answer 5

I numeri primi non sono strettamente necessari per garantire la diversità; ciò che è necessario è che il fattore sia relativamente primo al modulo.

Poiché il modulo per l'aritmetica binaria è sempre una potenza di due, qualsiasi numero dispari è relativamente primo, e sarebbe sufficiente. Se si dovesse prendere un modulo diverso da un overflow, tuttavia, un numero primo continuerà a garantire la diversità (supponendo che non si sia scelto lo stesso primo ...).