Algorytmy i struktury danych · Middle · Pytanie 53 z 75
Co dzieje się z tablicą haszującą, gdy współczynnik wypełnienia jest za wysoki?
- ✓Poprawna odpowiedź: Powiększa tablicę i ponownie wstawia (przehaszowuje) wszystkie wpisy
- 2Przechodzi na posortowaną tablicę i wyszukiwanie binarne
- 3Odrzuca nowe klucze, dopóki jakieś nie zostaną usunięte
Wyjaśnienie
Współczynnik wypełnienia to liczba wpisów podzielona przez liczbę kubełków. Gdy przekroczy próg, kolizje są częste, więc tablica rośnie, zwykle dwukrotnie. Przehaszowanie to O(n), ale rzadkie, więc wstawianie pozostaje zamortyzowanie O(1).