BD-2st-1.2-w06.tresc-1.1-Slajd41

Funkcja haszowa

Dobra funkcja haszowa to taka, która odwzorowuje wartości kluczy rozłożone nierównomiernie w obrębie dużej dziedziny, w przestrzeń adresową rekordów o znacznie mniejszym rozmiarze w taki sposób, że wynikowe adresy są równomiernie rozłożone w obrębie przestrzeni adresowej tablicy haszowej.

Praktyka pokazuje, że tablica haszowa powinna być zajęta w 70 do 90%, tak aby zapewnić niewielką liczbę kolizji i nie powodować zbyt dużego marnowania obszaru dyskowego. Stąd zalecany rozmiar tablicy haszowej jest wyrażony wzorem

r/M between 0.7 and 0.9, gdzie r jest liczbą rekordów, a M jest liczbą szczelin adresowych tablicy haszowej.

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