Migliore funzione di hash per identificatori misti numerici e letterali

Question

Per motivi di prestazioni, ho bisogno di dividere un gruppo di oggetti identificati da una stringa in gruppi. Oggetti possono essere sia identificati da un numero o una stringa in forma prefissata (qualificato) con puntini separare parti dell'identificatore:

12 
323 
12343 
2345233 
123123131 
ns1:my.label.one 
ns1:my.label.two 
ns1:my.label.three 
ns1:system.text.one 
ns2:edit.box.grey 
ns2:edit.box.black 
ns2:edit.box.mixed 

identificatori numerici sono da 1 a diversi milioni. Gli identificatori di testo hanno più probabilità di averne molti a partire dallo stesso prefisso dello spazio dei nomi (ns1 :) e con lo stesso prefisso del percorso (edit.box.).

Qual è la migliore funzione di hash per questo scopo? Sarebbe bello poter prevedere in qualche modo la dimensione del bucket in base alle statistiche degli identificatori di oggetti. Ci sono alcuni buoni articoli per costruire una buona funzione di hash basata su alcune informazioni statistiche?

Esistono diversi milioni di identificatori di questo tipo, ma lo scopo è dividerli in gruppi di 1-2.000 in base alla funzione di hash.

Answer 1

Due buone funzioni di hash possono essere mappate nello stesso spazio di valori e, in generale, non causano nuovi problemi in seguito alla combinazione di esse.

Quindi la funzione di hash può assomigliare a questo:

if it's an integer value: 
    return int_hash(integer value) 
return string_hash(string value) 

A meno che non ci sia alcuna aggregazione dei tuoi numeri interi intorno a certi valori di modulo N, dove N è un numero possibile di benne, poi int_hash può semplicemente restituire il suo ingresso.

Scegliere un hash di stringa non è un nuovo problema. Prova "djb2" (http://www.cse.yorku.ca/~oz/hash.html) o simile, a meno che tu non abbia osceni requisiti di prestazione.

Non credo che ci sia molto da fare nella modifica della funzione di hash per tenere conto dei prefissi comuni. Se la tua funzione di hash è buona per iniziare, è improbabile che i prefissi comuni creino qualsiasi aggregazione di valori hash.

Se si esegue questa operazione e l'hash non funziona in modo imprevisto, e si mettono i diversi milioni di valori hash in qualche migliaio di bucket, le popolazioni bucket verranno distribuite normalmente, con media (diversi milioni/pochi mille) e varianza 1/12 (poche migliaia)^2

Con una media di 1500 voci per bucket, che rende la deviazione standard da qualche parte intorno al 430. Il 95% di una distribuzione normale si trova entro 2 deviazioni standard della media quindi il 95% dei tuoi bucket conterrà 640-2360 voci, a meno che non abbia sbagliato le mie somme. È sufficiente o hai bisogno che i secchi siano di dimensioni più simili?

Answer 2

Probabilmente andrebbe sicuro con sha1 e troncandolo a qualsiasi dimensione desideri.

Non sarebbe estremamente efficiente, ma forse la funzione di hash non sarà un collo di bottiglia?

Answer 3

Ritengo che CRC16 sarebbe un hash ragionevole da utilizzare su queste stringhe e che i gruppi non dovrebbero superare i 1-2 mila.

questo dovrebbe rendere la tabella hash circa 1 MB + tuttavia molti elementi che si hanno in esso * 4 byte, quindi stiamo parlando di 50 MB, e poi ci sono anche tutti i dati effettivi vengano memorizzati, che era meglio essere molto piccolo.