w tym poście zobaczymy, jak HashSet działa wewnętrznie w Javie, co jest również ulubionym pytaniem z wywiadem o Kolekcjejava Collections, ale przed przejściem do wewnętrznej implementacji HashSet w Javie ważne jest, aby znać dwa punkty na temat HashSet.
- HashSet w Javie przechowuje tylko unikalne wartości, tzn. duplikaty nie są dozwolone.
- HashSet działa na koncepcji hashowania tak jak w Javie, ale jego działanie różni się od Hashmapy w następujący sposób-
- w Hashmapie dodawana jest para (klucz, wartość) i funkcja hash jest obliczana za pomocą klucza.
- gdzie podobnie jak w funkcji HashSet obliczana jest przy użyciu samej wartości. Zauważ, że w Hashsecie mamy metodę add(E e), która pobiera tylko element, który ma być dodany jako parametr.
również można się już domyślić, ponieważ funkcja hash jest obliczana na podstawie wartości, dlatego tylko uniquevalues są przechowywane w zestawie Hash. Jeśli spróbujesz ponownie zapisać ten sam element, obliczona funkcja skrótu będzie taka sama, więc element zostanie nadpisany.
HashSet wewnętrznie używa HashMap
teraz wracając do wewnętrznej implementacji HashSet w Javie najważniejszym punktem jest Implementacja klasy HashSet wewnętrznie używa HashMap do przechowywania swoich elementów.
w zestawie HashSet jest wiele konstruktorów jeden bez żadnego parametru i kilka innych z początkową pojemnością lub współczynnikiem obciążenia, ale każdy z tych konstruktorów tworzy Hashmapę.Ponieważ HashSet wewnętrznie używa Hashmapy, wiedza o tym, jak Hashmapy działają wewnętrznie w Javie, pomoże Ci zrozumieć, jak HashSet działa wewnętrznie w Javie.
fragmenty konstruktora HashSet
w klasie HashSet w Javie widać, że konstruktory klasy tworzą Hashmapę.
/*** Constructs a new, empty set; the backing <tt>HashMap</tt> instance has* default initial capacity (16) and load factor (0.75).*/public HashSet() { map = new HashMap<>();}
public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor);}
a mapa, która służy do przechowywania wartości, jest zdefiniowana jako
private transient HashMap<E,Object> map;
w konstruktorze, jeśli zauważyłeś, są parametry o nazwie pojemność początkowa i współczynnik obciążenia.Dla Hashsetu domyślna pojemność początkowa wynosi 16, czyli zostanie utworzona tablica (lub wiadro) o długości 16, A domyślny współczynnik obciążenia wynosi 0,75. Gdzie współczynnik obciążenia jest miarą tego, jak pełna może być tabela skrótu, zanim jego pojemność zostanie automatycznie zwiększona.
jak dodawane są elementy – wewnętrzna implementacja HashSet
w punkcie 2 powyżej stwierdziłem, że HashSet oblicza funkcję skrótu używając samej wartości i nie ma pary (klucz, wartość) w HashSet, a następnie pojawiło się oświadczenie, że HashSet wewnętrznie używa HashMap do przechowywania obiektów.Te dwa stwierdzenia mogą brzmieć sprzecznie jako pary sklepów HashMap (klucz, wartość), więc zobaczmy, jak te dwa wyrażenia kontradyktoryjne są prawdziwe.
w rzeczywistości z add Metoda klasy HashSet wywołana jest metoda put () HashMap, gdzie wartość, która ma być ustawiona w zbiorze, staje się kluczem, a jako wartość używany jest stały obiekt „PRESENT”.
tak definiuje się PRESENT w implementacji HashSet-
// Dummy value to associate with an Object in the backing Mapprivate static final Object PRESENT = new Object();
w ten sposób Metoda add jest zaimplementowana w klasie HashSet-
public boolean add(E e) { return map.put(e, PRESENT)==null;}
możesz więc zobaczyć, że w wewnętrznej implementacji zestawu HashSet jest to para (klucz, wartość), która faktycznie otrzymuje added.It po prostu rzeczywista wartość (która jest dodawana do zestawu HashSet) staje się kluczem, a obojętna wartość „obecna” jest dodawana jako wartość podczas zapisywania jej na podkładowej mapie HashMap.
na przykład polecenie dodawania elementu do HashSet – set.add („Bombaj”); wewnętrznie przekłada się na mapę.put („Bombaj”, obecny); a następnie dodano do kopii instancji HashMap.
należy tutaj zauważyć, że wartość w Hashmapie może być duplikatem, ale klucz powinien być unikalny. W ten sposób HashSet zapewnia, że przechowywane są w nim tylko unikalne wartości, ponieważ wartość, która ma być przechowywana w HashSetbecomes klucz podczas przechowywania go w HashMap.
jak element jest usuwany-wewnętrzna implementacja HashSet
kiedy musimy usunąć element z HashSet, wewnętrznie ponownie Usuń metodę HashSetcalls Usuń (Object key) metodę Hashmapy.
tak jest zaimplementowana w klasie HashSet.
public boolean remove(Object o) { return map.remove(o)==PRESENT;}
tutaj zauważ, że metoda remove(Object key) z Hashmapy Zwraca wartość powiązaną z kluczem.Natomiast metoda remove (Object o) W Zestawie HashSet Zwraca wartość logiczną. Wiemy również, że dla każdej valueadded w HashSet, wewnętrznie, gdy jest dodawany do powiązanej Hashmapy, wartość staje się kluczem, a wartością jest zawsze obiekt o nazwie PRESENT. Dlatego wartość, która zostanie zwrócona z metody remove (Object key) Hashmapy jest zawsze obecna, a więc mapa warunków.remove (o) = = PRESENT.
jak elementy są pobierane z zestawu HashSet w Javie
w zestawie HashSet nie ma metody get, jak podano na mapie lub liście. W HashSet iterator jest tam, który będzie iteratethrough wartości zestawu. Wewnętrznie wywoła zestaw kluczy Mapy Hashmapy, ponieważ wartości są przechowywane jako klucze na mapie Hashmapy, więc otrzymamy wartości przechowywane w zestawie HashMap.
w ten sposób iterator jest wewnętrznie zaimplementowany w zestawie HashSet w Javie.
/*** Returns an iterator over the elements in this set. The elements* are returned in no particular order.** @return an Iterator over the elements in this set* @see ConcurrentModificationException*/public Iterator<E> iterator() { return map.keySet().iterator();}
zwraca uwagę
- w przeciwieństwie do HashMap, gdzie funkcja skrótu jest obliczana za pomocą klucza HashSet używa samej wartości do obliczenia funkcji skrótu.
- ponieważ funkcja hash jest obliczana na podstawie wartości, dlatego tylko unikalne wartości są przechowywane w zestawie Hash.
- HashSet wewnętrznie używa HashMap do przechowywania swoich elementów.
- gdy element zostanie dodany do Hashsetu za pomocą metody add(E e) wewnętrznie HashSet wywołuje metodę put() Mapy Hashmapy, gdzie wartość przekazana w metodzie add staje się kluczem w metodzie put (). Wartość pozorna „PRESENT”jest przekazywana jako wartość w metodzie put ().
zalecenia dotyczące Nauki (Kursy Udemy)
- Kurs Java Programming Masterclass
- Java In-Depth: Zostań kompletnym inżynierem Java!
- Spring Framework Master Class Course
- Complete Python Bootcamp Course
- Python for Data Science and Machine Learning
to wszystko na ten temat jak HashSet działa wewnętrznie w Javie. Jeśli masz jakiekolwiek wątpliwości lub sugestie, aby dodać komentarz. Dzięki!
Tematy pokrewne
- jak ArrayList działa wewnętrznie w Javie
- jak HashMap działa wewnętrznie w Javie
- jak LinkedList Class działa wewnętrznie w Javie
- LinkedHashSet w Javie z przykładami
- TreeSet w Javie z przykładami
możesz też polubić-