Hashing dinamico perfetto - Dynamic perfect hashing
In informatica , l' hashing dinamico perfetto è una tecnica di programmazione per risolvere le collisioni in una struttura di dati di tabelle hash . Anche se richiede più memoria rispetto alle controparti della tabella hash, questa tecnica è utile per le situazioni in cui è necessario eseguire query, inserimenti ed eliminazioni veloci su un ampio set di elementi.
Dettagli
caso statico
Schema FKS
Il problema dell'hashing statico ottimale è stato risolto per la prima volta in generale da Fredman, Komlós e Szemerédi. Nel loro articolo del 1984, descrivono in dettaglio uno schema di tabelle hash a due livelli in cui ciascun bucket della tabella hash (di primo livello) corrisponde a una tabella hash separata di secondo livello. Le chiavi vengono hash due volte: il primo valore hash viene mappato a un determinato bucket nella tabella hash di primo livello; il secondo valore hash fornisce la posizione di quella voce nella tabella hash di secondo livello di quel bucket. La tabella di secondo livello è garantita per essere esente da collisioni (cioè hashing perfetto ) al momento della costruzione. Di conseguenza, il costo di ricerca è garantito essere O(1) nel caso peggiore .
Nel caso statico, ci viene fornito un insieme con un totale di x voci, ognuna con una chiave univoca, in anticipo. Fredman, Komlós e Szemerédi scelgono una tabella hash di primo livello con dimensione s = 2(x-1) bucket.
Per costruire, le voci x sono separate in s bucket dalla funzione di hashing di livello superiore, dove s = 2(x-1) . Quindi per ogni bucket con k voci, viene allocata una tabella di secondo livello con k 2 slot e la sua funzione di hash viene selezionata casualmente da un set di funzioni di hash universale in modo che sia priva di collisioni (ovvero una funzione di hash perfetta ) e memorizzata accanto alla tabella hash. Se la funzione hash selezionata casualmente crea una tabella con collisioni, viene selezionata casualmente una nuova funzione hash fino a quando non è possibile garantire una tabella priva di collisioni. Infine, con l'hash senza collisioni, le k voci vengono hash nella tabella di secondo livello.
La dimensione quadratica dello spazio k 2 assicura che la creazione casuale di una tabella con collisioni sia poco frequente e indipendente dalla dimensione di k , fornendo un tempo di costruzione ammortizzato lineare. Sebbene ogni tabella di secondo livello richieda uno spazio quadratico, se le chiavi inserite nella tabella hash di primo livello sono distribuite uniformemente , la struttura nel suo insieme occupa lo spazio O( n ) previsto , poiché le dimensioni dei bucket sono piccole con alta probabilità .
La funzione hash di primo livello è scelta in modo specifico in modo che, per l'insieme specifico di x valori di chiave univoci, lo spazio totale T utilizzato da tutte le tabelle hash di secondo livello abbia previsto uno spazio O( n ), e più specificamente T < s + 4*x. Fredman, Komlós e Szemerédi hanno mostrato che data una famiglia di hashing universale di funzioni hash, almeno la metà di queste funzioni ha quella proprietà.
Custodia dinamica
Dietzfelbinger et al. presentano un algoritmo di dizionario dinamico che, quando un insieme di n elementi viene aggiunto in modo incrementale al dizionario, le query di appartenenza vengono sempre eseguite in tempo costante e quindi O(1) tempo nel caso peggiore, lo spazio di archiviazione totale richiesto è O(n) (lineare) , e O(1) tempo di inserimento ed eliminazione ammortizzato previsto ( tempo costante ammortizzato ).
Nel caso dinamico, quando una chiave viene inserita nella tabella hash, se la sua voce nella rispettiva sottotabella è occupata, si dice che si verifica una collisione e la sottotabella viene ricostruita in base al nuovo conteggio totale delle voci e alla funzione hash selezionata casualmente. Poiché il fattore di carico della tabella di secondo livello è mantenuto basso (1/ k ), la ricostruzione non è frequente e il costo previsto ammortizzato degli inserimenti è O(1). Analogamente, il costo previsto ammortizzato delle cancellazioni è O(1).
Inoltre, le dimensioni finali della tabella di primo livello o di una qualsiasi delle sottotabelle non sono conoscibili nel caso dinamico. Un metodo per mantenere lo spazio O( n ) atteso della tabella consiste nel richiedere una ricostruzione completa quando si è verificato un numero sufficiente di inserimenti e delezioni. Per i risultati dovuti a Dietzfelbinger et al., finché il numero totale di inserimenti o eliminazioni supera il numero di elementi al momento dell'ultima costruzione, il costo previsto ammortizzato di inserimento e cancellazione rimane O (1) con il rimaneggiamento completo preso in considerazione .
L'implementazione dell'hashing dinamico perfetto di Dietzfelbinger et al. usa questi concetti, così come la cancellazione pigra , ed è mostrato in pseudocodice di seguito.
Implementazione dello pseudocodice
Individuare
function Locate(x) is
j := h(x)
if (position hj(x) of subtable Tj contains x (not deleted))
return (x is in S)
end if
else
return (x is not in S)
end else
end
Inserire
Durante l'inserimento di una nuova voce x in j , il contatore di operazioni globali, count , viene incrementato.
Se x esiste in j , ma è contrassegnato come eliminato, il contrassegno viene rimosso.
Se x esiste in j o nella sottotabella T j , e non è contrassegnato come cancellato, si dice che si verifica una collisione e la tabella di secondo livello del j- esimo bucket T j viene ricostruita con una diversa funzione hash selezionata casualmente h j .
function Insert(x) is
count = count + 1;
if (count > M)
FullRehash(x);
end if
else
j = h(x);
if (Position hj(x) of subtable Tj contains x)
if (x is marked deleted)
remove the delete marker;
end if
end if
else
bj = bj + 1;
if (bj <= mj)
if position hj(x) of Tj is empty
store x in position hj(x) of Tj;
end if
else
Put all unmarked elements of Tj in list Lj;
Append x to list Lj;
bj = length of Lj;
repeat
hj = randomly chosen function in Hsj;
until hj is injective on the elements of Lj;
for all y on list Lj
store y in position hj(y) of Tj;
end for
end else
end if
else
mj = 2 * max{1, mj};
sj = 2 * mj * (mj - 1);
if the sum total of all sj ≤ 32 * M2 / s(M) + 4 * M
Allocate sj cells for Tj;
Put all unmarked elements of Tj in list Lj;
Append x to list Lj;
bj = length of Lj;
repeat
hj = randomly chosen function in Hsj;
until hj is injective on the elements of Lj;
for all y on list Lj
store y in position hj(y) of Tj;
end for
end if
else
FullRehash(x);
end else
end else
end else
end else
end
Elimina
L'eliminazione di x contrassegna semplicemente x come eliminato senza rimozione e il conteggio degli incrementi . Sia nel caso di inserimenti che di cancellazioni, se il conteggio raggiunge una soglia M viene ricostruita l'intera tabella, dove M è un multiplo costante della dimensione di S all'inizio di una nuova fase . Qui la fase si riferisce al tempo tra le ricostruzioni complete. Nota che qui il -1 in "Delete( x )" è una rappresentazione di un elemento che non è nell'insieme di tutti i possibili elementi U .
function Delete(x) is
count = count + 1;
j = h(x);
if position hj(x) of subtable Tj contains x
mark x as deleted;
end if
else
return (x is not a member of S);
end else
if (count >= M)
FullRehash(-1);
end if
end
Ricostruzione completa
Una ricostruzione completa della tabella di S inizia rimuovendo tutti gli elementi contrassegnati come cancellati e quindi impostando il successivo valore di soglia M a un multiplo costante della dimensione di S . Una funzione hash, che partiziona S in s ( M ) sottoinsiemi, dove la dimensione del sottoinsieme j è s j , viene ripetutamente scelta a caso finché:
Infine, per ogni sottotabella T j viene ripetutamente scelta casualmente una funzione hash h j da H sj fino a quando h j è iniettiva sugli elementi di T j . Il tempo previsto per una ricostruzione completa della tabella di S con dimensione n è O( n ).
function FullRehash(x) is
Put all unmarked elements of T in list L;
if (x is in U)
append x to L;
end if
count = length of list L;
M = (1 + c) * max{count, 4};
repeat
h = randomly chosen function in Hs(M);
for all j < s(M)
form a list Lj for h(x) = j;
bj = length of Lj;
mj = 2 * bj;
sj = 2 * mj * (mj - 1);
end for
until the sum total of all sj ≤ 32 * M2 / s(M) + 4 * M
for all j < s(M)
Allocate space sj for subtable Tj;
repeat
hj = randomly chosen function in Hsj;
until hj is injective on the elements of list Lj;
end for
for all x on list Lj
store x in position hj(x) of Tj;
end for
end
