The underlying implementation of HashMap in Java is a combination structure of arrays, linked lists and red and black trees. 1. It calculates the index position through the hash value of the key and uses perturbation processing to reduce hash collisions; 2. When a hash conflict occurs, the linked list stores elements with the same index; 3. When the linked list length exceeds the threshold (default 8), it converts to a red and black tree to improve performance; 4. When the number of elements exceeds the capacity and multiplies the load factor (default 0.75), it triggers capacity expansion, doubles the array size and redistributes elements; 5. When customizing the key, the equals() and hashCode() methods need to be rewrite to ensure correct access.
The underlying implementation of HashMap in Java mainly relies on array and linked list (or red and black tree) structures. When you put key-value pairs into a HashMap, it determines where the data is stored based on the hash value of the key. If the index calculated by different keys is the same, a hash conflict will occur. At this time, HashMap will use a linked list or a red and black tree to handle these conflicts.

Hash algorithm and index calculation
Each object has its own hashCode()
method. HashMap does not use this value directly, but instead performs a "perturbation" process on it, that is, hash (rehash). The purpose of this is to reduce the probability of hash collisions.

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
After that, HashMap will use this hash value and array length to perform bitwise operations to obtain an index value:
index = (n - 1) & hash;
Here n is the length of the array, and must be a power of 2, which can ensure more uniform distribution and reduce collisions.

Handling hash conflicts: linked lists and red and black trees
When multiple different keys are mapped to the same array position, they are organized into a linked list. However, too long link list will affect the search efficiency. Therefore, after the linked list length exceeds a certain threshold (the default is 8), the linked list will be converted into a red and black tree to improve the performance of search, insertion and deletion.
- When the number of nodes is less than 6, the red and black tree will degenerate back to the link table again
- This design is designed to balance search efficiency and space overhead
So you can understand it as: HashMap = Array linked list red and black tree
Scaling mechanism: resize()
When the number of elements in a HashMap exceeds the capacity multiplied by the load factor (default is 0.75), HashMap will expand. The expansion process includes:
- Create a new array with twice the size
- Recalculate the hash and index all elements in the old array and copy it to the new array
This process is time-consuming, so when initializing HashMap, if you can estimate the data volume, it is best to specify the initial capacity to avoid frequent expansion.
Requirements about key
HashMap allows key to be null, which will be placed at the first position of the array. But if you customize the type of key, such as a class, then be sure to rewrite equals()
and hashCode()
methods, otherwise it may lead to inability to obtain the value correctly or memory leaks.
For example:
class Person { String name; @Override public int hashCode() { return name.hashCode(); } @Override public boolean equals(Object obj) { if (this == obj) return true; if (!(obj instanceof Person)) return false; return this.name.equals(((Person) obj).name); } }
Let's summarize
HashMap is actually a dynamic array, plus a combined structure of linked lists or red and black trees. Its efficiency comes from good hashing algorithms, reasonable conflict handling strategies and automatic scaling mechanisms. Understanding these principles can help write more efficient code and can also help you better deal with related issues during interviews or debugging.
Basically that's it.
The above is the detailed content of How does HashMap work internally in Java?. For more information, please follow other related articles on the PHP Chinese website!

Hot AI Tools

Undress AI Tool
Undress images for free

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

There are three common methods to traverse Map in Java: 1. Use entrySet to obtain keys and values at the same time, which is suitable for most scenarios; 2. Use keySet or values to traverse keys or values respectively; 3. Use Java8's forEach to simplify the code structure. entrySet returns a Set set containing all key-value pairs, and each loop gets the Map.Entry object, suitable for frequent access to keys and values; if only keys or values are required, you can call keySet() or values() respectively, or you can get the value through map.get(key) when traversing the keys; Java 8 can use forEach((key,value)->

In Java, Comparable is used to define default sorting rules internally, and Comparator is used to define multiple sorting logic externally. 1.Comparable is an interface implemented by the class itself. It defines the natural order by rewriting the compareTo() method. It is suitable for classes with fixed and most commonly used sorting methods, such as String or Integer. 2. Comparator is an externally defined functional interface, implemented through the compare() method, suitable for situations where multiple sorting methods are required for the same class, the class source code cannot be modified, or the sorting logic is often changed. The difference between the two is that Comparable can only define a sorting logic and needs to modify the class itself, while Compar

To deal with character encoding problems in Java, the key is to clearly specify the encoding used at each step. 1. Always specify encoding when reading and writing text, use InputStreamReader and OutputStreamWriter and pass in an explicit character set to avoid relying on system default encoding. 2. Make sure both ends are consistent when processing strings on the network boundary, set the correct Content-Type header and explicitly specify the encoding with the library. 3. Use String.getBytes() and newString(byte[]) with caution, and always manually specify StandardCharsets.UTF_8 to avoid data corruption caused by platform differences. In short, by

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 JDK8, 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 Concu should be used in multithreaded

JavaScript data types are divided into primitive types and reference types. Primitive types include string, number, boolean, null, undefined, and symbol. The values are immutable and copies are copied when assigning values, so they do not affect each other; reference types such as objects, arrays and functions store memory addresses, and variables pointing to the same object will affect each other. Typeof and instanceof can be used to determine types, but pay attention to the historical issues of typeofnull. Understanding these two types of differences can help write more stable and reliable code.

InJava,thestatickeywordmeansamemberbelongstotheclassitself,nottoinstances.Staticvariablesaresharedacrossallinstancesandaccessedwithoutobjectcreation,usefulforglobaltrackingorconstants.Staticmethodsoperateattheclasslevel,cannotaccessnon-staticmembers,

std::chrono is used in C to process time, including obtaining the current time, measuring execution time, operation time point and duration, and formatting analysis time. 1. Use std::chrono::system_clock::now() to obtain the current time, which can be converted into a readable string, but the system clock may not be monotonous; 2. Use std::chrono::steady_clock to measure the execution time to ensure monotony, and convert it into milliseconds, seconds and other units through duration_cast; 3. Time point (time_point) and duration (duration) can be interoperable, but attention should be paid to unit compatibility and clock epoch (epoch)

ReentrantLock provides more flexible thread control in Java than synchronized. 1. It supports non-blocking acquisition locks (tryLock()), lock acquisition with timeout (tryLock(longtimeout, TimeUnitunit)) and interruptible wait locks; 2. Allows fair locks to avoid thread hunger; 3. Supports multiple condition variables to achieve a more refined wait/notification mechanism; 4. Need to manually release the lock, unlock() must be called in finally blocks to avoid resource leakage; 5. It is suitable for scenarios that require advanced synchronization control, such as custom synchronization tools or complex concurrent structures, but synchro is still recommended for simple mutual exclusion requirements.
