--- title: Java Hashtable date: 2024-01-28 tags: [Algorithm, Java, Collection] cover: https://assets.vluv.space/cover/Dev/Algorithm/hash_table.webp excerpt: "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." updated: 2026-07-08 21:17:39 lang: en i18n: cn: /hash_table translation: 2 --- ## 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 ```mermaid 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 (`{java} Node`) > > | Term | Explanation | > | ------------------- | ------------------------------------------------------------ | > | **Capacity** | The length of the array (buckets). In Java's `HashMap` it is always kept at $2^n$. | > | **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 1. **Compute the hash**: call the object's `{java} hashCode()` method. Taking `String s` as an example, its hash is computed as $hashCode = s[0]*31^{n-1} + s[1]*31^{n-2} + ... + s[n-1]$; 2. **Compute the index**: derive the bucket index with `{java} index = hashCode & (Capacity-1)`. If the bucket is empty, place the entry directly into the array slot; otherwise enter the collision-handling logic 3. **Collision handling** 1. **TreeNode**: if the bucket is already a red-black tree, call `putTreeVal` to insert in $O(\log n)$. 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 `{java} TREEIFY_THRESHOLD` (8) and the array length reaches `{java} MIN_TREEIFY_CAPACITY` (64), the list is converted into a red-black tree. > [!QUESTION]- Why are the thresholds 8 and 64? > > Answer generated by Gemini > > In the JDK 1.8 source code, treeification has two hard requirements: > 1. **List length reaches 8** (`TREEIFY_THRESHOLD`) > 2. **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 $O(n)$ lookups become unacceptable is it worth trading space for $O(\log n)$ 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 ($2^3$) is equivalent to a right shift by three bits $0110 0100 >> 3 = (0000 1100)\_2 = 12$ is the quotient And the last three bits of `01100100`, $(100)\_2 = 4$, are the remainder Given $n = 2^m$, 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` $$ \begin{align} \nonumber & 2 = (10)_2 \quad 2 -1 = (1)_2 \\ & 4 = (100)_2 \quad 4 -1 = (11)_2 \\ & 8 = (1000)_2 \quad 8 - 1 = (111)_2 \\ & ...... \\ &By\ induction:\\ & 2^m = (1000...0)_2 \ a\ leading\ 1\ followed\ by\ m\ zeros\\ & 2^m-1 = (111..1)_2 \ exactly\ m\ ones \end{align} $$ **Worked example** `(n-1) & hash`, let `hash` = 45367, binary 0100 1010 1111 0111, compute `hash % 8` `45367 % 8 = 45367 & 7` $$ \begin{align} &8 = (1000)_2 \quad7 = (111)_2 \quad hash = \ (0100\ 1010\ 1111\ 0111)_2 \\ &45367 \ \%\ 8 = 7 \\ &(0100 1010 1111 0111)_2 \ \&\ (0000\ 0000\ 0000\ \ 0111)_2 = (111)_2 = 7 \end{align} $$ #### 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. ```java 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); } } ``` ```powershell [INPUT = 16] [OUTPUT] hashCode = 69609650 index = 2 index = 2 hashCode % 16 == hashCode & (bucketsLen - 1) is true ---------------------------------------- [INPUT = 47] hashCode = 69609650 index = 34 index = 18 hashCode % 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 $2^n$. | | **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 [算法分析：哈希表的大小为何是素数](https://blog.csdn.net/zhishengqianjun/article/details/79087525) [哈希函数除数的选取为什么是质数？哈希冲突解决方法,闭散列&开散列](https://blog.csdn.net/lovehang99/article/details/101997405)