Maps and Hashing in Java

Why do we need maps?

In arrays and lists, you find an item by its position (its index), like grades[2]. But in real life you usually know a name or an ID, not a position. To find the grade of student 2025-0101 in a list, you would have to check the items one by one.

A map fixes this: you store each value under a key, and later you ask for it by that same key.

The two rules

1. Keys are unique. Each key appears once. If you store a value under a key that already exists, the old value is replaced.
2. Values can repeat. Two different students can have the same grade. Two products can have the same price.

import java.util.HashMap;
import java.util.Map;

public class Grades {
  public static void main(String[] args) {
    Map<String, Integer> grades = new HashMap<>();

    grades.put("2025-0012", 89);   // insert
    grades.put("2025-0047", 92);
    grades.put("2025-0101", 89);   // same value is OK
    grades.put("2025-0012", 95);   // same key: replaces 89

    System.out.println(grades.get("2025-0012"));  // 95
    System.out.println(grades.get("2025-9999"));  // null
    System.out.println(grades.containsKey("2025-0047")); // true
    System.out.println(grades.size());            // 3

    grades.remove("2025-0047");                   // delete
    System.out.println(grades.size());            // 2

    for (String id : grades.keySet()) {           // order not guaranteed
      System.out.println(id + " -> " + grades.get(id));
    }
  }
}

95
null
true
3
2
2025-0101 -> 89
2025-0012 -> 95

HashMap, LinkedHashMap, or TreeMap?

All three classes have the same Map methods, so put, get, and remove work the same way in each. They differ in one thing you can see: the order of the keys when you loop over the map or print it. This program puts the same 4 pairs, in the same order, into one map of each kind:

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.TreeMap;

public class ThreeMaps {
  static void addGrades(Map<String, Integer> m) {
    m.put("Rico", 88);   // same 4 pairs,
    m.put("Bea", 92);    // same order,
    m.put("Liza", 85);   // for every map
    m.put("Dan", 90);
    m.put("Rico", 91);   // same key: new value, same place
  }

  public static void main(String[] args) {
    Map<String, Integer> hash = new HashMap<>();
    Map<String, Integer> linked = new LinkedHashMap<>();
    Map<String, Integer> tree = new TreeMap<>();
    addGrades(hash);
    addGrades(linked);
    addGrades(tree);
    System.out.println("HashMap:       " + hash);
    System.out.println("LinkedHashMap: " + linked);
    System.out.println("TreeMap:       " + tree);
    System.out.println(tree.get("Liza"));
  }
}

▶ Try it in the Programiz online compiler: tap Copy, paste it there, change public class ThreeMaps to public class Main (Programiz saves your code as Main.java, and Java needs the file name and the public class name to match), then press Run.

Output (checked in Java). Java prints a map as key=value pairs inside curly braces:

HashMap:       {Liza=85, Dan=90, Rico=91, Bea=92}
LinkedHashMap: {Rico=91, Bea=92, Liza=85, Dan=90}
TreeMap:       {Bea=92, Dan=90, Liza=85, Rico=91}
85

Read the three lines one at a time:

• HashMap printed Liza, Dan, Rico, Bea: neither the order added nor A to Z. It is bucket order, which Part 6 explains.
• LinkedHashMap printed Rico, Bea, Liza, Dan: the order the keys were first added. The second put("Rico", 91) changed Rico's value but not his place.
• TreeMap printed Bea, Dan, Liza, Rico: sorted by key, A to Z.

Here is when to use each one:

Good to know: a TreeMap sorts String keys by their character codes, so every capital letter comes before every small letter ("Zed" comes before "ana"). Write names the same way, like "Ana" and "Zed", to get A to Z.

Which map fits? Three quick situations (for self-study, not for grading):

Quick review: characters and strings

A character (char in Java) is one letter, digit, symbol, or space, written in single quotes: 'D'. A string (String) is a sequence of characters in order, written in double quotes: "DOG". Each character has a position, its index, starting at 0.

Inside the computer, every character is stored as a number called its character code (from the ASCII or Unicode table). For example, 'D' is 68.

The hashCode rule

The goal is to turn the whole string into one number that depends on every character and on their order. We build that number one character at a time and call it h (short for "hash"). Think of h as a running total: the hash code so far.

Why multiply by 31? If we only added the codes, "DOG" and "GOD" would get the same number, because they have the same letters. Multiplying by 31 before each add makes each character's position matter: "DOG" gives 67,868, but "GOD" gives 70,748. (Java's designers chose 31 because it is an odd prime that mixes the numbers well, and computers can multiply by it quickly.)

Good to know: Java's documentation writes the same rule as one long formula, s[0]·31ⁿ⁻¹ + s[1]·31ⁿ⁻² + … + s[n−1], where s[0] is the code of the first character, s[1] the second, and n is the number of characters. The running total gives the same answer in smaller steps.

Character codes you need

Uppercase letters go from A = 65 to Z = 90. Lowercase letters are 32 more: a = 97 to z = 122. The digit 0 is 48, and a space is 32.

Worked example: "DOG"

Char	Code	31 × h + code	New h
D	68	31 × 0 + 68	68
O	79	31 × 68 + 79	2,187
G	71	31 × 2,187 + 71	67,868

"DOG".hashCode() = 67,868

Check with the long formula: 68 × 31² + 79 × 31 + 71 = 68 × 961 + 2,449 + 71 = 65,348 + 2,449 + 71 = 67,868. Same answer.

Worked example: "DOG" → bucket 12

There are two ways to get the answer. Both give the same result for a positive hash code.

Why does this work? 16 = 2⁴, so dividing by 16 is like chopping off the last 4 bits. The chopped-off bits are the remainder. This only works because the capacity is a power of 2 (16, 32, 64…), which is why HashMap capacities always are.

Why a HashMap has no order

When you loop over a HashMap's keys, Java walks its buckets in number order (0, 1, 2, …) and reads each chain. So the keys come out in bucket order, not in the order you added them. That is why the Grades program in Part 2 printed 2025-0101 before 2025-0012: inside Java's real HashMap (with the mixing step from Part 5), 2025-0101 sits in bucket 1 and 2025-0012 in bucket 2.

Need the keys in the order you added them? Use LinkedHashMap. Sorted by key? Use TreeMap. Compare the three in the three-maps output from Part 2 .

The same thing in Java

This program puts three entries and prints each key's hash code and bucket, using the course formula:

import java.util.HashMap;

public class HashMapExample {
  static int capacity = 16;

  static void addEntry(HashMap<String, String> map,
                       String key, String value) {
    map.put(key, value);
    int hashCode = key.hashCode();
    int bucketIndex = hashCode & (capacity - 1);
    System.out.println(key + " -> " + value
        + " | hash " + hashCode + " | bucket " + bucketIndex);
  }

  static void removeEntry(HashMap<String, String> map, String key) {
    if (map.containsKey(key)) {
      int bucketIndex = key.hashCode() & (capacity - 1);
      map.remove(key);
      System.out.println("Removed " + key + " from bucket " + bucketIndex);
    } else {
      System.out.println(key + " not found");
    }
  }

  public static void main(String[] args) {
    HashMap<String, String> map = new HashMap<>();
    addEntry(map, "Alice", "Developer");
    addEntry(map, "Bob", "Designer");
    addEntry(map, "Charlie", "Manager");
    removeEntry(map, "Bob");
    removeEntry(map, "Dana");
  }
}

▶ Try it in the Programiz online compiler: tap Copy, paste it there, change public class HashMapExample to public class Main (Programiz saves your code as Main.java, and Java needs the file name and the public class name to match), then press Run.

Output:

Alice -> Developer | hash 63350368 | bucket 0
Bob -> Designer | hash 66965 | bucket 5
Charlie -> Manager | hash -1891246254 | bucket 2
Removed Bob from bucket 5
Dana not found

Notice "Charlie": its hash code is negative because it wrapped around, but & 15 still gives a bucket from 0 to 15.