Tablice haszujące (pomoc w zadaniu)

Question

Witam wszystkich. Przygotowuję się do egzaminu z algorytmów i chciałem się upewnić czy dobrze rozumiem tablice haszujace. Może ktoś podpowiedzieć czy dobrze rozwiązałem zad 3 ewentualnie skorygować. Z góry dzięki Treść - https://drive.google.com/file/d/0B3KtZH0UJ5fRU09iNDFySEtzV3M/view?usp=drivesdk Rozwiązanie - https://drive.google.com/file/d/0B3KtZH0UJ5fRc2FpOVZlY1FOdms/view?usp=drivesdk

Answer 1

Cześć,

​Wydaje mi się, że źle obliczyłeś Hashowanie podwójne:
​H(x, k) = (h1(x) + (h2x) * k) mod n, gdzie n - ilość elementów, x - element, k - domniemana pozycja elementu x
Z: http://smurf.mimuw.edu.pl/node/334

Według tego, tablica a) powinna wyglądać:
0) ?
1) X
2) X
3) X
4) X
5) X
​6) 6
7) ?
​8) ?

Dodam, że nie znam się na hashowaniu podwójnym, ale z tego co przeczytałem na: http://smurf.mimuw.edu.pl/node/334 wydaje mi się, że dobrze to policzyłem.

​Pozdrawiam,
Tomek

Comments

Ok, dziękuję za odpowiedź. Zastanawia mnie tylko ten X. W treści jest napisane, że stawiamy go jak komórka jest zajęta i nie ma tam klucza 6. Do tego pierwszego nie mam wątpliwości ale skąd pewność że nie ma tam takiego samego klucza?

---

Cześć,

​Klucz powinien być unikalny, wartość już nie musi być unikalna (na początku było napisane "wstawiono klucz 6"), więc nie może się powtórzyć.

Przykład:
​Mamy dwa te same klucze, jeden za drugim, kiedy będziemy chcieli zmienić wartość pod danym kluczem lub sprawdzić jego zawartość, nigdy nie będziemy mieć dostępu do drugiego klucza, ponieważ znajduje się on za pierwszym, na którym to zakończy się algorytm przeszukiwania (oraz sprawdzania kolizji).

​Pozdrawiam,
Tomek

---

Dzięki wielkie, teraz wszystko jasne. Niby to oczywiste ale bez Twojej pomocy bym tego nie załapał. W drugiej tabeli dodajemy wynik funkcji do klucza później mod n i kolizje rozwiązujemy po przez przejście do następnej komórki?