Podstawowy algorytm Hashtable - usuwanie duplikatów

Question

Właśnie miałem wywiad dziś rano i otrzymałem pytanie "Podaj algorytm usuwania duplikatów z listy liczb całkowitych". Jest to dość standardowe pytanie, więc byłem pewny, że mogę na nie odpowiedzieć.

Jestem parafrazą, ale powiedziałem coś w stylu "Można użyć hashtable." Zacznij od pierwszej liczby całkowitej i wstaw ją do tablicy, a następnie dla każdej kolejnej liczby całkowitej wykonaj wyszukiwanie hashtable, aby sprawdzić, czy liczba całkowita jest już w hashtable, jeśli nie, włóż go, jeśli już tam jest, a następnie wyrzuć go, ponieważ jest duplikatem.Tak więc iteracji w liście w ten sposób.Jeśli hashtable jest zaprojektowany poprawnie, odnośniki i wkładki powinny być stały czas na średni."

Następnie ankieter odpowiedział (znowu jestem parafrazując) „Ale Hashtable wyszukiwań nie są stałe czas, zależą od tego, ile elementy są już w nim. Algorytm opisałeś byłoby O (n^2)”

Następnie odpowiedziałem: "Naprawdę? Myślałem, że jeśli zaprojektowałeś dobrą funkcję mieszającą, byłby to stały czas? Wykonywanie O (n) zwykle"

Następnie ankieter odpowiedział "Więc mówisz, że czas wyszukiwania byłby taki sam dla tabeli mieszania z wieloma wpisami i hashtable z kilkoma wpisami "

Potem powiedziałem:" Tak. t zostało zaprojektowane poprawnie. "

Następnie ankieter powiedział: „To nie jest prawda”

więc jestem bardzo mylić teraz. Jeśli ktoś może wskazać, gdzie się mylę, będę bardzo wdzięczny

Answer 1

jeśli ktoś może wskazać, gdzie się mylę

nie są złe w ogóle: odpowiednio zaprojektowane stoły hash daje oczekiwana skuteczność wyszukiwania O(1) i wstawki w amortyzowanym O(1), więc Twój algorytm to O(N). Wyszukiwanie w mocno obciążonych tabelach mieszających jest rzeczywiście nieco wolniejsze z powodu możliwej powielonej rozdzielczości, ale oczekiwany czas wyszukiwania pozostaje O(1). Może to nie być wystarczająco dobre dla systemów czasu rzeczywistego, w których "amortyzacja" się nie liczy, ale we wszystkich praktycznych sytuacjach to wystarcza.

Oczywiście zawsze można użyć zbalansowanego drzewa dla przedmiotów, które widziałeś dla najgorszego przypadku, algorytmu O(N*LogN), lub jeśli liczby mają rozsądne granice (np. Od 0 do 100 000), możesz użyć tablicy boolowskiej przetestować członkostwo w najgorszym przypadku i potencjalną poprawę w porównaniu z tablicą asocjacyjną ze względu na mniejszy stały mnożnik.