Big-O - Um einem HashSet ein Element hinzuzufügen, ist die Komplexität O (1), und wie bestimmt ein HashSet, ob das hinzuzufügende Element eindeutig ist oder nicht? DieseWenn Hashset 'add' Komplexität ist O (1), wie einzigartige Elemente gespeichert werden?
hängt von der Wahl der Hash-Tabelle, aber in den meisten traditionellen Implementierungen von Hash-Tabellen (lineare Sondieren, angekettet Hashing, quadratische Sondierung, etc.) die Kosten für eine Insertion tun ist auf Erwartung O (1) eher als worst-case O (1). Der O (1) -Term kommt hier aus der Tatsache, dass im Durchschnitt im Durchschnitt nur eine konstante Anzahl von Elementen in der Hash-Tabelle beim Einfügen eines neuen Wertes betrachtet werden muss. Beim linearen Sondieren geschieht dies, weil die erwartete Länge des Laufs der zu überprüfenden Elemente O (1) ist, und bei verkettetem Hashing liegt es daran, dass nur erwartete O (1) -Elemente in dem betreffenden Bucket vorhanden sind. Die Hash-Tabelle kann dann prüfen, ob das neu eingefügte Element einem dieser Werte entspricht, wenn eine Einfügung durchgeführt wird. Wenn ja, wissen wir, dass es ein Duplikat ist. Wenn nicht, wissen wir, dass das neue Element kein Duplikat sein kann. Wir haben jedes Element überprüft, das möglicherweise gleich sein könnte. Das bedeutet, dass im Durchschnitt die Kosten einer Einfügung O (1) und wir zum Zeitpunkt der Insertion auf Eindeutigkeit prüfen können.
Fragen Sie über Hash-Tabelle Datenstruktur im Allgemeinen oder über bestimmte Implementierung? Und es gibt keine Magie, die Einfügeoperation in eine Hashtabelle ist im schlimmsten Fall nicht "O (1)". https://en.wikipedia.org/wiki/Hash_table – DAle