Jan 27·6 min· PV

Java Hashtable

A hash table looks up data in O(1) time. This post walks through hash tables in the Java ecosystem: the data structure, the put process, and thread safety.

Java·Algorithm·Collection

Data Structure

A hash table is built on an array, but to handle heavy hash collisions, Java (specifically HashMap since JDK 1.8) uses a hybrid storage structure

graph TD
    Table[Hash Table Array] --> B1[Bucket 0]
    Table --> B2[Bucket 1]
    Table --> B3[Bucket ...]
    Table --> Bn[Bucket n]

    B1 --> N1[Node K-V]
    N1 --> N2[Node K-V]
    N2 --> N3[Node K-V]

    B3 --> T1((TreeNode Red))
    T1 --> T2((TreeNode Black))
    T1 --> T3((TreeNode Black))

Summary

Bucket: a storage unit in the hash table that holds key-value pairs. Each bucket may contain one or more nodes (Node<K,V>)

Term	Explanation
Capacity	The length of the array (buckets). In Java’s `HashMap` it is always kept at .
Load Factor	Defaults to `0.75`; when the element count reaches `Capacity * 0.75`, a resize is triggered.
Hash Collision	Different keys produce the same index
Rehashing	On resize, a new array of double the capacity is created and old entries are re-placed into it after recomputing their positions.

The put Process

Compute the hash: call the object’s hashCode() method. Taking String s as an example, its hash is computed as ;
Compute the index: derive the bucket index with index = hashCode & (Capacity-1). If the bucket is empty, place the entry directly into the array slot; otherwise enter the collision-handling logic
Collision handling
1. TreeNode: if the bucket is already a red-black tree, call putTreeVal to insert in .
2. LinkedList: traverse to the end of the list and append the new node (JDK 1.8+)
  - Treeification: after insertion, if the list length reaches TREEIFY_THRESHOLD (8) and the array length reaches MIN_TREEIFY_CAPACITY (64), the list is converted into a red-black tree.

Why are the thresholds 8 and 64?

Answer generated by Gemini

In the JDK 1.8 source code, treeification has two hard requirements:

List length reaches 8 (TREEIFY_THRESHOLD)
Array capacity reaches 64 (MIN_TREEIFY_CAPACITY)

If only condition 1 is met but not condition 2, HashMap prefers resizing over treeification. Why these two gates?

1. Why resize first (Capacity < 64)?

The core reason: fix the cause, not the symptom.

When the array is small (say 16 or 32), long lists usually appear because there are too few buckets, which makes hash collisions far more likely. In this case resizing is the better choice:

Effect of resizing: the array doubles, and nodes in the old list are redistributed based on the high bits of their hash, most likely splitting across two different buckets, so the list naturally shortens.
Cost comparison: maintaining a red-black tree, with its left rotations, right rotations, and recoloring, is far more complex than simply resizing the array and splitting the list.

So while the array is small, resizing is the preferred way to resolve collisions. Only once the array is large enough (>= 64), when further resizing is too expensive and no longer spreads collisions effectively, does the red-black tree kick in as the fallback.

2. Why is the list threshold 8?

Two considerations are at play here: space cost and statistical probability.

A. Space/Time Trade-off

A TreeNode (red-black tree node) is roughly twice the size of a Node (list node).
When the list is short, linear traversal is very fast, and the performance gained by converting to a red-black tree does not offset its construction and memory costs.
Only when the list grows long enough that lookups become unacceptable is it worth trading space for time.

B. Poisson Distribution
This is the core mathematical basis. The HashMap source comments spell it out:

In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution…

With a well-designed hash function, key distribution should follow a Poisson distribution. At a load factor of 0.75, the probability of a bucket holding a given number of nodes is:

Node count (k)	Probability
0	0.60653066
1	0.30326533
2	0.07581633
…	…
8	0.00000006

Conclusion: under normal conditions, the probability of a list reaching length 8 is less than one in ten million.
If it actually reaches 8, something has gone badly wrong with hash collisions (an extremely poor hash algorithm, or a hash DoS attack). At that point HashMap converts the list to a red-black tree to keep the system from grinding to a halt. 8 is a statistical “practically impossible” boundary.

3. Why is the untreeify threshold 6 (`UNTREEIFY_THRESHOLD`)?

When deletions shrink a red-black tree to 6 nodes, it degrades back into a list. Why not 7?

Reason: to avoid thrashing.
If the treeify threshold were 8 and the untreeify threshold 7, then a put bringing the count to 8 (convert to tree), followed by a remove bringing it to 7 (convert to list), then another put back to 8…
Frequent structural conversions burn CPU. Leaving a buffer of 2 nodes (8 -> 6) effectively prevents this performance oscillation around the boundary.

Hashtable’s Fast Modulo Trick

Proof

In binary bit arithmetic, integer division by 8 () is equivalent to a right shift by three bits

is the quotient

And the last three bits of 01100100, , are the remainder

Given , the quotient is the binary hash shifted right by m bits, and the remainder is the last m bits of hash

To compute hash % n, we need the last m bits of hash. Since the binary representation of n-1 is exactly m ones, it follows that hash & (n-1) equals hash % n

Worked example

(n-1) & hash, let hash = 45367, binary 0100 1010 1111 0111, compute hash % 8

45367 % 8 = 45367 & 7

Why is the size of a Java hash table a power of 2?

Code Verification

In the JDK, Hashtable computes the modulo as hash & (n-1). This only works when n is a power of 2; in other cases it does not necessarily hold.

public class HashTable {    public static void main(String[] args) {        int bucketsLen = new Scanner(System.in).nextInt();        int hashCode = new String("Hello").hashCode();        System.out.println("hashCode = " + hashCode);        int index = hashCode & (bucketsLen - 1);        System.out.println("index = " + index);        index = hashCode % bucketsLen;        System.out.println("index = " + index);        String isEqual = (hashCode % bucketsLen) == (hashCode & (bucketsLen - 1)) ? "true" : "false";        System.out.println("hashCode % bucketLen == hashCode & (bucketsLen - 1) is " + isEqual);    }}

[INPUT = 16][OUTPUT]hashCode = 69609650index = 2index = 2hashCode % 16 == hashCode & (bucketsLen - 1) is true----------------------------------------[INPUT = 47]hashCode = 69609650index = 34index = 18hashCode % bucketLen == hashCode & (bucketsLen - 1) is false

Hashtable vs HashMap vs ConcurrentHashMap

Term	Explanation
Capacity	The length of the array (buckets). In Java’s `HashMap` it is always kept at .
Load Factor	Measures how full the hash table is; defaults to `0.75`. When the element count reaches `capacity * 0.75`, a resize is triggered.
Hash Collision	Different keys produce the same index. This is the core problem every hash table must handle.
Rehashing	When the array runs out of room, a new array of double the size is created and old entries are re-placed into it after recomputing their positions.

Ref

算法分析：哈希表的大小为何是素数
 哈希函数除数的选取为什么是质数？哈希冲突解决方法,闭散列&开散列