Funzione hash da 64 bit a 10 bit

Desidero una funzione hash che richiede un numero lungo (64 bit) e produce un risultato di 10 bit. Qual è la migliore funzione di hash per tale scopo. Gli input sono fondamentalmente indirizzi di variabili (gli indirizzi sono di 64 bit o 8 byte su Linux), quindi la mia funzione di hash dovrebbe essere ottimizzata a tale scopo.Funzione hash da 64 bit a 10 bit

fonte

2012-07-06 MetallicPriest

Quali informazioni sulla distribuzione dei valori a 64 bit nel tuo universo puoi darci? –

Non esiste una funzione di hash "migliore" per tutti i casi. Devi studiare la distribuzione e le caratteristiche dei tuoi numeri di input. –

L'input è l'indirizzo delle variabili su Linux. – MetallicPriest

direi coincidevano simili:

uint32_t hash(uint64_t x) 
{ 
    x >>= 3; 
    return (x^(x>>10)^(x>>20)) & 0x3FF; 
}

Il timore significativi 3 bit non sono molto utili, come la maggior parte delle variabili sono 4 byte o 8 byte allineati, in modo da rimuoverli. Quindi prendiamo i 30 bit successivi e li mescoliamo insieme (XOR) in blocchi di 10 bit ciascuno.

Naturalmente, si potrebbe anche prendere il (x>>30)^(x>>40)^(x>>50) ma non sono sicuro se faranno alcuna differenza nella pratica.

fonte

2012-07-06 09:34:30 rodrigo

Poiché si usa xor-shift per la miscelazione, raccomanderei l'uso di una delle 275 triplette note con un periodo di 2^64-1 nella loro matrice 64x64 come descritto da Marsaglia, ad esempio (7,11,10) o (21, 17,48). Poiché questo mixa bit in modo pseudocasuale senza stranezze note, è valido per xorare insieme tutte le parole prima di fare il & 0x3ff. In questo modo, ogni bit di input dovrebbe avere la possibilità di influenzare tutti i bit di output. Forse non perfettamente come 50:50 distribuito come in un hash crittografico, ma buono come si può ottenere. A parte questo, un'idea ancora eccellente, +1 – Damon

Il meglio per la maggior parte delle distribuzioni è mod di un numero primo, 1021 è il più grande numero primo a 10 bit. Non è necessario rimuovere i bit bassi.

static inline int hashaddress(void *v) 
{ 
     return (uintptr_t)v % 1021; 
}

Se si pensa che le prestazioni potrebbero essere una preoccupazione, avere un paio di alterna a portata di mano e correre li nel programma vero e proprio. I microbenchmark sono rifiuti; una differenza di pochi cicli è quasi certa di essere sommersa dagli effetti della cache e le dimensioni contano.

fonte

2012-07-06 11:45:43 jthill

ho scritto un giocattolo programma-vedere alcuni indirizzi reali sullo stack, area dati, e heap. Fondamentalmente ho dichiarato 4 globals, 4 locali e ho fatto 2 mallocs. Ho lasciato cadere gli ultimi due bit quando stampavo gli indirizzi. Ecco un uscita da una delle piste:

20125e8 
20125e6 
20125e7 
20125e4 
3fef2131 
3fef2130 
3fef212f 
3fef212c 
25e4802 
25e4806

Che cosa questo mi dice:

Il LSB in questa uscita (3 ° bit dell'indirizzo) è spesso 'sulla' e 'off'. Quindi non lo lascerei cadere nel calcolo dell'hash. Eliminare 2 LSB sembra sufficiente.
Vediamo anche che c'è più entropia negli 8-10 bit inferiori. È necessario utilizzare durante il calcolo dell'hash.
Sappiamo che su una macchina a 64 bit, virtual addresses are never more than 48 bits wide.

Cosa vorrei fare dopo:

/* Drop two LSBs. */ 
a >>= 2; 

/* Get rid of the MSBs. Keep 46 bits. */ 
a &= 0x3fffffffffff; 

/* Get the 14 MSBs and fold them in to get a 32 bit integer. 
The MSBs are mostly 0s anyway, so we don't lose much entropy. */ 
msbs = (a >> 32) << 18; 
a ^= msbs;

Ora passiamo questo attraverso una decent 'half avalanche' hash function, invece di rotolare nostra. 'Valanga tempo' significa che ogni bit di ingresso ha la possibilità di influenzare i bit nella stessa posizione e superiore:

uint32_t half_avalanche(uint32_t a) 
{ 
    a = (a+0x479ab41d) + (a<<8); 
    a = (a^0xe4aa10ce)^(a>>5); 
    a = (a+0x9942f0a6) - (a<<14); 
    a = (a^0x5aedd67d)^(a>>3); 
    a = (a+0x17bea992) + (a<<7); 
    return a; 
}

Per un hash 10 bit, utilizzare i 10 bit MSB del uint32_t restituito.La funzione hash continua a funzionare correttamente se si selezionano gli MSB N per un hash N bit, raddoppiando effettivamente il conteggio del bucket con ogni bit aggiuntivo.

Ero un po 'annoiato, quindi ho scritto un punto di riferimento per questo giocattolo. Niente di speciale, alloca un mucchio di memoria sullo heap e prova l'hash che ho descritto sopra. La fonte può essere trovata da here. Un risultato esempio:

1024 secchi, 256 valori generati, 29 collissions
1024 secchi, 512 valori generati, 103 collissions
1024 secchi, 1024 valori generati, 370 collissions

successivo: Ho provato gli altri due hash a rispondere qui. Entrambi hanno prestazioni simili. Sembra: scegli quello più veloce;)

fonte

2012-07-06 14:54:53 ArjunShankar

Funzione hash da 64 bit a 10 bit

risposta

Problemi correlati