Dev Learning Lab

The labs on this site need JavaScript to run. The same content is written out below.

Learn › Java › Collections

Kinds of Set and Map

Why do the same values come out in a different order?

A Set is a collection that holds each value only once, and a Map is a collection that holds keys paired with values. Each comes in three kinds, whose names start with Hash, LinkedHash, and Tree, and the kind you choose determines the order in which things come out and which values can go in.

Checked against real execution · Checked by running 30 combinations on JDK 21

Concepts in this lab

List, Set, Map
These are the three basic kinds of Java collections. A List is ordered, allows duplicates, and is accessed by index. A Set does not allow duplicates. A Map stores key-value pairs, and its keys cannot be duplicated. You choose among them by the nature of the data (whether order is needed, whether duplicates are allowed, and whether you look things up by key).
Hash table and HashMap
This data structure decides the storage location (bucket) of a key from the value that a hash function produces for that key. The location can be computed directly from the key alone, so lookup, insertion, and removal are O(1) on average. Java's HashMap has this structure; it does not guarantee order and is not thread-safe.
LinkedHashSet and LinkedHashMap
These are a HashSet and a HashMap that remember insertion order. They put entries into a hash table in the same way, but they also maintain a linked list that connects the entries in insertion order, so iteration returns them in insertion order. Re-inserting an element or a key that is already present does not change the position where it was first inserted. Insertion and lookup are O(1) on average, the same as HashMap, and maintaining the linked list takes a little more memory. They are used for lists that must be shown in insertion order.
TreeSet and TreeMap
These are a Set and a Map that always keep their elements (for TreeMap, the keys) in sorted order. Internally each is a red-black tree, and on every insertion the position is decided by comparing with compareTo (or with the Comparator given to the constructor), so iteration returns the smallest first. Insertion, lookup, and removal are all O(log n), which is slower than HashMap, but the smallest value or the range of values greater than or equal to some value can be obtained directly. If no Comparator was given, or the given Comparator does not permit null, inserting null throws a NullPointerException. If no Comparator was given, inserting an object that does not implement Comparable throws a ClassCastException. Whether two values are the same is decided by whether the comparison result is 0, not by equals.
Time complexity (big-O notation)
This notation shows how fast the number of operations of an algorithm grows as the input size n grows. O(1) means constant regardless of size, O(log n) means only one more step when the size doubles, O(n) means proportional to the size, and O(n²) means proportional to the square of the size. It is the basis for judging which approach holds up as the amount of data grows.

Try these

Running with the default settings

  1. Set<String> set = new HashSet<>(): Creates an empty HashSet. HashSet uses hashCode to compute a bucket number for each element and stores it in that bucket. It does not keep track of insertion order.
  2. set.add("grape"): "grape" gets bucket number 11, which is computed from its hashCode. Iteration starts from the lowest bucket number, so the order is now grape.
  3. set.add("apple"): "apple" gets bucket number 1, which is computed from its hashCode. Iteration starts from the lowest bucket number, so the order is now apple, grape.
  4. set.add("date"): "date" gets bucket number 0, which is computed from its hashCode. Iteration starts from the lowest bucket number, so the order is now date, apple, grape.
  5. set.add("apple"): The same element is already in the set. A Set cannot contain duplicate elements, so add does not add it and returns false, and that false is printed. The size stays at 3.
  6. set.add("fig"): "fig" gets bucket number 5, which is computed from its hashCode. Iteration starts from the lowest bucket number, so the order is now date, apple, fig, grape.
  7. System.out.println(set): Prints the elements by going through them one after another from the start (iteration). HashSet iterates starting from the bucket with the lowest number. This is neither the insertion order (grape, apple, date, fig) nor the sorted order (apple, date, fig, grape). The output is [date, apple, fig, grape].
  8. System.out.println(set.size()): The code adds five times, but one element was a duplicate and did not go in again, so the size is 4.

Result of this run

Code

Set<String> set = new HashSet<>();
set.add("grape");
set.add("apple");
set.add("date");
System.out.println(set.add("apple"));   // adds a value that is already present
set.add("fig");

System.out.println(set);                   // iterates from the start and prints
System.out.println(set.size());

Assumptions of this model

The output, the size, the value returned when a duplicate is added, and the type of exception were checked for all 30 combinations against the result of running the same code on JDK 21 on this PC. The bucket numbers of HashSet and HashMap were also checked against values read from the internal array of real objects. However, the Java specification does not guarantee the iteration order of the Hash kind. The order shown here is the one on JDK 21 with 16 buckets (12 elements or fewer), and it can change with a different version or a different number of elements. The specific value that the hashCode of a record returns is not specified either, and on JDK 21 the hashCode of Task(int id) was equal to id. A TreeSet decides whether two values are the same by whether the result of compareTo is 0, not by equals. The difference in performance (the Hash kind is faster than the Tree kind) was not measured, and the lab follows the time complexity stated in the documentation.

Previous lab: Inside HashMap · Next lab: Stack, queue, priority queue

Concepts in this lab

What this lab shows

Settings

Code


      
    


    

      
Diagram

      

      

    


    

      

      

      

    


  


  

    

      
Run comparison

      

      

    

    

      
Try these