Jaki typ rozdzielczości kolizji został wybrany dla implementacji HashTable/Dictionary w .net?

Question

Jak wiemy, istnieją 2 klasyczne strategie rozwiązywania kolizji: Oddzielne łańcuchy i Otwarte adresowanie.

Zastanawiam się, który został wybrany dla HashTable/Dictionary w .net.

Czy zastosowano inną strategię?

Answer 1

To wszystko jest opisane w niniejszym opracowaniu na MSDN: An Extensive Examination of Data Structures Using C# 2.0

... kolizja technika zwana rehasing rozdzielczości, która jest techniką wykorzystywane przez klasy Hashtable ramową w .NET. W końcowej sekcji zajmiemy się klasą Dictionary, która używa techniki kolizji znającej łańcuch. ....

... Rehasing działa w następujący sposób: jest to zestaw hash różnych funkcji, H1 ... Hn, a podczas wkładania lub pobierania elementu z tabeli mieszania, początkowo hash H1 funkcja jest używana. Jeśli doprowadzi to do kolizji, zamiast tego zostanie wypróbowana metoda H2, aw razie potrzeby zostanie zwiększona do wartości Hn. W poprzedniej sekcji pokazano tylko jedną funkcję skrótu, która jest początkową funkcją haszującą (H1) . Pozostałe funkcje skrótu są bardzo podobne do tej funkcji, różnicując je tylko przez współczynnik multiplikatywny. W ogóle, funkcja skrótu Hk jest zdefiniowany jako:

Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize 

Dictionary grupa różni się od Hashtable klasie sposobów więcej niż jeden. Oprócz tego, że słownik jest silnie napisany, słownik używa także innej strategii rozwiązywania kolizji niż klasa Hashtable , stosując technikę zwaną łańcuchem. Przypomnij sobie, że przy sondowaniu , w razie kolizji wypróbowane jest inne miejsce na liście łyżek . (Po ponownym wprowadzeniu skrótu hasz zostanie ponownie obliczony i zostanie wypróbowany nowy slot.) Jednak przy łańcuchowaniu wykorzystywana jest drugorzędna struktura danych do przechowywania kolizji. Konkretnie, każde gniazdo w Słowniku ma tablicę elementów, które są odwzorowane na to wiadro. W zdarzeniu kolizji element kolizyjny jest dodawany do listy wiaderek .

Pamiętaj tylko pierwsze zdanie jest moja własna :-)

Answer 2

To rzeczywiście bardzo ciekawe pytanie; Właśnie zrobiłem blog post o tym, jak Dictionary zaimplementowano za kulisami. Mogę pokryć Hashtable w późniejszym.