SO-1st-2.3-w9.tresc-1.0-Slajd23
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
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.
