Come posso verificare se la mia funzione di hash è buona in termini di carico massimo?

Question

Ho letto vari articoli sul problema "Balls and Bins" e sembra che se una funzione hash funziona correttamente (cioè è effettivamente una distribuzione casuale), allora il seguente dovrebbe/deve essere vero se ho hash n valori in una tabella hash con n asole (o contenitori):

1. probabilità che un bidone è vuoto, per grandi n è 1/e.
2. Il numero previsto di contenitori vuoti è n/e.
3. Probabilità che un contenitore abbia palle <= 1/ek! (corretto).
4. Probabilità che un contenitore abbia almeno k collisioni è <= ((e/k)**k)/e (corretto).

Questi sembrano facili da controllare. Ma il test max-load (il numero massimo di collisioni con alta probabilità) viene generalmente indicato in modo vago.

La maggior parte dei testi indica che il numero massimo di collisioni in un qualsiasi contenitore è O(ln(n)/ln(ln(n))). Alcuni dicono che è 3*ln(n)/ln(ln(n)). Altri tipi di documenti si mescolano a ln e log - di solito senza definirli, o affermano che log è log base e quindi usa ln altrove.

È ln il registro di basare e o 2 ed è questo max-load formula giusta e quanto grande dovrebbe essere n per eseguire un test?

Questa conferenza sembra coprirlo meglio, ma io non sono un matematico.

http://pages.cs.wisc.edu/~shuchi/courses/787-F07/scribe-notes/lecture07.pdf

BTW, with high probability sembra significare 1 - 1/n.

Answer 1

Questa è un'affascinante carta/conferenza-- mi fa desiderare di aver preso una classe di algoritmi formali.

Ho intenzione di dare una risposta ad alcune risposte qui, sulla base di quello che ho appena letto da questo, e sentitevi liberi di votarmi. Apprezzerei una correzione, però, piuttosto che un semplice downvote :) Userò anche n e N in modo intercambiabile qui, che è un grande no-no in alcune cerchie, ma dal momento che sto solo copiando formule, spero che mi perdonerai.

In primo luogo, la base dei registri. Questi numeri sono indicati come notazione O grande, non come formule assolute. Ciò significa che stai cercando qualcosa 'nell'ordine di ln (n)/ln (ln (n))', non con l'aspettativa di una risposta assoluta, ma più che con n diventa più grande, la relazione di n per il numero massimo di collisioni dovrebbe seguire quella formula. I dettagli della curva attuale che puoi tracciare variano a seconda dell'implementazione (e non ne so abbastanza delle implementazioni pratiche per dirti che cos'è una curva "buona", tranne che dovrebbe seguire quella relazione big-O). Queste due formule che hai postato sono in realtà equivalenti in notazione O grande. Il 3 nella seconda formula è solo una costante ed è correlato a una particolare implementazione. Un'implementazione meno efficiente avrebbe una costante più grande.

Con questo in mente, vorrei eseguire test empirici, perché sono un biologo di cuore e sono stato addestrato per evitare prove dure e veloci come indicazioni di come il mondo funziona davvero.Inizia con N come numero, ad esempio 100, e trova il raccoglitore con il maggior numero di collisioni in esso. Questo è il tuo carico massimo per quella corsa. Ora, i tuoi esempi dovrebbero essere il più vicino possibile a quello che ti aspetti che gli utenti usino, quindi forse vuoi estrarre a caso le parole da un dizionario o qualcosa di simile come input.

Eseguire quel test molte volte, almeno 30 o 40. Poiché si utilizzano numeri casuali, è necessario accertarsi che il carico massimo medio che si ottiene sia vicino alle "aspettative" teoriche di il tuo algoritmo. L'aspettativa è solo la media, ma dovrai comunque trovarla, e più il tuo std dev/std sarà errato su quella media, più puoi dire che la tua media empirica corrisponde all'aspettativa teorica. Una corsa non è sufficiente, perché una seconda manche (molto probabilmente) darà una risposta diversa.

Quindi, aumentare N, per dire, 1000, 10000, ecc. Aumentarlo logaritmicamente, perché la formula è logaritmica. Con l'aumentare di N, il tuo carico massimo dovrebbe aumentare nell'ordine di ln (n)/ln (ln (n)). Se aumenta ad una velocità di 3 * ln (n)/ln (ln (n)), significa che stai seguendo la teoria che hanno messo in evidenza in quella lezione.

Questo tipo di test empirico ti mostrerà anche dove il tuo approccio si rompe. Può essere che il tuo algoritmo funzioni bene per N < 10 milioni (o qualche altro numero), ma soprattutto, inizia a collassare. Perché potrebbe essere? Forse hai qualche limitazione a 32 bit nel tuo codice senza rendertene conto (cioè usando un 'float' invece di un 'double'), o qualche altro dettaglio di implementazione. Questi tipi di dettagli ti consentono di sapere dove il codice funzionerà correttamente nella pratica, e quindi quando le tue esigenze pratiche cambiano, puoi modificare il tuo algoritmo. Forse far funzionare l'algoritmo per dataset di grandi dimensioni rende molto inefficiente per quelli molto piccoli, o viceversa, quindi individuare quel compromesso ti aiuterà a caratterizzare ulteriormente come potresti adattare il tuo algoritmo a situazioni particolari. Un'abilità sempre utile da avere.

EDIT: una prova del motivo per cui la base della funzione di log non importa con notazione O-grande:

log N = log_10 (N) = log_b (N)/log_b (10)= (1/log_b(10)) * log_b(N) 

1/log_b (10) è una costante, e in notazione O-grande, le costanti vengono ignorate. Le modifiche di base sono gratuite, motivo per cui stai riscontrando una tale variazione nei documenti.

Answer 2

Dopo un po 'di ricerca e di tentativi ed errori credo di poter fornire modo qualcosa a parte a una risposta.

1. Per cominciare, ln e log sembrano riferirsi per accedere in base e se si guarda in matematica dietro la teoria. Ma come indicato da mmr, per le stime O (...), non importa.

2. max-load può essere definito per qualsiasi probabilità che ti piace. La formula utilizzata è tipica

   1-1/n ** c

La maggior parte dei documenti sul tema dell'uso

1-1/n 

Un esempio potrebbe essere più semplice.

Supponiamo che tu abbia una tabella hash degli slot 1000 e che desideri hash 1000 cose. Supponiamo anche che tu voglia conoscere il max-load con una probabilità di 1-1/1000 o 0.999.

Il max-load è il numero massimo di valori hash che risultano essere uguali, ovvero. collisioni (supponendo che la tua funzione di hash sia buona).

Utilizzando la formula per la probabilità di ottenere esattamente k hash identici valori

Pr[ exactly k ] = ((e/k)**k)/e 

poi accumulando la probabilità di esattamente 0..k voci fino a quando il totale è pari o superiore 0.999 si dice che è il kmax-load.

es.

Pr[0] = 0.37 
Pr[1] = 0.37 
Pr[2] = 0.18 
Pr[3] = 0.061 
Pr[4] = 0.015 
Pr[5] = 0.003  // here, the cumulative total is 0.999 
Pr[6] = 0.0005 
Pr[7] = 0.00007 

Quindi, in questo caso, il max-load è 5.

Quindi, se la mia funzione di hash sta lavorando bene sul mio insieme di dati, allora mi devo aspettare il numero maxmium di valori hash identici (o collisioni) per essere 5.

Se non lo è allora questo potrebbe essere dovuto alle seguenti ragioni:

1. I suoi dati ha piccoli valori (come brevi stringhe) che hash allo stesso valore. Qualsiasi hash di un singolo carattere ASCII sceglierà 1 di 128 valori hash (ci sono modi per aggirare questo, ad esempio potresti usare più funzioni hash, ma rallenta l'hashing e non ne so molto).

2. La tua funzione di hash non funziona bene con i tuoi dati - prova con dati casuali.

3. La tua funzione di hash non funziona bene.

Le altre prove che ho citato nella mia interrogazione sono anche utile vedere che la funzione di hash è in esecuzione come previsto.

Per inciso, la mia funzione di hash ha funzionato bene - tranne che su stringhe brevi (1..4 caratteri).

Ho anche implementato una semplice versione di tabella divisa che colloca il valore di hash nello slot meno utilizzato da una scelta di 2 posizioni. Questo più che dimezza il numero di collisioni e significa che aggiungere e cercare nella tabella hash è un po 'più lento.

Spero che questo aiuti.

Answer 3

Ecco un inizio approssimativo della soluzione di questo problema che coinvolge distribuzioni uniformi e carico massimo.

Invece di cassonetti e sfere o urne o scatole o secchi o m e n, le persone (p) e le porte (d) saranno utilizzate come denominazioni.

Esiste un valore previsto esatto per ciascuna porta a cui è assegnato un determinato numero di persone. Ad esempio, con 5 persone e 5 porte, la porta massima prevista è esattamente 1.2864 {(1429-625)/625} sopra la media (p/d) e la porta minima è esattamente -0.9616 {(24-625)/625 } sotto la media. Il valore assoluto della distanza della porta più alta rispetto alla media è un po 'più grande della porta più piccola perché tutte le persone potrebbero attraversare una porta, ma non meno di zero può attraversare una delle porte.Con un gran numero di persone (p/d> 3000), la differenza tra il valore assoluto della distanza della porta più alta dalla media e la porta più bassa diventa trascurabile.

Per un numero dispari di porte, la porta centrale è essenzialmente zero e non è scalabile, ma tutte le altre porte sono scalabili da determinati valori che rappresentano p = d. Questi valori arrotondati per d = 5 sono:

-1,163 -0,495 0 * 0,495 1,163 * si avvicina lentamente zero dal -0.12

Da questi valori, è possibile calcolare il numero previsto di persone per qualsiasi numero di persone passando attraverso ciascuna delle 5 porte, inclusa la porta massima. Ad eccezione della porta ordinata media, la differenza dalla media è scalabile di sqrt (p/d).

Così, per p = 50.000 e D = 5:
Previsto numero di persone che attraverso la porta massima, che potrebbe essere una qualsiasi delle 5 porte, = 1.163 * sqrt (p/d) + p/d. = 1.163 * sqrt (10.000) + 10.000 = 10.116.3 Per p/d < 3.000, il risultato di questa equazione deve essere leggermente aumentato.

Con più persone, la porta centrale si avvicina lentamente a zero da -0.11968 a p = 100 ep = 5. Può sempre essere arrotondato a zero e, come le altre 4 porte, ha una discreta differenza.

I valori per 6 ante sono: -1,272 -0,643 -0,202 0,202 0,643 1,272

Per 1000 porte, i valori approssimati sono: -3.25, -2.95, -2.79 ... 2.79, 2.95, 3.25

Per ogni d e p, esiste un valore previsto esatto per ciascuna porta ordinata. Si spera che una buona approssimazione (con un errore relativo < 1%) esista. Qualche professore o matematico da qualche parte deve saperlo.

Per testare la distribuzione uniforme, è necessario un numero di sessioni ordinate in media (750-1000 funziona bene) piuttosto che un numero maggiore di persone. Non importa cosa, le differenze tra le sessioni valide sono grandi. Questa è la natura della casualità. Le collisioni sono inevitabili. *

I valori previsti per 5 e 6 porte sono stati ottenuti mediante il calcolo della forza bruta pura utilizzando numeri interi a 640 bit e facendo la media della convergenza dei valori assoluti delle porte opposte corrispondenti. Per d = 5 e p = 170: -6,63901 -2,95905 -0,119342 2,81054 6,90686 (27,36099 31,04095 33,880658 36,81054 40,90686) Per d = 6 e p = 108: -5,19024 -2,7711 -0,973979 0,734434 2,66716 5,53372 (12,80976 15.2289 17.026021 18.734434 20.66716 23.53372)

Spero che tu possa distribuire uniformemente i tuoi dati.

• È quasi garantito che tutti i figli di George Foreman o una situazione simile combatteranno contro la tua funzione di hash. E una corretta pianificazione contingente è il lavoro di tutti i bravi programmatori.