SOP wyk nr 9-Slajd22

Implementacja katalogu — tablica haszowa

Pozycja danego wpisu wyznaczana jest zgodnie z wartością funkcji haszującej dla nazwy danego pliku. Działanie przykładowej funkcji haszującej mogłoby polegać na zsumowaniu kodów znaków tworzących nazwę, a następnie wyznaczeniu wartości modulo liczba pozycji z tej sumy. Wykorzystując tę samą funkcję przy wyszukiwaniu wpisu, można go szybko zlokalizować. Funkcja haszująca nie gwarantuje unikalności (nie jest to funkcja różnowartościowa), należy się więc liczyć z konfliktami, gdy ta sama wartość zostanie wyznaczona dla dwóch różnych nazw. W zależności od sposobu rozwiązywania konfliktów, potrzebne mogą być dodatkowe struktury.

<< Poprzedni slajd | Spis treści | Następny slajd >>