Hashtable kolizja rehashing - jak czytać wartości?

Question

Próbuję zrozumieć, jak Hashtables działają w języku C#. Przeczytałem artykuł MSDN i rozumiem, że C# Hashtables używa 'rehashing' dla kolizji, tj. Jeśli spróbuję wstawić parę klucz/wartość do tablicy, jeśli użycie HashFunction H1 spowoduje kolizję, to spróbuje HashFunction H2, H3 itd., dopóki nie zostaną znalezione żadne kolizje.

MSDN cytat:

Hashtable klasa wykorzystuje inną technikę zwaną rehasing. (Niektóre źródła odnoszą się do hashuje jako podwójne mieszaja.)

prace hashuje następująco: jest to zbiór różnych hash funkcji, H1 ... Hn, a podczas wkładania lub pobierania elementu z tabeli mieszania, początkowo używana jest funkcja skrótu H1. 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ólnym funkcja mieszająca Hk jest zdefiniowany jako:

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

Jednakże, biorąc przykład z site1 MSDN:

private static Hashtable employees = new Hashtable(); 

public static void Main() 
{ 
    // Add some values to the Hashtable, indexed by a string key 
    employees.Add("111-22-3333", "Scott"); 
    employees.Add("222-33-4444", "Sam"); 
} 

Załóżmy, że dodanie drugiego klawisza spowoduje kolizji, więc H2 będą musiały być używany. Jednak, kiedy dzwonię do pracowników ["222-33-4444"], w jaki sposób hakowiec wie, jak używać H2? Czy istnieje oddzielne mapowanie? Dzięki.

Answer 1

tabele Hash przechowywać zarówno klucz i wartość w samej tabeli mieszania. W ten sposób podczas późniejszych operacji, takich jak wyszukiwanie tabel mieszania, można zagwarantować, że znaleziona wartość będzie zgodna z indeksem użytym do wyszukiwania. Tabele skrótu używają prostej metody "spróbuj podstawowej metody sprawdzania aż do sukcesu". W tym przypadku metodą wyszukiwania jest "użyj funkcji mieszania X", w której X zmienia się po awarii.

W innych schematach metodą wyszukiwania jest "spójrz na wpis w tablicy X" (określony przez funkcję skrótu), gdzie X zwiększa się o jeden po każdym niepowodzeniu w sposób zawijania.

Nurtujące pytanie brzmi teraz, co dzieje się, gdy wartość NIE JEST w tabeli? Cóż, może to być dość brzydkie: gdy trafisz na wpis w tabeli, którego brakuje, lub, co gorsza, gdy wykonujesz iterację przez tyle wpisów, ile jest przechowywanych w tabeli, możesz być pewny, że wpis nie jest prawidłowy. tam - ale w najgorszym przypadku może to zająć trochę czasu.

Należy pamiętać, że ponieważ z jednym kluczem można powiązać tylko jedną wartość, po znalezieniu klucza można znaleźć wartość. Najgorszą tabelą mieszającą może być wykonanie odpowiednika niepoprawnej pamięci podręcznej liniowej przeszukiwania wszystkich wartości w tabeli mieszania ... ale ostatecznie, znajdzie wartość, jeśli jest tam, ponieważ porównuje przechowywany klucz do żądany klucz do sprawdzenia, czy jest tam. Jedyne bloki optymalizacji z zamkniętymi tablicami mieszającymi to gdzie najpierw szukać - w tym przypadku, gdzie funkcja hash 1 mówi, a następnie 2, a następnie 3 ...

Answer 2

Najpierw spróbuje H1. Jeśli nie znajdzie dopasowania, użyje H2. I tak dalej.

Answer 3

Myślę, że źle rozumiesz rehashing. Jest tylko jedna funkcja skrótu: wirtualna object.GetHashCode() (lub, jeśli dostarczasz IHashCodeProvider lub IEqualityComparer, używa tego obiektu do obliczenia kodu skrótu). Gdy tabela mieszania jest pełna, rozszerza swoją pojemność i redystrybuuje elementy na nowych, większych tablicach. Prywatna metoda, która to robi nazywa się Rehash(), ale nie oblicza ponownie kodów skrótu.

KOREKTA

hashuje nie wykorzystuje nową funkcję, lecz działa na poprzedniej wartości kodu skrótu; powoduje to przeszukanie kolejnych szczelin do momentu znalezienia pustego (dla wstawienia/ustawienia) lub do momentu, aż wszystkie klucze z tym samym (początkowym) kodem haszowania zostaną sprawdzone pod kątem równości z kluczem indeksu (dla wyszukiwania).

EDIT

Aby odpowiedzieć na to pytanie wprost:

Załóżmy, że dodanie drugiego klawisza spowoduje kolizji, więc H2 będą musiały być użyte. Jednak, kiedy dzwonię do pracowników ["222-33-4444"], w jaki sposób hakowiec wie, jak używać H2? Czy istnieje oddzielne mapowanie? Dzięki.

1. Oblicz poprawną wiadro oparciu o kod hash przekazany klucz.
2. Jeśli to wiadro jest puste, zawieść.
3. Jeśli klucz kubełkowy pasuje do przekazanego klucza, należy zwrócić wartość kubełka.
4. Jeśli licznik kolizji skrótu wynosi zero, oznacza to niepowodzenie.
5. Obliczyć następny kod skrótu z bieżącego kodu skrótu.
6. Oblicz właściwą łyżkę na podstawie nowego kodu skrótu.
7. przejdź do kroku 2.