Sets Flashcards
Is a HashSet a good choice for finding out if an array has any duplicates?
Yes because a HashSet has only unique keys, so if you try to add a duplicate value to a set it will return false
What is the most common implementation of the Set interface?
Hash Set
What is the time complexity of Hash Set add, remove, contains operations
O(1)
What is the time complexity of Tree Set add, remove, contains operations
O(log n)
When is a Hash Set a good choice?
When you don’t want to maintain the order
When is Tree Set a good choice?
When you want to sort the elements according to some comparator
What is a Tree Set
Parent and children nodes, ordered using red-black algorithm (which is a self balancing binary search tree)
What is a Linked HashSet
It is between as Hash Set and Tree Set and is a doubly-linked list implementation of a Hash Set
What is a set?
A set unique set of keys
What are the 4 key characteristics of a Tree Set?
- sorts elements in ascending order
- does not maintain insertion order
- unique values
- not thread safe
When should you use a HashSet instead of a TreeSet
When you care about performance (speed) and not order.
A TreeSet is slower as it has to sort the elements after each insertion/deletion
What is the time complexity of add, remove, contains for LinkedHashSet?
O(1)
How does a Tree Set compare elements?
Using the compareTo method by implementing the Comparable interface
Can a TreeSet have a null element?
No, it will throw a null pointer exception
Can a HashSet or LinkedHashSet store null values?
Yes, a max of one null value because all elements are unique
