Z czego składa się tabela haszująca?

Tablica haszująca składa się z tablicy o stałym rozmiarze (wiadro lub slot) oraz funkcji haszującej.

• Tablica (wiadra/sloty): Reprezentuje ciąg komórek, w których przechowywane są pary "klucz-wartość". Rozmiar tablicy określa liczbę możliwych miejsc do przechowywania elementów.

• Funkcja haszująca: Zamienia klucz na wartość całkowitą (kod haszujący), która jest używana do określenia indeksu komórki w tablicy (wiadro), w której będzie przechowywana lub z której będzie wyodrębniana odpowiednia wartość.

Dodatkowo, może występować:

• Strategia rozwiązywania kolizji: Mechanizm obsługi sytuacji, gdy różne klucze generują ten sam kod haszujący i wskazują na tę samą komórkę tablicy. Popularne strategie:
  • Łańcuchowanie (Separate Chaining): Każda komórka tablicy przechowuje wskaźnik na listę powiązaną (lub inną strukturę danych), zawierającą wszystkie pary "klucz-wartość", których kody haszujące wskazują na tę komórkę.
  • Adresowanie otwarte: W przypadku kolizji, poszukuje się wolnej komórki w tablicy według określonej reguły (np. liniowe lub kwadratowe sondowanie).