Perché è così, più bit "1" nella mia chiave, più tempo è necessario inserire in HashMap?

Question

Sto facendo un progetto per una classe che si concentra sull'archiviazione di una matrice enorme con la maggior parte dei valori 0 in memoria e su cui viene eseguita una matematica matriciale. Il mio primo pensiero è stato quello di utilizzare uno HashMap per memorizzare gli elementi della matrice e memorizzare solo gli elementi che non sono zero, al fine di evitare l'utilizzo di enormi quantità di memoria.

Volevo creare una chiave per lo HashMap che rappresenterebbe sia il numero di riga e di colonna dell'elemento in un modo che, quando ho avuto accesso a quella voce nella mappa, è stato possibile estrarre entrambi i valori. Non conosco Java e C# - in C# vorrei creare un struct con i membri e Column, ma in Java ho realizzato rapidamente che non ci sono tipi di valori utente. Con una scadenza incombente sono andato con una scommessa sicura e reso il Key un lungo. Ho archiviato i dati di riga (int 32 bit) nei primi 32 bit e i dati di colonna negli ultimi 32 utilizzando un cambio di bit molto semplice. [EDIT: Mi piacerebbe anche notare che la mia HashMap è inizializzata con una dimensione iniziale specifica che rappresenta esattamente il numero di valori che immagazzino, che non viene mai superato.]

[Nota a margine: la ragione per cui voglio per poter estrarre nuovamente i dati riga/colonna è di aumentare notevolmente l'efficienza della moltiplicazione di matrici, dalle O(n^2) a O(n), e una più piccola n per l'avvio]

quello che ho notato dopo l'attuazione questa struttura è che ci vuole un enorme 7 secondi per leggere una matrice 23426 x 23426 da un file di testo in cui vengono dati solo elementi diversi da zero, ma ci vogliono solo 2 secondi per calcolare i valori di autovalori che ci viene richiesto di dare! Dopo aver commentato in modo selettivo i metodi, ho concluso che la maggior parte di questo intervallo di 7 secondi è dedicato alla memorizzazione dei miei valori nello HashMap.

public void Set(double value, int row, int column) { 
    //assemble the long key, placing row and column in adjacent sets of bits 
    long key = (long)row << SIZE_BIT_MAX; //(SIZE_BIT_MAX is 32) 
    key += column; 
    elements.put(key, value); 
} 

Questo è il codice per l'impostazione di un valore. Se invece utilizzo questo metodo:

public void Set(double value, int row, int column) { 
    //create a distinct but smaller key (around 32 bits max) 
    long key = (long)(row * matrixSize) + column; 
    elements.put(key, value); 
} 

La lettura richiede solo 2 secondi. Entrambe queste versioni della chiave sono distinte per ogni elemento, entrambi sono di tipo lungo e il codice effettivo per crearli è di complessità minima. È il elements.put(key, value) che fa la differenza tra 7 secondi e 2.

La mia domanda è, perché? La differenza che vedo tra queste versioni chiave è che il primo ha bit impostati su 1 in tutto e più frequentemente, mentre il secondo ha tutti i suoi 32 bit più alti impostati su 0. Sto inseguendo un'aringa rossa, o è questa differenza abbastanza drammatica nelle prestazioni il risultato di qualcosa di interno nel metodo HashMap.put?

Answer 1

Date un'occhiata a come Long implementa il metodo hashCode() (almeno in OpenJDK 7):

public int hashCode() { 
    return (int)(value^(value >>> 32)); 
} 

Questo significa che la vostra chiave viene farcito di nuovo in 32 bit; tutti i bit più bassi si annullano a vicenda abbastanza spesso, con il risultato di molte collisioni che richiedono allo HashMap di dedicare più tempo alla ricerca di uno slot libero in un bucket. Il tuo secondo metodo evita questo problema perché il codice hash generato da ogni chiave è un valore univoco (perché hai solo 23426 x 23426 = 548777476 elementi che si adattano bene a 32 bit).

Quindi, la resa è la selezione chiave ma non il numero di bit impostati.

Tuttavia, che cosa esattamente cosa si intende con “i tipi di valore utente?”

public class MatrixKey { 
    private final int row; 
    private final int column; 
    public MatrixKey(int row, int column) { 
     this.row = row; 
     this.column = column; 
    } 
    public int getRow() { return row; } 
    public int getColumn() { return column; } 
} 

Questa classe può fare una perfetta buona chiave per una Map in Java, una volta si sceglie di implementare hashCode() e equals(). Assicurati solo di non implementare il suo metodo hashCode come fa Long. :)

Answer 2

A seconda dell'implementazione, è possibile che si verifichino collisioni hash.

Se tutti i valori di hash finiscono nello stesso "bucket", l'implementazione normalmente li inserisce in un elenco di un certo tipo. Se questo è il caso, i tempi di accesso risentiranno in modo significativo.

Answer 3

Dal JDK 6 documentation for Long.hashCode() (si noti che il long primitiva è autoboxed in un oggetto Long - mentre in C# primitive in realtà sono oggetti):

restituisce un codice hash per questo a lungo. Il risultato è l'OR esclusivo delle due metà del valore lungo primitivo detenuto da questo oggetto Lungo.Cioè, il codice hash è il valore dell'espressione:

(int)(this.longValue()^(this.longValue()>>>32)) 

Penso dato questa definizione, questo spiega perché:

il tasso di collisione si riduce quando si introducono più entropia e disperderla in tal modo più attraverso la metà superiore del valore long. (Edit: Ho letto l'ordine sbagliato, quindi ecco la contro-argomentazione sotto)

Le collisioni potrebbero essere più probabile quando si estende nel campo di long - dopo tutto, in Java, codici hash sono solo int dimensioni, in modo puoi avere solo una quantità limitata di distribuzione equa. Se sai che è "uniformemente" distribuito su un intervallo int, le tue collisioni sono ridotte. Se lo diffondi nell'intervallo long, aumenta notevolmente le possibilità di collisione.

Ecco from the HashMap Java documentation (sottolineatura mia):

Questa implementazione fornisce prestazioni costanti in tempo per le operazioni di base (get e put), assumendo la funzione di hash disperde gli elementi correttamente tra i secchi

Nota a margine: i miglioramenti delle prestazioni sono ancora migliori sintonizzando initial capacity e load factor - consultare la documentazione HashMap per ulteriori informazioni.