HashMap implements key-value pair storage through hash tables in Java, and its core lies in quickly positioning data locations. 1. First, use the hashCode() method of the key to generate a hash value and convert it into an array index through bit operations; 2. Different objects may generate the same hash value, resulting in conflicts. At this time, the node is mounted in the form of a linked list. After JDK 8, the linked list is too long (default length 8) and it will be converted to a red and black tree to improve efficiency; 3. When using a custom class as a key, the equals() and hashCode() methods must be rewritten; 4. HashMap dynamically expands capacity. When the number of elements exceeds the capacity and multiplies by the load factor (default 0.75), expand and rehash; 5. HashMap is not thread-safe, and ConcurrentHashMap or synchronous packaging should be used in multithreads.

The internal working principle of HashMap in Java is actually not complicated, but understanding it can help you better use this commonly used data structure. Simply put, HashMap is a key-value pair storage structure implemented through a hash table . Its core lies in how to quickly locate the location of data.

Hash function and array index calculation

HashMap uses an array to store data internally, and each element is a node of a linked list or red and black tree (JDK 8 and above). When you insert a key-value pair, HashMap will first call hashCode() method of the key object to get an integer, and then convert the integer into the subscript of the array through a series of bit operations.

For example:

 map.put("apple", 1);

Here, hashCode() of "apple" returns an integer, and HashMap will perform modulo operations based on the current array length to obtain which position the key value should be stored in the array.

It should be noted that different objects may return the same hash value, which leads to hash conflicts .

Handling hash conflicts: linked lists and red and black trees

When multiple keys are mapped to the same array index, these key-value pairs are hung on this position as a linked list. If the linked list is too long, the search efficiency will decrease. Therefore, starting from JDK 8, when the linked list length exceeds the threshold (the default is 8), the linked list will be converted to a red and black tree to improve search performance.

This is why we recommend that when customizing the class as a HashMap key, we must override equals() and hashCode() methods at the same time - otherwise it may lead to inaccurate data access or memory leaks.

Common questions include:

• Forgot to override hashCode() , causing objects with the same logic to be allocated to different buckets
• Use variable objects as keys, and the corresponding value cannot be found after modification

Scaling mechanism: load factor and rehash

HashMap is not a fixed size, it will automatically expand when the data volume reaches a certain threshold. The trigger point of expansion is determined by two factors: the current capacity and load factor (the default is 0.75).

For example, the initial capacity is 16 and the load factor is 0.75. Then when the number of elements exceeds 16 * 0.75 = 12 , HashMap will expand to twice the original size and recalculate the index position of each key. This process is called rehashing .

Although expansion can avoid hash conflicts too severe, it is a performance-consuming operation itself. Therefore, if you know in advance that you have to store a lot of data, it is best to specify the appropriate capacity during initialization to reduce the number of expansions.

Thread safety issue: Don't use HashMap casually under multi-threading

HashMap is not thread-safe. Simultaneous put operations in a multi-threaded environment may lead to dead loops or data confusion, especially when expanding rehash. If you need thread-safe maps, consider:

• Use Collections.synchronizedMap(new HashMap())
• Or it is more recommended to use ConcurrentHashMap

Basically that's it. Understanding the internal mechanism of HashMap helps you write more efficient and stable code, especially when dealing with large amounts of data or concurrent scenarios.

The above is the detailed content of How does a HashMap work internally in Java?. For more information, please follow other related articles on the PHP Chinese website!