"Well, how is your processor?"
"It's OK. I sat in liquid nitrogen for an hour, so now I'm as good as new!"
"Great. Then let's continue."
Mathematically speaking, a set is a group of unique elements. Thus, in programming, a Set is a collection of unique elements, i.e. a collection that doesn't let you store identical elements.
"I don't know if Ellie showed you Set's inheritance hierarchy. If not, here it is:"
"A HashSet is a collection that store elements internally using the hash values returned by the hashCode() method."
"For simplicity, HashSet<E> stores a HashMap<E, Object> object that stores the HashSet's values as keys."
"Using hash codes lets you quickly search for, add, and remove elements from the Set."
"But keep in mind that your class must properly implement the hashCode & equals methods in order to add objects of your classes to a Set, and to correctly find them there."
"Both methods are used a lot inside HashSet/HashMap."
"If you forget to implement the hashCode() method, then you risk not being able to find your object in the Set, even if it is present."
"Yes, I remember, I remember. You told me about this earlier. I've heard all about it."
"OK. Then here's some more useful information for you."
"Suppose you've correctly implemented hashCode and equals in your class, and you happily store your objects in a Set."
"But then you go and change one of the objects, and by so doing you change the internal data used to calculate its hash. So the object's hash changes."
"And this means that when you search for it in the Set, you probably won't find it."
"Whoa! How does that work?"
"This is a well-known pitfall when working with hashes. Essentially, HashSet (and HashMap) searches are only guaranteed to work properly if the objects are immutable."
"Whoa! And what, no one does anything about it?"
"Everyone pretends that the problem doesn't exist. But this frequently comes up in interviews, so it may be worth remembering…"
"A LinkedHashSet is a HashSet whose elements are also stored in a linked list. Normal HashSets don't support ordering of the elements. First, it simply isn't an official operation. Second, even the internal order can change significantly when a single element is added."
But you can get an iterator from a LinkedHashSet and use it to go through all of the elements in the order they were added to the LinkedHashSet. It doesn't happen often, but sometimes this is very much needed."
"I see. I love when classes exist for these «just in case» scenarios. Such cases aren't all that rare."
"TreeSet is a collection that stores elements in the form of a tree ordered by values. A TreeSet<E> contains a TreeMap<E, Object> that stores all of these values. And this TreeMap uses a balanced red-black tree to store elements. As a result, it supports very fast add, remove, and contains operations."
"Yes, I remember. We discussed that just recently. And I also thought about where this is used."
"And it turns out that some of Java's most popular collections use it."
"Yep. By the way, interviewers often ask about TreeSet. They're usually trying to trick you. They'll say, 'if a TreeSet uses a binary tree, then all elements can form one long branch, so searches will take a long time. «This is just the time to put the insolent fellow in his place by stating, "Even a child knows that TreeSet and TreeMap use balanced red-black trees, so that situation is actually impossible.»"
"Ah. I'd love to see the face of the person who asked that question. I might even memorize that phrase. …"
"But in practice, Set turned out to not be as simple as I initially thought."
"On the other hand, the situation with Queue is much simpler:"
"Queue implements a queue. Elements are added to the end of the queue and taken from the front."
"PriorityQueue is actually the only classic implementation of the Queue interface, not counting LinkedList, which technically is also a queue."
"Okay, I'm getting tired. That's all for today. Until next time."
GO TO FULL VERSION