国产av日韩一区二区三区精品,成人性爱视频在线观看,国产,欧美,日韩,一区,www.成色av久久成人,2222eeee成人天堂

Table of Contents
Hash calculation and array index
How to resolve hash conflicts
Scaling mechanism: load factor and rehashing
Tips for setting initial capacity
Home Java javaTutorial How Does Java HashMap Work Internally?

How Does Java HashMap Work Internally?

Jul 06, 2025 am 12:22 AM

HashMap uses a hash algorithm to map keys to array indexes to achieve fast access. 1. First call hashCode() to get the hash value, and then determine the index position through perturbation function processing and modulo acquisition; 2. Use a linked list to resolve hash conflicts. After Java 8, the linked list will be converted into a red and black tree to improve search efficiency; 3. The load factor is defaulted to 0.75 when expanding capacity, and if the threshold exceeds the rehashing value, rehashing will expand the array capacity; 4. The initial capacity can be preset to reduce the number of expansions to improve performance.

How Does Java HashMap Work Internally?

Java's HashMap is a very commonly used collection class, and its internal implementation is actually quite clever. It maps keys (Keys) into array indexes through a hash algorithm, thereby achieving fast insertion and search. But how exactly did it? Let's break down several key points.

How Does Java HashMap Work Internally?

Hash calculation and array index

HashMap uses an array to store data internally, and each element is a Node (or Entry). When you put a key-value pair, HashMap will first call hashCode() method of key to get an integer hash value, then process the hash value again through a "perturbation function", and finally determine its position in the array (that is, index) through modulus operation.

How Does Java HashMap Work Internally?

For example:
Assuming that the length of the array is 16 and the hash value of a certain key is 35 after processing, then the index is 35 % 16 = 3 , so this node will be placed at the subscript of the array as 3.

What should be noted is:

How Does Java HashMap Work Internally?
  • If two different keys compute the same index, a hash collision occurs
  • Java 8 introduces the situation of frequent collisions in red and black trees (I will talk about it later)

How to resolve hash conflicts

HashMap uses linked list method to handle hash conflicts. That is, when multiple keys are mapped to the same array subscript, they are stringed in a linked list.

For example, if you have three key-value pairs, all of which fall at index=5, they will form a linked list at the 5th position of the array. Each time you search, you need to traverse this linked list for key comparison (equals).

Starting from Java 8, if the linked list length exceeds the threshold (default is 8), the linked list will be converted to a red and black tree, which can reduce the time complexity of the search from O(n) to O(log n) and improve performance.

But be aware of:

  • The conversion of red and black trees comes at a cost and is only cost-effective when there are frequent conflicts.
  • When the number of elements in the tree is reduced to less than 6, it will degenerate back to the linked list again

Scaling mechanism: load factor and rehashing

HashMap is not a fixed size, it will automatically expand according to the amount of data. The key factor that determines whether to expand capacity is the load factor , which is 0.75 by default.

To give a practical example:
If you initialize a HashMap, the default capacity is 16, then when put into the 16 * 0.75 = 12 element, the HashMap will expand to twice the original size (become 32), and recalculate the index of all keys. This process is called rehashing .

Although scaling can avoid too many hash conflicts, it also has costs:

  • Need to create a new larger array
  • Re-hash all the old data and insert it into the new array
  • Multi-threading may also trigger a dead loop (HashMap is not thread-safe)

Tips for setting initial capacity

If you know in advance how many elements you want to put, it is recommended to specify the initial capacity when constructing a HashMap. This can reduce the number of expansions and improve performance.

For example, if you want to put 100 elements, the default load factor is 0.75, then you need at least a capacity of 100 / 0.75 ≈ 134 . To avoid multiple expansions, you can create it directly like this:

 Map<String, String> map = new HashMap<>(134);

Of course, you can also leave a little room, and it is no problem to set it to 150 or 200.


Basically that's it. HashMap is very smart, but there are some small details that are easily overlooked, such as the secondary perturbation of hash, the threshold value of the linked list to the red and black tree, the expansion time, etc. Understanding these is still very helpful in writing more efficient code.

The above is the detailed content of How Does Java HashMap Work Internally?. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undress AI Tool

Undress AI Tool

Undress images for free

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

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

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Hot Topics

PHP Tutorial
1502
276
Asynchronous Programming Techniques in Modern Java Asynchronous Programming Techniques in Modern Java Jul 07, 2025 am 02:24 AM

Java supports asynchronous programming including the use of CompletableFuture, responsive streams (such as ProjectReactor), and virtual threads in Java19. 1.CompletableFuture improves code readability and maintenance through chain calls, and supports task orchestration and exception handling; 2. ProjectReactor provides Mono and Flux types to implement responsive programming, with backpressure mechanism and rich operators; 3. Virtual threads reduce concurrency costs, are suitable for I/O-intensive tasks, and are lighter and easier to expand than traditional platform threads. Each method has applicable scenarios, and appropriate tools should be selected according to your needs and mixed models should be avoided to maintain simplicity

Best Practices for Using Enums in Java Best Practices for Using Enums in Java Jul 07, 2025 am 02:35 AM

In Java, enums are suitable for representing fixed constant sets. Best practices include: 1. Use enum to represent fixed state or options to improve type safety and readability; 2. Add properties and methods to enums to enhance flexibility, such as defining fields, constructors, helper methods, etc.; 3. Use EnumMap and EnumSet to improve performance and type safety because they are more efficient based on arrays; 4. Avoid abuse of enums, such as dynamic values, frequent changes or complex logic scenarios, which should be replaced by other methods. Correct use of enum can improve code quality and reduce errors, but you need to pay attention to its applicable boundaries.

Understanding Java NIO and Its Advantages Understanding Java NIO and Its Advantages Jul 08, 2025 am 02:55 AM

JavaNIO is a new IOAPI introduced by Java 1.4. 1) is aimed at buffers and channels, 2) contains Buffer, Channel and Selector core components, 3) supports non-blocking mode, and 4) handles concurrent connections more efficiently than traditional IO. Its advantages are reflected in: 1) Non-blocking IO reduces thread overhead, 2) Buffer improves data transmission efficiency, 3) Selector realizes multiplexing, and 4) Memory mapping speeds up file reading and writing. Note when using: 1) The flip/clear operation of the Buffer is easy to be confused, 2) Incomplete data needs to be processed manually without blocking, 3) Selector registration must be canceled in time, 4) NIO is not suitable for all scenarios.

How does a HashMap work internally in Java? How does a HashMap work internally in Java? Jul 15, 2025 am 03:10 AM

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

Effective Use of Java Enums and Best Practices Effective Use of Java Enums and Best Practices Jul 07, 2025 am 02:43 AM

Java enumerations not only represent constants, but can also encapsulate behavior, carry data, and implement interfaces. 1. Enumeration is a class used to define fixed instances, such as week and state, which is safer than strings or integers; 2. It can carry data and methods, such as passing values ??through constructors and providing access methods; 3. It can use switch to handle different logics, with clear structure; 4. It can implement interfaces or abstract methods to make differentiated behaviors of different enumeration values; 5. Pay attention to avoid abuse, hard-code comparison, dependence on ordinal values, and reasonably naming and serialization.

What is a Singleton design pattern in Java? What is a Singleton design pattern in Java? Jul 09, 2025 am 01:32 AM

Singleton design pattern in Java ensures that a class has only one instance and provides a global access point through private constructors and static methods, which is suitable for controlling access to shared resources. Implementation methods include: 1. Lazy loading, that is, the instance is created only when the first request is requested, which is suitable for situations where resource consumption is high and not necessarily required; 2. Thread-safe processing, ensuring that only one instance is created in a multi-threaded environment through synchronization methods or double check locking, and reducing performance impact; 3. Hungry loading, which directly initializes the instance during class loading, is suitable for lightweight objects or scenarios that can be initialized in advance; 4. Enumeration implementation, using Java enumeration to naturally support serialization, thread safety and prevent reflective attacks, is a recommended concise and reliable method. Different implementation methods can be selected according to specific needs

Java Optional example Java Optional example Jul 12, 2025 am 02:55 AM

Optional can clearly express intentions and reduce code noise for null judgments. 1. Optional.ofNullable is a common way to deal with null objects. For example, when taking values ??from maps, orElse can be used to provide default values, so that the logic is clearer and concise; 2. Use chain calls maps to achieve nested values ??to safely avoid NPE, and automatically terminate if any link is null and return the default value; 3. Filter can be used for conditional filtering, and subsequent operations will continue to be performed only if the conditions are met, otherwise it will jump directly to orElse, which is suitable for lightweight business judgment; 4. It is not recommended to overuse Optional, such as basic types or simple logic, which will increase complexity, and some scenarios will directly return to nu.

How to fix java.io.NotSerializableException? How to fix java.io.NotSerializableException? Jul 12, 2025 am 03:07 AM

The core workaround for encountering java.io.NotSerializableException is to ensure that all classes that need to be serialized implement the Serializable interface and check the serialization support of nested objects. 1. Add implementsSerializable to the main class; 2. Ensure that the corresponding classes of custom fields in the class also implement Serializable; 3. Use transient to mark fields that do not need to be serialized; 4. Check the non-serialized types in collections or nested objects; 5. Check which class does not implement the interface; 6. Consider replacement design for classes that cannot be modified, such as saving key data or using serializable intermediate structures; 7. Consider modifying

See all articles