Come sappiamo ci sono 2 strategie classiche per la risoluzione delle collisioni: concatenamento separato e indirizzamento aperto.Quale tipo di risoluzione collisione viene scelta per l'implementazione HashTable/Dictionary in .net?
Mi chiedo quale sia stato scelto per HashTable/Dictionary in .net.
Oppure sono state utilizzate altre strategie?
E 'tutto descritto in questo articolo su MSDN: An Extensive Examination of Data Structures Using C# 2.0
... collisione tecnica di risoluzione chiamata rehasing, che è il tecnica utilizzata per classe Hashtable di .NET Framework. Nella sezione finale , esamineremo la classe Dizionario, che utilizza una tecnica di risoluzione di collisione conosciuta come concatenamento. ....
... Rehasing funziona come segue: v'è un insieme di hash diversi funzioni, H1 ... Hn, e durante l'inserimento o il recupero di un elemento dal tabella hash, inizialmente l'hash H1 la funzione è usata Se questo porta a una collisione, viene invece provato H2 e, se necessario, fino a Hn. La sezione precedente mostrava solo una funzione hash, che è la funzione iniziale di hash (H1). Le altre funzioni di hash sono molto simili a a questa funzione, differenziandosi solo per un fattore moltiplicativo. In generale, la funzione hash Hk è definita come:
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize
La classe Dictionary differisce dalla classe Hashtable in più modi di uno. Oltre a essere fortemente tipizzato, il dizionario utilizza una strategia di risoluzione delle collisioni diversa dalla classe Hashtable , utilizzando una tecnica indicata come concatenamento. Ricordiamo che con il sondaggio , in caso di collisione, viene provato un altro slot nell'elenco dei bucket . Con il rehashing, l'hash viene ricalcolato e viene provato il nuovo slot . Con il concatenamento, tuttavia, viene utilizzata una struttura dati secondaria per contenere eventuali collisioni. Nello specifico, ogni slot nel dizionario ha una matrice di elementi che si associano a quel bucket. Nell'evento di una collisione, l'elemento collisione viene anteposto all'elenco dei bucket .
Ricorda solo la prima frase è mia :-)
Un 'dizionario' non ha una struttura dati secondaria per contenere le collisioni. Almeno in C# 4 non è così. – Gabe
@Gabe: potresti fornire un'altra spiegazione o collegamento? – Seb
@Gabe: Potresti elaborare? Mi sembra una descrizione abbastanza accurata di 'Dictionary
che in realtà è una domanda davvero interessante; Ho appena fatto un blog post su come Dictionary è implementato dietro le quinte. Posso coprire Hashtable in uno successivo.
Buona domanda. Probabilmente non avrei mai cercato quel documento se non avessi postato questa domanda. –