Understanding Java HashMap: Data Structure, Hash Function, Collision Handling, Put Process, Resizing, and Thread Safety

1. HashMap data structure – HashMap stores key‑value pairs using an array of Node objects, where each bucket may contain a singly linked list or a red‑black tree (JDK 1.8). The basic Node class encapsulates a String key and String value , and the table is declared as Node[] table = new Node[24]; .

2. Hash function and collision – To locate a bucket, the key's hashCode() is obtained, then its range is limited by hash % length or more efficiently by hash & (length‑1) . To reduce collisions, the high 16 bits of the hash are XORed with the low 16 bits, producing a final hash with fewer repeated low bits.

3. Put process – When inserting, HashMap first ensures the table is initialized (e.g., if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; ). It then computes the bucket index and handles three cases: (1) same key – replace value; (2) different key – chain via linked list; (3) different key with many entries – convert the list to a red‑black tree. The code iterates through the list, creates a new node with newNode(hash, key, value, null) , and treeifies when the list length exceeds TREEIFY_THRESHOLD (8).

4. Resizing – When size > threshold (default load factor 0.75), HashMap expands the array, typically doubling its capacity (e.g., 16 → 32). The resize method creates a new table, rehashes existing nodes, and moves them either directly (if a bucket has a single node) or splits linked‑list or tree buckets into low and high partitions based on the new capacity. The code shows the detailed migration logic, including handling of TreeNode splits and rebuilding linked lists.

5. Thread safety – Concurrent modifications can lead to inconsistent data. To achieve thread safety, one can synchronize the put method, but this incurs a lock per operation. Alternatives such as Hashtable or ConcurrentHashMap provide built‑in concurrency control without the same performance penalty.

Overall, the article provides a comprehensive walkthrough of HashMap’s internal mechanisms, illustrated with actual source code snippets.