String hashing, interning and locale traps

"Aa" and "BB" have the same hash code, 2112, and so do all 65,536 strings that can be built from 16 such blocks. String.hashCode is not a secret or random number: its formula is part of the documentation, so collisions are easy to make, and thousands of colliding keys can slow a HashMap down. Equal strings sometimes share one object in the string pool and sometimes do not, which is why == is unreliable for comparing text. And toLowerCase() without arguments follows the language the computer is set to: on a Turkish system "TITLE" becomes "tıtle", and a lookup by that key fails.

You will compute the hash by hand, flood a map with collisions and time it, see which strings the pool shares and why a key that changes is lost, and fix the locale bug with Locale.ROOT. The exercise finds a repeated substring with a rolling hash that must survive a collision.

hashCode multiplies by 31 and adds each char

The documented formula is s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] in int arithmetic, where s[i] are the chars. The usual way to evaluate it is a loop: multiply the result so far by 31 and add the next char. HashFormula.java does that for "Pune" and compares the result with hashCode():

// String.hashCode is documented as s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1], computed in int arithmetic.
// The loop below is the usual way to evaluate that sum: multiply by 31, add the next char.
void main() {
    int h = 0;
    for (char c : "Pune".toCharArray()) {
        int before = h;
        h = 31 * h + c;
        IO.println(String.format("31 * %,9d + '%c' (%3d) = %,10d", before, c, (int) c, h));
    }
    IO.println("\"Pune\".hashCode() = " + "Pune".hashCode());
    IO.println("\"Mumbai\".hashCode() = " + "Mumbai".hashCode() + ": the sum passed 2,147,483,647 and wrapped round");
    IO.println("\"Aa\".hashCode() = " + "Aa".hashCode() + ", \"BB\".hashCode() = " + "BB".hashCode());
    IO.println("because 65 * 31 + 97 = " + (65 * 31 + 97) + " and 66 * 31 + 66 = " + (66 * 31 + 66));
    IO.println("\"\".hashCode() = " + "".hashCode());

    // A hash table picks a bucket from the hash code. With a negative code, % gives a negative index.
    int mumbai = "Mumbai".hashCode();
    IO.println("Mumbai's hash % 8 = " + (mumbai % 8) + ", Math.floorMod(hash, 8) = " + Math.floorMod(mumbai, 8));
}

31 *         0 + 'P' ( 80) =         80
31 *        80 + 'u' (117) =      2,597
31 *     2,597 + 'n' (110) =     80,617
31 *    80,617 + 'e' (101) =  2,499,228
"Pune".hashCode() = 2499228
"Mumbai".hashCode() = -1979126203: the sum passed 2,147,483,647 and wrapped round
"Aa".hashCode() = 2112, "BB".hashCode() = 2112
because 65 * 31 + 97 = 2112 and 66 * 31 + 66 = 2112
"".hashCode() = 0
Mumbai's hash % 8 = -3, Math.floorMod(hash, 8) = 5

Step through the loop, then see what happens to a longer name:

• The four steps for "Pune" give 2,499,228, the same number hashCode() returns.
• Longer strings pass the largest int, 2,147,483,647, and wrap round, an integer overflowinteger overflow: What happens when the result of +, -, * or ++ does not fit its integer type: Java keeps the lowest 32 or 64 bits of the true result, so the value wraps round without an error, and Integer.MAX_VALUE + 1 is Integer.MIN_VALUE. More in “Integer arithmetic, division and overflow” that raises no error: "Mumbai" already hashes to a negative number.
• Code that picks a bucketbucket: One slot of a hash table's array. A HashMap picks a key's bucket from its hash code, keeps the keys that land in the same bucket together, and searches them with equals. or a shard with hash % 8 then gets a negative index, -3. Math.floorMod(hash, 8), the remainder of floor divisionfloor division: Division that rounds the quotient down, toward negative infinity: Math.floorDiv(-7, 2) is -4. Math.floorMod gives the remainder that goes with it, which has the sign of the divisor. More in “Integer arithmetic, division and overflow”, always lands between 0 and 7.
• The empty string hashes to 0, because the loop has nothing to add.

Aa and BB collide, and so does every string built from them

'A' is 65 and 'a' is 97, so "Aa" is 65 × 31 + 97 = 2112; "BB" is 66 × 31 + 66, also 2112. That is a hash collisionhash collision: Two different keys with the same hash code, such as Aa and BB, which both hash to 2112. A hash table keeps both and tells them apart with equals; many collisions in one place make its lookups slow., and it does not stay alone. Because the hash of a longer string is built from the hashes of its parts, any string made of such blocks has the same hash as every other string of the same number of blocks. Collisions.java builds the families of 2 and 4 blocks:

// "Aa" and "BB" have the same hash code, so any string made of k such blocks has the same hash code as every other
// one: 2^k strings with one hash. Here k = 2, then k = 4.
void main() {
    for (int blocks : new int[] {2, 4}) {
        List<String> family = family(blocks);
        Set<Integer> hashes = new HashSet<>();
        for (String s : family) {
            hashes.add(s.hashCode());
        }
        IO.println(family.size() + " strings: " + String.join(" ", family));
        IO.println("distinct hash codes among them: " + hashes);
    }

    List<String> family = family(4);
    Map<String, Integer> map = new HashMap<>();
    for (int i = 0; i < family.size(); i++) {
        map.put(family.get(i), i);
    }
    IO.println("a HashMap still keeps them apart: size " + map.size() + ", get(\"BBAaBBAa\") = " + map.get("BBAaBBAa"));
}

// Every string of the given number of blocks, each block "Aa" or "BB".
List<String> family(int blocks) {
    List<String> family = new ArrayList<>(List.of(""));
    for (int block = 0; block < blocks; block++) {
        List<String> longer = new ArrayList<>();
        for (String s : family) {
            longer.add(s + "Aa");
            longer.add(s + "BB");
        }
        family = longer;
    }
    return family;
}

4 strings: AaAa AaBB BBAa BBBB
distinct hash codes among them: [2031744]
16 strings: AaAaAaAa AaAaAaBB AaAaBBAa AaAaBBBB AaBBAaAa AaBBAaBB AaBBBBAa AaBBBBBB BBAaAaAa BBAaAaBB BBAaBBAa BBAaBBBB BBBBAaAa BBBBAaBB BBBBBBAa BBBBBBBB
distinct hash codes among them: [-540425984]
a HashMap still keeps them apart: size 16, get("BBAaBBAa") = 10

Step from the one collision to families of any size:

4 blocks give 2⁴ = 16 strings with one hash code, and 16 blocks give 65,536. Equal hash codes do not make keys equal: HashMap compares keys with equals once their hashes match, so all 16 strings are separate entries and each is found again. Collisions cost time, not correctness, as the next section measures.

Colliding keys slow a HashMap down unless they can be ordered

HashMap keeps the keys of one bucket together and searches them by equals. Its documentation warns that many keys with the same hash code slow down any hash table, and says that for keys that are Comparable it may use their order to break ties. Since JDK 8 a crowded bucket can become a balanced tree (JEP 180). String is Comparable; the record below is not:

// Puts thousands of keys with one shared hash code into a HashMap, then looks each one up again.
// HashMap keeps colliding keys in one bucket; for keys that are Comparable, such as String, it can order a crowded
// bucket as a tree. Tag is a record that is not Comparable and whose hash code is always 42.
record Tag(String name) {
    @Override
    public int hashCode() {
        return 42;
    }
}

List<String> family(int blocks) {
    List<String> family = new ArrayList<>(List.of(""));
    for (int b = 0; b < blocks; b++) {
        List<String> longer = new ArrayList<>();
        for (String s : family) {
            longer.add(s + "Aa");
            longer.add(s + "BB");
        }
        family = longer;
    }
    return family;
}

long fillAndFind(List<?> keys) {
    long start = System.nanoTime();
    Map<Object, Integer> map = new HashMap<>();
    for (Object k : keys) {
        map.put(k, 1);
    }
    int found = 0;
    for (Object k : keys) {
        if (map.containsKey(k)) {
            found++;
        }
    }
    if (found != keys.size()) {
        throw new AssertionError("lost keys");
    }
    return (System.nanoTime() - start) / 1_000_000;
}

void main() {
    List<String> small = family(13);      // 8,192 strings
    List<String> large = family(16);      // 65,536 strings
    List<Tag> tags = small.stream().map(Tag::new).toList();
    IO.println(String.format("%,6d String keys, one hash code: %,6d ms", small.size(), fillAndFind(small)));
    IO.println(String.format("%,6d String keys, one hash code: %,6d ms", large.size(), fillAndFind(large)));
    IO.println(String.format("%,6d Tag keys, one hash code:    %,6d ms", tags.size(), fillAndFind(tags)));
}

 8,192 String keys, one hash code:     51 ms
65,536 String keys, one hash code:     38 ms
 8,192 Tag keys, one hash code:       673 ms

All the keys of each run share one bucket. Step through one lookup in it, first for the strings, then for the records:

The 65,536 colliding String keys were stored and found again quickly, because the bucket became a tree ordered by compareTo, so each lookup takes about 16 comparisons instead of tens of thousands. The 8,192 Tag keys took many times longer, with an eighth as many keys: without an order, a lookup may have to visit every key in the bucket, and the total work grows with the square of the number of keys.

Literals and constant expressions share one pooled object

Seven expressions below all have the text "Pune". The figure shows which of them refer to one shared object and which make objects of their own:

The Java Language Specification makes one promise about shared string objects: string literals, and more generally strings that are the values of constant expressions, are internedinterning: Keeping one shared String object for each distinct text. Every string literal and every String constant expression of a program is interned, and intern() returns the shared copy, which is why == can be true between them. More in “Strings: first look and equality”, so every occurrence of the same such string refers to one object. Everything else is an ordinary object:

// When do two equal strings share one object? == answers that question (and only that one).
void main() {
    String city = "Pune";
    String joinedByCompiler = "Pu" + "ne";          // a constant expression: javac joins it
    String part = "Pu";
    String joinedAtRunTime = part + "ne";           // part is a variable, so this runs at run time
    final String fixedPart = "Pu";
    String joinedConstant = fixedPart + "ne";       // a final variable with a constant value is a constant too
    String copy = new String("Pune");
    String block = """
            Pune""";

    IO.println("city == \"Pu\" + \"ne\":             " + (city == joinedByCompiler));
    IO.println("city == part + \"ne\":             " + (city == joinedAtRunTime));
    IO.println("city == fixedPart + \"ne\":        " + (city == joinedConstant));
    IO.println("city == new String(\"Pune\"):      " + (city == copy));
    IO.println("city == a text block \"Pune\":     " + (city == block));
    IO.println("city == (part + \"ne\").intern():  " + (city == joinedAtRunTime.intern()));
    IO.println("city.equals(part + \"ne\"):        " + city.equals(joinedAtRunTime));
}

city == "Pu" + "ne":             true
city == part + "ne":             false
city == fixedPart + "ne":        true
city == new String("Pune"):      false
city == a text block "Pune":     true
city == (part + "ne").intern():  true
city.equals(part + "ne"):        true

• "Pu" + "ne" is a constant expressionconstant expression: An expression the compiler works out itself, made only of literals, constant variables and operators, such as "Pu" + "ne" or 60 * 60. Its value is fixed at compile time, and one of type String is interned like a literal. More in “Strings: first look and equality”, so the compiler joins it and it is the same pooled object as "Pune". part + "ne" reads a variable, so it runs at run time and creates a new string: == is false although the text is the same.
• A final variable initialised with a constant is itself a constant, a constant variableconstant variable: A final variable of a primitive type or String initialised with a constant expression, such as static final int LIMIT = 500. javac copies its value into the code that reads it. More in “How Java runs: bytecode, class loading, JIT”, so fixedPart + "ne" is a constant expression again and shares the pooled object. A text block is a literal too.
• new String("Pune") always creates a new object, so it is never == to another string. There is almost never a reason to write it.
• intern() returns the pooled object with the same contents, adding the string to the pool if needed, so s.intern() == t.intern() is true exactly when s.equals(t). Application code rarely needs it: compare text with equals, and if a program holds millions of duplicate strings, the JVM can share their contents for you with -XX:+UseStringDeduplication, which JEP 192 introduced for the G1 collector.

A key that changes is lost inside a HashMap

Strings make good map keys because they never change: a String is an immutable objectimmutable object: An object whose state can never change once it exists, such as a String. Methods that seem to change it, like toUpperCase(), return a new object, so one object can be shared safely by many variables and threads. More in “Strings: first look and equality”, so its hash code stays the same for as long as it is a key. A List key is different. MutableKey.java changes one after it went into a HashMap, then tries a String key:

// Why immutable keys matter: a key that changes after it went into a HashMap cannot be found again.
void main() {
    Map<List<String>, Integer> byRoute = new HashMap<>();
    List<String> route = new ArrayList<>(List.of("Pune", "Mumbai"));
    IO.println("hash code of the route when it goes in: " + route.hashCode());
    byRoute.put(route, 12127);
    route.add("Surat");                                  // the key changes, and so does its hash code
    IO.println("hash code of the same list after add:   " + route.hashCode());
    IO.println("get(route) = " + byRoute.get(route) + ", size = " + byRoute.size());
    IO.println("get(List.of(\"Pune\", \"Mumbai\")) = " + byRoute.get(List.of("Pune", "Mumbai")));

    Map<String, Integer> byName = new HashMap<>();
    String name = "Pune-Mumbai";
    byName.put(name, 12127);
    String longer = name.concat("-Surat");               // a String never changes: concat makes a new one
    IO.println("get(name) = " + byName.get(name) + ", and the new string is a different key: " + byName.get(longer));
}

hash code of the route when it goes in: -1901649174
hash code of the same list after add:   1258668217
get(route) = null, size = 1
get(List.of("Pune", "Mumbai")) = null
get(name) = 12127, and the new string is a different key: null

Step through what the map does with the changed key:

A List computes its hash code from its elements, so the changed list has a new hash code, and the map looks for it under the wrong one. Neither the changed list nor an equal copy of the original finds the entry, although the map still holds it. The Map documentation warns about this very case: once a key held by a map can stop being equals to what it was, the map promises nothing about how it behaves. A String can never change: concat returned a new string, and the original key still found its value.

toLowerCase() follows the default locale unless you pass Locale.ROOT

toLowerCase() and toUpperCase() without arguments use the default localedefault locale: The locale the JVM takes from the computer's settings when it starts, which String.format, printf and formatted use whenever no Locale is passed. The options -Duser.language and -Duser.country set it. More in “Formatted output with printf and formatted”, the language and country the JVM takes from the computer’s settings. Most of the time nobody notices, until the program runs somewhere else:

// Case conversion follows the rules of a language, and the default language is whatever the computer is set to.
void main() {
    Map<String, String> settings = Map.of("title", "Results", "id", "42");
    String key = "TITLE";

    Locale.setDefault(Locale.of("tr", "TR"));        // as on a computer set to Turkish
    IO.println("default locale " + Locale.getDefault().toLanguageTag() + ":");
    IO.println("  \"TITLE\".toLowerCase()            = " + key.toLowerCase());
    IO.println("  \"title\".toUpperCase()            = " + "title".toUpperCase());
    IO.println("  settings.get(key.toLowerCase())  = " + settings.get(key.toLowerCase()));
    IO.println("  \"TITLE\".toLowerCase(Locale.ROOT) = " + key.toLowerCase(Locale.ROOT));
    IO.println("  settings.get(with Locale.ROOT)   = " + settings.get(key.toLowerCase(Locale.ROOT)));
    IO.println("  \"TITLE\".equalsIgnoreCase(\"title\") = " + key.equalsIgnoreCase("title"));

    Locale.setDefault(Locale.US);
    IO.println("lengths can change:");
    IO.println("  \"Straße\".toUpperCase(Locale.ROOT)   = " + "Straße".toUpperCase(Locale.ROOT) + " (6 chars became " + "Straße".toUpperCase(Locale.ROOT).length() + ")");
    String istanbul = "\u0130stanbul".toLowerCase(Locale.ROOT);    // İstanbul, with a dotted capital İ
    IO.println("  \"İstanbul\".toLowerCase(Locale.ROOT) = " + istanbul + " (8 chars became " + istanbul.length()
            + ": i + " + String.format("U+%04X", (int) istanbul.charAt(1)) + " COMBINING DOT ABOVE)");
}

default locale tr-TR:
  "TITLE".toLowerCase()            = tıtle
  "title".toUpperCase()            = TİTLE
  settings.get(key.toLowerCase())  = null
  "TITLE".toLowerCase(Locale.ROOT) = title
  settings.get(with Locale.ROOT)   = Results
  "TITLE".equalsIgnoreCase("title") = true
lengths can change:
  "Straße".toUpperCase(Locale.ROOT)   = STRASSE (6 chars became 7)
  "İstanbul".toLowerCase(Locale.ROOT) = i̇stanbul (8 chars became 9: i + U+0307 COMBINING DOT ABOVE)

Side by side, the two ways of lowercasing the run’s key:

• Turkish has a dotted and a dotless i in both cases, so under the Turkish locale I lowercases to the dotless ı and i uppercases to the dotted İ. "TITLE".toLowerCase() became "tıtle", and the settings lookup returned null: the key title was never found.
• toLowerCase(Locale.ROOT) applies the rules that belong to no language, so the result is the same on every computer. Locale.ROOTLocale.ROOT: The locale that belongs to no language or country, so text converted with it is the same on every computer. Pass it for text a program reads, such as keys, identifiers and protocol words. is for anything a program, not a person, reads: map keys, file extensions, HTTP header names, enum names, command words. Use the user’s locale only for text you show to that user.
• equalsIgnoreCase compares code point by code point without any locale, so it is safe for such checks; for language-aware comparison of names use Collator.
• Case conversion can change the length: ß uppercases to SS, and the Turkish capital İ lowercases in the root locale to i followed by U+0307, a combiningcombining mark: A code point that attaches to the character before it instead of standing alone, such as a vowel sign, the virama or an accent. Its Unicode category is M (Mn, Mc or Me), so Character.isLetter is false for it. More in “Unicode, UTF-16 and Indian scripts” dot. Never apply indexes found in one form of a string to the other.

Practise: find a repeated substring with a rolling hash

A rolling hashrolling hash: A hash of a window of text that is updated in constant time as the window slides by one char: take out the char that leaves, multiply by the base, and add the char that arrives. lets you hash every window of k characters in a text in O(n) total, by updating the hash as the window slides instead of recomputing it. RepeatFinder.java asks for the first window whose content appeared at an earlier position, and two of its checks contain the colliding pair Aa and BB. As it starts, the method returns null, which is right for only two of the six checks:

// Your turn: find the first substring of length k that occurs twice in a text, with a rolling hash.
//
// Slide a window of k chars along the text. Keep the hash of the window in the form String.hashCode uses,
// h = s[i]*31^(k-1) + ... + s[i+k-1], and update it in O(1) when the window moves one char to the right:
// subtract the char that leaves times 31^(k-1), multiply by 31, add the char that arrives (all in int arithmetic,
// which wraps round exactly as String.hashCode does). Return the window whose content appeared at an earlier
// position, the earliest such window, or null when no window repeats. Equal hashes do not prove equal text:
// "Aa" and "BB" share one. Check a match with regionMatches before you return it.
String repeatedSubstring(String text, int k) {
    return null;    // Write your code here.
}

int failed = 0;
int total = 0;

void check(String text, int k, String expected) {
    total++;
    String got = repeatedSubstring(text, k);
    if (!java.util.Objects.equals(got, expected)) {
        failed++;
        IO.println("FAIL repeatedSubstring(\"" + text + "\", " + k + "): expected " + quoted(expected) + ", got " + quoted(got));
    }
}

String quoted(String s) {
    return s == null ? "null" : "\"" + s + "\"";
}

void main() {
    check("banana", 3, "ana");
    check("abcd", 2, null);
    check("aaaa", 1, "a");
    check("AaBB", 2, null);              // "Aa" and "BB" collide, but nothing repeats
    check("AaBBAa", 2, "Aa");            // the colliding "BB" comes first and must not be returned
    check("मेरा नाम मेरा", 4, "मेरा");
    IO.println(failed + " of " + total + " checks failed");
    if (failed > 0) {
        System.exit(1);
    }
}

FAIL repeatedSubstring("banana", 3): expected "ana", got null
FAIL repeatedSubstring("aaaa", 1): expected "a", got null
FAIL repeatedSubstring("AaBBAa", 2): expected "Aa", got null
FAIL repeatedSubstring("मेरा नाम मेरा", 4): expected "मेरा", got null
4 of 6 checks failed

You are done when it prints 0 of 6 checks failed. Hints: compute 31^(k-1) once with a loop; keep a Map<Integer, List<Integer>> from each hash to the start positions of earlier windows; when the current hash is in the map, confirm the match with text.regionMatches(earlier, text, start, k) before returning it; then slide the window with h = (h - text.charAt(start) * power) * 31 + text.charAt(start + k). A version that trusts the hash alone returns "BB" for both collision checks.

Six ideas came before this exercise, from the formula to Locale.ROOT. Test each of them below: the practice begins with whichever you are least sure of and gives the reason behind every choice you pick:

Interview questions

Fresher · What does intern() do, and why is == unreliable for comparing strings?

== asks whether two references point to one object, not whether two strings hold the same text. Java guarantees that string literals and other constant expressions are interned, so every "Pune" literal in a program refers to one object and == between two of them is true. A string built at run time, by concatenating a variable, reading input or calling new String, is a new object, so == with an equal literal is false. Code that compares with == therefore works in a quick test with literals and fails with real input. intern() returns the pooled object with the same contents, adding this string to the pool if it is not there, so s.intern() == t.intern() is true exactly when s.equals(t). Compare text with equals; intern() is rarely needed in application code.

An interviewer who likes this question usually probes the edges of the constant rule and the cost of interning. Two such probes, each with its reasoning:

Beyond the warm-up, the module bank has two harder cases from production: a request whose field names all share one hash code, and settings that fall back to their defaults for one customer only.

Key takeaways

• String.hashCode is s[0]*31^(n-1) + … + s[n-1] in int arithmetic: it can be negative, and "Aa" and "BB" collide, so blocks of them give 2ᵏ strings with one hash code.
• Use Math.floorMod(hash, n), not hash % n, to turn a hash code into an index.
• HashMap stays correct with collisions; Comparable keys such as String let a crowded bucket become a tree, while colliding keys without an order make lookups slow.
• Literals and constant expressions are interned; strings built at run time are new objects; compare with equals.
• Immutable keys such as String keep their hash code; a mutable key that changes is lost inside a HashMap.
• toLowerCase() and toUpperCase() use the default locale: pass Locale.ROOT for keys and identifiers, and expect the length to change in some languages.