HashSet and HashMap

Open the contacts app on your phone and type "Ra". Ravi's number appears. The phone did not read every contact from the top to find him. It went to the right place straight away.

A HashMap is that contact list. It stores pairs: a key (the name you search by) and a value (what you want back, such as a number). You give it a key, and it gives you the value, in about the same time whether it holds ten contacts or ten million. Each key can appear only once, so saving "Ravi" a second time replaces his number instead of adding a second Ravi.

A HashSet is the same machine with the values taken away. It keeps only the keys, so it answers one question very quickly: "have I seen this before?" Think of a guest list at a door.

These two are the most useful collections after ArrayList. They turn many slow "look through everything" loops into one quick lookup.

Remember: a HashMap finds a value from its key without searching. A HashSet is a HashMap that only cares about the keys.

How can it find "Ravi" without searching? By turning the key into a shelf number.

Every Java object has a method called hashCode(). It returns an int that acts like a fingerprint of the object. For a String, the number is worked out from its letters by a fixed formula, so "Asha" always gives 2050251.

The map owns a row of buckets, which are numbered shelves. It squeezes the fingerprint into the range 0 to (number of buckets - 1), and that is the shelf. In the picture, "Asha" belongs on shelf 3. To find Asha again, the map repeats the sum, goes straight to shelf 3, and looks there. No other shelf is touched.

Two different keys can land on the same shelf. That is called a collision. Kiran and Divya do in the picture. It is not an error. The shelf simply keeps a short chain of everything that landed on it, and the map checks the items on that one shelf with equals, the method that asks "are these two the same?" As long as the chains stay short, a lookup stays quick. Keeping them short is why the map grows its row of buckets when it gets crowded.

Every block below can be pasted into jshell. Start with a HashSet, the guest list.

Set<String> invited = new HashSet<>();
System.out.println(invited.add("Asha"));
System.out.println(invited.add("Ravi"));
System.out.println(invited.add("Asha")); // already there, so nothing changes
System.out.println(invited.contains("Ravi"));
System.out.println(invited.size());

true
true
false
true
2

add answers true when it added something new, and false when the item was already there. That answer is useful on its own, and problem 1 uses it. A set never holds duplicates, so adding "Asha" twice leaves the size at 2.

Now the contact list, as a HashMap.

Map<String, String> contacts = new HashMap<>();
contacts.put("Asha", "98450 11111");
contacts.put("Ravi", "98450 22222");
System.out.println(contacts.get("Ravi"));
System.out.println(contacts.get("Meera")); // no such key: null, not an error
System.out.println(contacts.containsKey("Asha"));
System.out.println(contacts.put("Asha", "98450 33333")); // returns the old value
System.out.println(contacts.size());

98450 22222
null
true
98450 11111
2

put(key, value) stores a pair. get(key) reads it back, and gives null when the key is missing. Be careful with that null: if your map holds Integer values and you write int n = map.get("x") for a missing key, Java tries to unbox null and throws a NullPointerException. Check with containsKey, or use one of the helpers below.

The last put replaced Asha's number, and handed back the old one. The size stayed at 2.

The counting problem

A very common job: count how many times each word appears. The first attempt reads the old count, adds one, and puts it back.

String[] words = {"tea", "chai", "tea", "coffee", "tea", "chai"};
Map<String, Integer> counts = new HashMap<>();
for (String word : words) {
    // getOrDefault gives 0 for a word we have not met yet
    counts.put(word, counts.getOrDefault(word, 0) + 1);
}
System.out.println(counts.get("tea"));
System.out.println(counts.get("chai"));
System.out.println(counts.get("coffee"));

3
2
1

getOrDefault(word, 0) means "the count so far, or 0 if this word is new". It saves you an if. There is a shorter way still.

String[] words = {"tea", "chai", "tea", "coffee", "tea", "chai"};
Map<String, Integer> counts = new HashMap<>();
for (String word : words) {
    // "put 1 if new, otherwise combine the old value with 1 using sum"
    counts.merge(word, 1, Integer::sum);
}
System.out.println(counts.get("tea"));
System.out.println(counts.get("chai"));
System.out.println(counts.get("coffee"));

3
2
1

merge(key, 1, Integer::sum) says: "if the key is new, store 1. If it already has a value, combine the old value and 1 with sum." The Integer::sum part is a method reference, which is a shorthand for passing an existing method as the rule. Counting is the use you will meet most.

Another common job: sort things into groups, such as names by their first letter. Each group is a list, and the list must exist before you can add to it.

String[] names = {"Asha", "Ravi", "Anil", "Meera", "Ravindra"};
Map<Character, List<String>> byInitial = new HashMap<>();
for (String name : names) {
    // make the empty list only the first time a letter appears
    byInitial.computeIfAbsent(name.charAt(0), letter -> new ArrayList<>()).add(name);
}
System.out.println(byInitial.get('A'));
System.out.println(byInitial.get('R'));
System.out.println(byInitial.get('M'));

[Asha, Anil]
[Ravi, Ravindra]
[Meera]

computeIfAbsent(key, rule) looks for the key. If it is missing, it runs the rule to make the value (here, a new empty list), stores it, and returns it. If the key is there, it returns what is stored. Either way you get a list back and can call add on it straight away. The letter -> new ArrayList<>() is a lambda, and it only runs the first time each letter appears. Ask for a letter that no name starts with, and get gives you null, as it does for any missing key.

Last, walking over a map. entrySet() gives you every key-value pair.

Map<String, Integer> stock = new HashMap<>();
stock.put("pens", 12);
stock.put("pads", 5);
stock.put("tape", 3);

int total = 0;
for (Map.Entry<String, Integer> entry : stock.entrySet()) {
    total += entry.getValue();
}
System.out.println(total);

// The map promises no order, so sort the keys to print them the same way every time.
List<String> keys = new ArrayList<>(stock.keySet());
Collections.sort(keys);
for (String key : keys) {
    System.out.println(key + " = " + stock.get(key));
}

20
pads = 5
pens = 12
tape = 3

A HashMap makes no promise about the order of its pairs. They might come out in any order, and the order can differ between Java versions. That is why the code sorts the keys before printing. Never write code that depends on the order. If you want a fixed order, lesson 8 has the collections for that.

Remember: getOrDefault reads with a fallback. merge combines values. computeIfAbsent creates a value the first time a key shows up.

Here is a small map with the same idea as the real one. It is an array of buckets, and each bucket is a chain of nodes (small objects holding a key, a value and a link to the next node).

static class TinyHashMap<K, V> {
    private static class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next; // the next node in the same bucket

        Node(K key, V value, Node<K, V> next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    private Node<K, V>[] buckets = newBuckets(8);
    private int size = 0;

    @SuppressWarnings("unchecked")
    private static <K, V> Node<K, V>[] newBuckets(int count) {
        return (Node<K, V>[]) new Node<?, ?>[count];
    }

    int size() {
        return size;
    }

    int bucketCount() {
        return buckets.length;
    }

    // hashCode can be negative, so floorMod keeps the answer between 0 and length - 1
    static int bucketFor(Object key, int bucketCount) {
        return Math.floorMod(key.hashCode(), bucketCount);
    }

    V get(K key) {
        for (Node<K, V> n = buckets[bucketFor(key, buckets.length)]; n != null; n = n.next) {
            if (n.key.equals(key)) {
                return n.value;
            }
        }
        return null;
    }

    void put(K key, V value) {
        int index = bucketFor(key, buckets.length);
        for (Node<K, V> n = buckets[index]; n != null; n = n.next) {
            if (n.key.equals(key)) {
                n.value = value; // same key: replace, never add a second one
                return;
            }
        }
        buckets[index] = new Node<>(key, value, buckets[index]);
        size++;
        // A crowded table means long chains, so grow before it gets slow.
        // 0.75 is the load factor the real HashMap also starts with.
        if (size > buckets.length * 0.75) {
            grow();
        }
    }

    private void grow() {
        Node<K, V>[] old = buckets;
        buckets = newBuckets(old.length * 2);
        for (Node<K, V> head : old) {
            for (Node<K, V> n = head; n != null; ) {
                Node<K, V> after = n.next; // save it, the move below overwrites next
                int index = bucketFor(n.key, buckets.length);
                n.next = buckets[index];
                buckets[index] = n;
                n = after;
            }
        }
    }
}

Go through it in order.

• buckets starts with 8 shelves. The real HashMap starts with 16.
• bucketFor turns a key into a shelf. hashCode() can be negative, and a negative number is not a valid shelf. Math.floorMod always answers from 0 up, so it is safe.
• get goes straight to one shelf and walks only that chain, comparing keys with equals. A miss gives null.
• put also walks the chain first. If the key is already there it replaces the value. If not, it adds a new node at the front of the chain and counts it.
• grow doubles the number of shelves once the map is more than three-quarters full. That fraction is called the load factor, and the real HashMap starts with the same 0.75. Every node must be moved to its new shelf, because the shelf number depends on how many shelves exist. We save n.next before moving each node, since moving it overwrites the link.

System.out.println("Asha".hashCode() + " -> bucket " + TinyHashMap.bucketFor("Asha", 8));
System.out.println("Ravi".hashCode() + " -> bucket " + TinyHashMap.bucketFor("Ravi", 8));

TinyHashMap<String, String> contacts = new TinyHashMap<>();
contacts.put("Asha", "98450 11111");
contacts.put("Ravi", "98450 22222");
contacts.put("Asha", "98450 33333"); // replaces, so the size stays 2
System.out.println(contacts.get("Asha"));
System.out.println(contacts.size());

2050251 -> bucket 3
2539842 -> bucket 2
98450 33333
2

Asha's key gave shelf 3 and Ravi's gave shelf 2, matching the picture. Saving Asha twice kept the size at 2. The numbers come from the formula Java documents for String, so you will see the same ones.

A HashSet is built on a HashMap and stores each item as a key. That is the whole trick.

"On average" is doing real work here. If many keys land on the same shelf, that chain gets long and lookups slow down. Good hashCode methods spread keys out, and lesson 7 shows what goes wrong when one does not.

static String firstDuplicate(List<String> words) {
    throw new UnsupportedOperationException("return the first word that has already appeared, or null");
}

static String firstDuplicate(List<String> words) {
    Set<String> seen = new HashSet<>();
    for (String word : words) {
        if (!seen.add(word)) { // add says false when the word was already there
            return word;
        }
    }
    return null;
}

static int[] twoSum(int[] numbers, int target) {
    throw new UnsupportedOperationException("find two positions whose numbers add up to target");
}

static int[] twoSum(int[] numbers, int target) {
    Map<Integer, Integer> positionOf = new HashMap<>(); // number -> where we saw it
    for (int i = 0; i < numbers.length; i++) {
        Integer partner = positionOf.get(target - numbers[i]);
        if (partner != null) {
            return new int[] {partner, i};
        }
        positionOf.put(numbers[i], i); // after the check, so a number cannot pair with itself
    }
    return new int[0];
}

static Map<Integer, List<String>> groupByLength(List<String> words) {
    throw new UnsupportedOperationException("map each length to the words that have it");
}

static Map<Integer, List<String>> groupByLength(List<String> words) {
    Map<Integer, List<String>> groups = new HashMap<>();
    for (String word : words) {
        groups.computeIfAbsent(word.length(), length -> new ArrayList<>()).add(word);
    }
    return groups;
}

HashMap is probably the most asked-about class in Java interviews. These are the usual questions.

• "How does a HashMap work?" It has an array of buckets. hashCode() of the key picks a bucket, and equals finds the right entry inside it. Say "buckets", "hashCode", "equals" and "collision" in that order and you have most of the answer.
• "What is a collision, and what happens?" Two different keys land in the same bucket. Both are kept in that bucket and told apart with equals. Lookups slow down only if the chains get long.
• "What are the capacity and load factor?" The capacity is the number of buckets, and 16 to start. The load factor, 0.75 by default, says how full the map may get before it doubles the capacity and moves every entry.
• "Can a key be null?" In a HashMap, yes, one null key. Do not rely on it. Some other maps refuse null keys.
• "Does a HashMap keep order?" No, and never depend on it. A fixed order needs a LinkedHashMap or a TreeMap, which lesson 8 covers.
• "HashMap or HashSet?" A map if you need to look something up by key. A set if you only need to ask "is this in there?" or want to remove duplicates.
• Count words, or find two numbers that add up. Problems 2 and 3 are the standard answers. Say the cost: one pass, O(n) time, O(n) extra space.
• Say the cost. "Lookup, insert and remove are O(1) on average. That is an average and not a promise, because it depends on the keys spreading out."

Made by VeraStack Labs