Algorytmy i struktury danych · Senior · Pytanie 54 z 75
Jaka jest oczekiwana liczba porównań przy udanym wyszukiwaniu w tablicy haszującej z łańcuchami i współczynnikiem wypełnienia α?
- 1Dokładnie α²
- 2Około log α
- ✓Poprawna odpowiedź: Około 1 + α/2
Wyjaśnienie
Przy równomiernym haszowaniu łańcuch ma średnio α elementów, a udane wyszukiwanie przegląda mniej więcej połowę. Dlatego tablice trzymają α poniżej stałej, np. 0.75: wyszukiwanie zajmuje kilka porównań.