Witam wszystkich.
Zabieram sie za pisanie programu który ma na celu implementacje tablic mieszających z wykorzystaniem funkcji mieszających przy podanym słowniku który składa sie z kilkunastu słów
Zanim zaczne chciałbym sie Was poradzić czy moje rozumowanie jej prawidłowe, mianowicie każde słowo ze słownika w postaci string'a przepuścić przez podaną funkcje mieszającą która oblicza index do tego wyrazu, następnie słowo z obliczonym indexem zapisać do tablicy?
Z góry dzięki za odp.
Mniej wiecej ok. Liczysz ze stringa index i zapisujesz cos tam pod tym indeksem odwolujac sie za pomoca stringa przepuszczonego przez ta funkcje zwracajaca index. Tylko wez pod uwage, ze dla kilku roznych stringow index moze wyjsc ten sam przy slabej funkcji hashujacej.
t0m_k napisał(a)
Tylko wez pod uwage, ze dla kilku roznych stringow index moze wyjsc ten sam przy slabej funkcji hashujacej.
Czyli tzw. kolizje? Jest jakiś sposób na rozwiązywanie kolizji czy zależy to tylko od skuteczności funkcji haszującej, np. sprawdzanie czy dany index sie powtarza, jeśli tak to znalezienie wolnego numeru?
Sposob poradzenia sobie z kolizjami zalezy od implementacji tej tablicy. Na przyklad mozesz miec na liscie ja zrobiona, wiec mozesz trzymac w kazdym elemencie listy wskaznik do elementow kolejnych dla, ktorych hash jest ten sam. W Twoim przypadku dla malej ilosci danych moze byc to dobry sposob, ale juz dla duzej ilosci danych nie polecam.
Oczywiscie samo wystepowanie kolizji zalezy tylko od funkcji hashujacej.