v tomto příspěvku uvidíme, jak HashSet interně funguje v Javě, což je také oblíbená otázka rozhovoru s kolekcemi, ale než se pustíme do interní implementace HashSet v Javě, je důležité vědět dva body o HashSet.
- HashSet v Javě ukládá pouze jedinečné hodnoty, tj.
- HashSet pracuje na konceptu hašování stejně jako HashMap v Javě, ale jeho práce se liší od HashMap následujícím způsobem –
- v HashMap je přidán pár (klíč, hodnota) a hašovací funkce je vypočtena pomocí klíče.
- kde stejně jako v HashSet hashovací funkce se vypočítá pomocí samotné hodnoty. Všimněte si, že v HashSet wehave add (E e) metoda, která bere jen prvek, který má být přidán jako parametr.
také jste možná uhodli, protože hašovací funkce je vypočtena pomocí hodnoty, proto jsou v Hashsetu uloženy pouze uniquevalues. Pokud se pokusíte uložitstejný prvek znovu, vypočtená hashovací funkce by byla stejná, takže prvek bude přepsán.
HashSet interně používá HashMap
nyní se vrací k interní implementaci HashSet v Javě nejdůležitějším bodem je implementace třídy HashSet interně používá HashMap k ukládání prvků.
v HashSet existuje mnoho konstruktorů jeden bez jakéhokoliv parametru a několik dalších s počáteční kapacity nebo zatížení faktor, ale každý z těchto konstruktoru vytvoří HashMap.Vzhledem k tomu, HashSet interně používá HashMap, takže vědět, jak HashMap pracuje interně v Javě vám pomůže pochopit, jak HashSet funguje interně v Javě.
fragmenty konstruktoru HashSet
ve třídě HashSet v Javě můžete vidět, že konstruktéři třídy vytvářejí 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, která se používá pro ukládání hodnot, je v konstruktoru definována jako
private transient HashMap<E,Object> map;
, pokud jste si všimli, existují parametry s názvem počáteční kapacita a faktor zatížení.Pro HashSet je výchozí počáteční kapacita 16, to je pole (nebo kbelík) délky 16 by bylo vytvořeno anddefault load factor je 0.75. Kde load factor je měřítkem toho, jak je plná tabulka hash povolena dříve, nežjeho kapacita se automaticky zvýší.
jak se přidávají prvky-HashSet interní implementace
v bodě 2 výše jsem uvedl, že HashSet vypočítá hašovací funkci pomocí samotné hodnoty a v HashSet neexistuje žádný pár (klíč, hodnota) a pak přišlo prohlášení, že HashSet interně používá HashMap k ukládání objektů.Tato dvě prohlášení mohou znít protichůdně, protože se HashMap ukládá (klíč, hodnota), takže se podívejme, jak tyto dvě protichůdné příkazy platí.
vlastně z add metody třídy HashSet put() se nazývá metoda HashMap, kde se hodnota, která musí být v sadě vložena, stává klíčem a jako hodnota se používá konstantní objekt „PRESENT“.
takto je PRESENT definován v implementaci HashSet-
// Dummy value to associate with an Object in the backing Mapprivate static final Object PRESENT = new Object();
a tak je metoda add implementována ve třídě HashSet –
public boolean add(E e) { return map.put(e, PRESENT)==null;}
takže můžete vidět, že v interní implementaci Hashsetu je to pár (klíč, hodnota), který se skutečně dostává added.It je to jen to, že skutečná hodnota (která je přidána do HashSet) se stává klíčem a fiktivní hodnota „přítomen“ je přidána jako hodnota whenstoring to v podkladové HashMap.
například příkaz pro přidání prvku do HashSet-set.přidat („Mumbai“); interně překládá do mapy.put („Mumbai“, současnost); a pak se přidá k podkladové instanci HashMap.
jedna věc, kterou je třeba poznamenat, je, že hodnota HashMap může být duplicitní, ale klíč by měl být jedinečný. Takto HashSet zajišťuje, že v něm jsou uloženy pouze jedinečné hodnoty, protože hodnota, která má být uložena v Hashsetse stává klíčem při ukládání do HashMap.
jak je element odstraněn-HashSet interní implementace
když potřebujeme Odstranit element z HashSet, interně znovu odebrat metodu HashSetcalls remove (Object key) metoda HashMap.
tak je implementován ve třídě HashSet.
public boolean remove(Object o) { return map.remove(o)==PRESENT;}
zde si všimněte, že metoda remove(Object key) HashMap vrací hodnotu přidruženou k klíči.Zatímco metoda remove (Object o) Hashsetu vrací Booleovskou hodnotu. Také víme, že pro každou hodnotupřidané v HashSet, interně, když je přidán do přidružené HashMap, hodnota se stává klíčem a hodnota je vždy anobject nazvaný přítomen. Proto je hodnota, která je vrácena z metody remove (Object key) HashMap vždy přítomna, tedy mapa podmínek.odebrat (o) = = přítomný.
jak jsou prvky načteny z Hashsetu v Javě
v Hashsetu neexistuje žádná metoda get, jak je uvedeno v mapě nebo seznamu. V HashSet iterátor je tam, který bude iterovatpřes hodnoty sady. Interně to bude volat keyset HashMap, protože hodnoty jsou uloženy jako keysin HashMap, takže to, co dostaneme, jsou hodnoty uložené v HashSet.
takto je iterator interně implementován v Hashsetu v Javě.
/*** 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();}
poukazuje na to,
- na rozdíl od HashMap, kde je hash funkce vypočtena pomocí klíče HashSet používá hodnotu sám pro výpočet hašovací funkce.
- protože hašovací funkce je vypočtena pomocí hodnoty, proto jsou v Hashsetu uloženy pouze jedinečné hodnoty.
- HashSet interně používá HashMap k ukládání svých prvků.
- když je prvek přidán do Hashsetu pomocí metody add (E e) interně HashSet volá metodu put () v HashMap, kde hodnota předaná v metodě add se stává klíčem v metodě put (). Fiktivní hodnota „PRESENT“ je předána jako hodnota v metodě put ().
doporučení pro učení (kurzy Udemy)
- Java programování Masterclass kurz
- Java in-Depth: Staňte se Kompletní Java inženýr!
- Spring Framework Master Class Course
- kompletní Python Bootcamp kurz
- Python pro Data Science a strojové učení
to je vše pro toto téma Jak HashSet pracuje interně v Javě. Máte-li jakékoli pochybnosti nebo jakékoli návrhy, prosím napište komentář. Díky!
Související témata
- jak ArrayList pracuje interně v Javě
- jak HashMap pracuje interně v Javě
- jak Třída LinkedList pracuje interně v Javě
- LinkedHashSet v Javě s příklady
- TreeSet v Javě s příklady
mohlo by se vám také líbit –