Grupa: Administrator 
Posty: 31 #2745132
Od: 2018-12-15
|
Łańcuchy: powtarzające się kolizje tworzą dłuższe listy połączone, ale nie zajmują żadnych dodatkowych indeksów tablicy.
Sondowanie liniowe jest nadal proste w koncepcji, ale trudniejsze do wdrożenia. W sondowaniu liniowym każdy indeks w tablicy mieszającej jest nadal zarezerwowany dla pojedynczego elementu. Gdy kolizja występuje w indeksie i, sprawdzamy, czy indeks i + 1 jest pusty, a jeśli tak, przechowujemy tam nasze dane, jeśli i + 1 miał również element, zaznaczamy i + 2, potem i + 3 i tak dalej, aż znajdziemy puste miejsce. Jak tylko znajdziemy puste miejsce, wstawiamy wartość. Po raz kolejny wyszukiwania mogą już nie być ściśle stałym czasem, jeśli mamy kilka kolizji w jednym indeksie, będziemy musieli przeszukać długą serię elementów, zanim znajdziemy poszukiwany element. Co więcej, za każdym razem, gdy mamy kolizję, zwiększamy prawdopodobieństwo kolejnych kolizji, ponieważ (w przeciwieństwie do łańcuchów) przychodzący przedmiot ostatecznie zajmuje nowy indeks.
|
