Quanti secchi di hash

Question

Se noto che una tabella hash (o qualsiasi altra struttura di dati costruita su una tabella hash) si sta riempiendo, a che punto dovresti costruire una nuova tabella con più bucket. E dato finora n elementi nella tabella, come fai a capire quanti secchi usare nel nuovo?

Quindi diciamo che ho 100 secchi. Devo riorganizzarlo quando ci sono 50 articoli? 500? 5000? O dovrei cercare il secchio più completo e la chiave su quello? Quindi, quando raggiungo quel punto, quanto sono grande la nuova tabella hash?

In relazione a questo, se si conosce in anticipo approssimativamente quanti elementi verranno inseriti, esiste un modo per calcolare il numero di bucket per ottenere una buona prestazione media?

So che la vera risposta dipende da molte altre considerazioni come l'importanza della velocità rispetto alle dimensioni in un esempio specifico, ma sto cercando linee generali di gilda.

So anche che non dovrei ottimizzare questo genere di cose a meno che una buona profilazione non abbia indicato che si tratta di un collo di bottiglia. Sto solo pensando a un progetto che userebbe molte tabelle hash e mi chiedevo come affrontarlo.

Answer 1

Una buona regola del pollice (non sempre ideale, beh, solo una regola del pollice) è quella di ripetere l'hash se l'hashtable è riempito fino all'80%. Ciò significa che se hai 100 secchi e 80 oggetti all'interno, indipendentemente da quante collisioni hai avuto prima, sta ottenendo il tempo per aumentare la capacità.

Quanto dovresti aumentarlo? Bene, non esiste anche un valore perfetto. La soluzione più semplice è raddoppiare la capacità ad ogni aumento. Quindi va a 200, 400, 800 e così via. Se pensi che sia troppo (dopotutto salterà da 8 MB di memoria a 16 MB quando l'hashtable diventa davvero grande e potresti non riempire mai i 16 MB), scegli un fattore di crescita più piccolo. Almeno 1/3 è raccomandato (aumentandolo da 100 a 133) Direi, forse lascialo crescere del 50% ogni volta come un compromesso.

Tutto ciò dipende anche dal modo in cui vengono gestite le collisioni. Un modo semplice per gestirli (il mio preferito personale) è quello di memorizzare gli elementi in un elenco collegato quando c'è una collisione. Se 3 elementi vengono posizionati sulla stessa chiave, ci sono ancora solo 3 confronti per trovarlo. Poiché l'elenco collegato è molto inefficace per la ricerca, potresti voler aumentare la capacità prima, ad es. se viene utilizzata una capacità del 60% per mantenere veloce la tabella hash. OTOH, puoi fare qualcosa di più sofisticato e tenere statistiche sul numero di collisioni. Finché non si hanno quasi collisioni (se si dispone di una funzione hash molto buona) non è necessario eseguire nuovamente l'hash, anche se il 99% della sua capacità è in uso. Inoltre, se gestisci le collisioni in modo sofisticato (ad esempio ogni nodo è di nuovo una tabella ordinata e puoi eseguire una ricerca binaria all'interno di queste) la tua ricerca potrebbe essere ancora abbastanza veloce se la tabella viene caricata al 200% (quindi hai il doppio degli elementi come capacità). In tal caso, potresti tenere le statistiche su quanto è grande la tabella ordinata più grande e quando diventa più grande di, diciamo, 8 voci, pensi che questo stia diventando troppo lento e poi riesci.

Il re-hashing è molto lento, quindi dovrebbe essere evitato il più spesso possibile. Pertanto, se è necessario eseguire nuovamente l'hash, non solo aumentare la capacità troppo poco, altrimenti è necessario ripetere la hash abbastanza presto quando si aggiungono più elementi. Pertanto, quando è necessario eseguire nuovamente l'hash, aumentare notevolmente la capacità rispetto al numero di elementi attualmente presenti nella tabella, tutto il resto è capacità insufficiente.

Answer 2

Generalmente, cerchi il fattore di carico (informalmente, l'hai già detto) che è formalmente definito come & # 945; & nbsp; = & nbsp; n & nbsp; / & nbsp; N , ovvero il rapporto tra bucket utilizzati e totali. Affinché una tabella di hash funzioni correttamente (o almeno per ragionare sulle sue prestazioni in termini matematici), dovrebbe essere & # 945; & Nbsp; & Lt; & Nbsp; 1.

Tutto il resto dipende dai test empirici: se vedi che la tua tabella hash non funziona bene a partire da & # 945; & nbsp; > & nbsp; 0.5, quindi assicurati di rimanere al di sotto di quel valore. Questo valore dipende anche dalla tecnica di risoluzione delle collisioni. L'hash con il concatenamento può richiedere altri fattori di carico oltre all'hash con indirizzamento aperto. Ancora un altro fattore è la localizzazione della cache. Se il tuo tavolo diventa troppo grande, non si adatta alla memoria principale. Poiché l'accesso all'array è casuale, il caricamento dalla cache può diventare un collo di bottiglia.

Answer 3

Esistono in genere due tipi di hashtable: aperto e chiuso.

In una tabella hash aperta trovi il bucket giusto in base all'hash, quindi crea un elenco di elementi che pendono dal bucket.

In un hashtable chiuso trovi il bucket iniziale usando il valore hash, e se è occupato sonderai il valore successivo. Nel caso semplicistico puoi farlo cercando il prossimo bucket gratuito, oppure puoi creare un secondo valore di hash dal tuo articolo e passare da quello (anche se devi assicurarti che questo sia il modulo principale la dimensione delle tabelle di hash in modo da visitare tutti i secchi).

In genere una tabella hash aperta non viene ridimensionata. Impostate le dimensioni iniziali in modo che siano ritenute ragionevoli per il problema. Come altri hanno sottolineato, è possibile ridimensionare su una tabella hash aperta, ma il ragionamento sulle prestazioni di questa struttura di dati ora diventa molto difficile. Se ridimensioni quando la lunghezza di un determinato bucket è L, allora potresti finire per ridimensionare solo L elementi nell'intera tabella hash, il che è molto inefficiente.

Una tabella hash chiusa viene ridimensionata quando il fattore di carico (n. di articoli nella tabella hash / n. di bucket) raggiunge un valore predefinito. Tendo a utilizzare l'80%, ma è improbabile che il valore esatto sia troppo critico.

Il vantaggio di una tabella hash chiusa è che il costo ammortizzato dell'inserimento di un elemento è sempre O (1) (assumendo una buona funzione hash). L'inserimento di un elemento particolare potrebbe essere O (N) a causa del costo del ridimensionamento, ma ciò avviene molto raramente.

Answer 4

Dipende dal tipo di tabella hash che stai costruendo. Se stai usando una tabella hash basata su array fisso (al contrario degli elenchi collegati per i bucket), dovresti ridimensionare l'array quando la tabella è piena o quando hai raggiunto un numero massimo di sonde (a seconda che ti interessi di più sulla velocità o memoria). Se stai usando elenchi collegati, la memoria non è poi così preoccupante e non devi cercare spazi vuoti, quindi il ridimensionamento non è un grosso problema.

La chiave con le tabelle hash è l'algoritmo di hashing, non il numero di bucket. Idealmente, vuoi sempre al massimo un oggetto in ogni bucket, quindi dovresti idealmente ridimensionare quando il numero di elementi nella tabella hash = il numero di bucket. Se i tuoi dati non sono distribuiti uniformemente, stai meglio con un algoritmo hash migliore rispetto a una strategia di ridimensionamento migliore.

Answer 5

Se si utilizza l'hashing lineare, la tabella stessa si occupa automaticamente del ridimensionamento, mantenendo un fattore di carico costante.