Kiedy wstawiamy/szukamy klucz w tabeli mieszającej, podręcznik mówi, że jest to czas O (1). Jak jednak można uzyskać czas wyszukiwania O (1)? Jeśli tablica asocjacyjna zapisze klucz w wektorze, będzie kosztować O (N), jeśli w drzewie binarnym będzie to O (logN). Po prostu nie mogę obrazować struktury danych z czasem dostępu O (1).czas przeszukania tabeli mieszania
Dzięki!
Hafter haszy klucz i umieszcza go w tablicy.
Na przykład hash (x) = 3, gdzie x jest twoim kluczem. Tabela następnie umieszcza ją w tablicy [3]. Dostęp z tablicy to O (1).
Co najmniej tablice skrótów składają się z tablicy i funkcji skrótu. Gdy obiekt zostanie dodany do tabeli, funkcja skrótu jest obliczana na obiekcie i jest przechowywana w tablicy w indeksie odpowiedniej wartości, która została obliczona. np. jeśli hash(obj) = 2 to arr[2] = obj.
Średnia wstawka/odnośnik na tabeli mieszania to O(1).
Możliwe jest jednak zderzenie, gdy obiekty obliczają tę samą wartość skrótu.
W ogólnym przypadku są "wiaderka" w każdym indeksie tablicy, aby obsłużyć te kolizje. Oznacza to, że wszystkie trzy obiekty są przechowywane w innej strukturze danych (może połączonej liście lub innej tablicy) na indeksie tablicy mieszającej.
Dlatego najgorszy przypadek wyszukiwania na tablicy mieszającej to O(n), ponieważ możliwe jest, że wszystkie obiekty przechowywane w tabeli mieszającej zostały zderzone i są przechowywane w tym samym pojemniku.
Najgorszy przypadek wyszukiwania w tabeli mieszającej to 'O (n)'. Rozważ: 'hash (x) = 3',' hash (y) = 3' 'hash (z) = 3', etc etc –