HashMap is implemented in Java through array linked lists/red and black trees. Its performance is affected by the initial capacity, load factor, hash function quality and the immutability of the keys; 1. Use (n-1)&hash to calculate the index to improve efficiency; 2. When the linked list length exceeds 8 and the number of buckets ≥64, it will be converted to a red and black tree, reducing the worst search complexity from O(n) to O(log n); 3. Rehash all elements when expanding, the overhead is high, and the capacity should be preset; 4. The key must be rewrite hashCode and equals correctly; 5. ConcurrentHashMap should be used in multi-threaded scenarios; the average time complexity is O(1) under reasonable use, but improper use will lead to performance degradation.

Java's HashMap is one of the most widely used data structures in the Java Collections Framework. It provides a fast and efficient way to store and retrieve key-value pairs using hashing. But how does it really work under the hood? And what affects its performance in real-world applications? Let's take a deep dive into HashMap , from its internal structure to performance implications.

How HashMap Works Internationally

At its core, HashMap uses an array of buckets, where each bucket can hold a linked list or a tree (in certain cases) of entries. Here's a breakdown of the key components:

• Array of Buckets : The HashMap maintains an internal array ( Node<k>[] table</k> ) where each index is called a "bucket."
• Hashing Function : When you insert a key-value pair, the key's hashCode() is used to compute an index in the array.
• Index Calculation : The actual bucket index is calculated using (n - 1) & hash , where n is the array length (which is always a power of two). This is faster than using module.
• Collision Handling : If two keys hash to the same bucket, entries are stored in a linked list. Starting from Java 8, if a bucket grows beyond a threshold (default 8), and the table is sufficiently large, the linked list is converted to a balanced tree (a TreeNode structure) to improve worst-case performance from O(n) to O(log n).

Each entry in the map is an instance of an internal Node class, which contains:

• The hash of the key
• The key
• The value
• A reference to the next node (for handling collisions)

Key Performance Factors

Several factors influence the performance of a HashMap . Understanding them helps avoid common pitfalls.

1. Initial Capacity and Load Factor

• Initial Capacity : The number of buckets in the hash table when it's created. Default is 16.
• Load Factor : A measure of how full the hash table is allowed to get before resizing. Default is 0.75.

When the number of entries exceeds capacity × load factor , the HashMap resizes (typically doubles in size), which involves rehashing all existing entries — an O(n) operation.

? Best Practice : If you know the expected number of entries, initialize the HashMap with an appropriate capacity to minimize rehashing.

 // If you expect ~1000 entries
Map<String, Integer> map = new HashMap<>(1024, 0.75f);

This avoids multiple resize operations.

2. Hash Function Quality

A poor hashCode() implementation can lead to many collisions, turning the HashMap into a collection of long linked lists (or trees), degrading performance.

? Ensure that keys override hashCode() and equals() correctly and uniformly distributed hash values.

For example, using a key that always returns the same hash code (eg, return 0; ) turns HashMap into a linked list — every operation becomes O(n).

3. Collision Resolution: Linked List vs. Tree

In Java 8 , when a bucket has more than 8 nodes and the table size is at least 64, the list is converted to a red-black tree.

• Best case : O(1) for get/put
• Worst case (many collisions) : O(log n) after treeification, instead of O(n)

This optimization is cruel for defending against denial-of-service attacks via hash collisions (eg, in web servers using user input as keys).

4. Resizing Overhead

Resizing is expensive because it requires:

• Creating a new, larger array
• Re-computing hash positions for all entries
• Reinserting all entries

Frequent resizing can significantly slow down bulk insertions.

?? Avoid letting the map grow dynamically with large datasets. Pre-size it when possible.

Performance in Practice: Time Complexity

Note: Worst case assumes treeified buckets. Without treeification, worst case would be O(n) per operation.

Concurrency and Alternatives

HashMap is not thread-safe . In multi-threaded environments, it can lead to infinite loops (especially during resizing in older Java versions) or data corruption.

• Use ConcurrentHashMap for thread-safe operations.
• ConcurrentHashMap also uses similar optimizations (treeify, resizing) but with fine-grained locking or CAS operations.

 Map<String, Integer> safeMap = new ConcurrentHashMap<>();

It scales better under high concurrency and avoids the pitfalls of Collections.synchronizedMap() .

Memory Overhead

Each Node in HashMap has object overhead:

• Reference to key, value, next
• Hash code stored
• Object header (12–16 bytes depending on JVM)

For large maps, this can add up. Consider alternatives like:

• IdentityHashMap (if reference equality is enough)
• Third-party libraries like Trove ( TObjectObjectHashMap ) for reduced overhead
• Off-heap storage for very large datasets

When to Use HashMap: Best Practices

• ? Use when you need fast average-case lookup, insertion, and deletion.
• ? Ensure keys are immutable or don't change in a way that affects hashCode() or equals() .
• ? Override hashCode() and equals() properly in custom key classes.
• ? Pre-size the map for known data volumes.
• ? Avoid using mutable objects as keys.
• ? Don't store sensitive data in HashMap without clearing references — memory leaks can occur.

Example of a good key:

 public final class PersonKey {
    private final String firstName;
    private final String lastName;

    // constructor, equals, hashCode...

    @Override
    public int hashCode() {
        return Objects.hash(firstName, lastName);
    }
}

Summary

HashMap is a powerful and efficient data structure when used correctly. Its average O(1) performance comes from smart hashing, dynamic resizing, and collision handling via linked lists and trees. However, performance can degrade due to poor hash functions, improper sizing, or misuse of keys.

By understanding how it works — from bucket indexing to treeification — and applying best practices around capacity, hashing, and concurrency, you can make the most of HashMap in performance-critical applications.

Basically, it's fast, but you've got to respect the hash.

The above is the detailed content of A Deep Dive into Java HashMap and Its Performance. For more information, please follow other related articles on the PHP Chinese website!