Znaczenie haszowania otwartego i haszowania zamkniętego

Otwarte haszowanie (oddzielne łańcuchowanie):

W otwartym haszowaniu klucze są przechowywane na połączonych listach dołączonych do komórek tabeli skrótów.

Closed Hashing (Open Addressing):

W zamkniętym haszowaniu wszystkie klucze są przechowywane w samej tablicy skrótów bez użycia połączonych list.

Nie jestem w stanie zrozumieć, dlaczego nazywają się otwartymi, zamkniętymi i osobnymi. Czy ktoś może to wyjaśnić?

Użycie „zamkniętych” kontra „otwartych” odzwierciedla, czy jesteśmy uwięzieni w używaniu określonej pozycji lub struktury danych (jest to bardzo niejasny opis, ale mam nadzieję, że reszta pomoże).

Na przykład „otwarte” w „otwartym adresowaniu” informuje nas, że indeks (czyli adres), pod którym obiekt będzie przechowywany w tablicy skrótów, nie jest całkowicie określony przez jego kod skrótu. Zamiast tego indeks może się różnić w zależności od tego, co już znajduje się w tabeli skrótów.

Określenie „zamknięte” w „zamkniętym haszowaniu” odnosi się do faktu, że nigdy nie opuszczamy tablicy mieszania; każdy obiekt jest przechowywany bezpośrednio w indeksie w wewnętrznej tablicy tablicy skrótów. Należy pamiętać, że jest to możliwe tylko przy użyciu jakiejś otwartej strategii adresowania. To wyjaśnia, dlaczego „zamknięte hashowanie” i „otwarte adresowanie” są synonimami.

Porównaj to z otwartym haszowaniem - w tej strategii żaden z obiektów nie jest faktycznie przechowywany w tablicy tablicy mieszającej; zamiast tego po zahaszowaniu obiektu jest on przechowywany na liście, która jest oddzielona od wewnętrznej tablicy tablicy skrótów. „open” odnosi się do wolności, jaką uzyskujemy opuszczając tablicę skrótów i używając oddzielnej listy. Nawiasem mówiąc, „oddzielna lista” wskazuje, dlaczego otwarte haszowanie jest również znane jako „oddzielne łączenie łańcuchowe”.

Krótko mówiąc, „zamknięte” zawsze odnosi się do pewnego rodzaju ścisłej gwarancji, na przykład gdy gwarantujemy, że obiekty są zawsze przechowywane bezpośrednio w tablicy mieszania (zamknięte hashowanie). Wówczas przeciwieństwem słowa „zamknięte” jest „otwarte”, więc jeśli nie masz takich gwarancji, strategia jest uznawana za „otwartą”.

Masz tablicę, która jest „tablicą skrótów”.

W Open Hashing każda komórka w tablicy wskazuje na listę zawierającą kolizje. Haszowanie wygenerowało ten sam indeks dla wszystkich elementów na połączonej liście.

W Closed Hashing używasz tylko jednej tablicy do wszystkiego. Przechowujesz kolizje w tej samej tablicy. Sztuczka polega na tym, aby użyć inteligentnego sposobu, aby przeskoczyć od kolizji do kolizji, gdy znajdziesz to, czego chcesz. I zrób to w powtarzalny / deterministyczny sposób.

Nazwa otwartego adresowania odnosi się do faktu, że lokalizacja („adres”) elementu nie jest określona przez wartość skrótu. (Ta metoda jest również nazywana zamkniętym haszowaniem).

W oddzielnym łańcuchu każdy zasobnik jest niezależny i ma jakiś rodzaj ADT (listy, drzewa wyszukiwania binarnego itp.) Wpisów o tym samym indeksie. W dobrej tablicy haszującej każdy zasobnik ma zero lub jeden wpis, ponieważ potrzebujemy operacji rzędu O (1) do wstawiania, wyszukiwania itp.

Jest to przykład z oddzielnym łańcuchowych za pomocą C ++ dzięki prostej funkcji mieszającej za pomocą operatora mod (Oczywiste jest, że złe funkcja hash)