Shulou(Shulou.com)06/01 Report--

How to analyze the basis and practice of HashMap, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain in detail for you, people with this need can come to learn, I hope you can gain something.

HashMap is a knowledge point often asked in an interview, and it is also one of the criteria to judge whether a candidate has a solid foundation, because HashMap can lead to many knowledge points, such as data structures (arrays, linked lists, red-black trees), equals and hashcode methods, in addition to thread safety questions. HashMap is the most ingenious collection of designs that I learned in my beginners. There are many details and optimization techniques worthy of our in-depth study. This article will cover the following issues.

Default size, load factor and expansion multiple

Underlying data structure

How to handle hash conflicts

How to calculate the hash value of key

Why is the length of the array to the power of 2

Process of finding, inserting and expanding capacity

Fail-fast mechanism

If all of the above can be answered, then this article may not be suitable for you.

Note: the source code of this article is explained in JDK1.8 version.

Data structure

In JDK1.8, HashMap is made up of array + linked list + red-black tree (1.7 version is array + linked list)

When a value is to be stored in HashMap, its hash is calculated based on the value of Key, and the location in the array is confirmed by the hash value. If a hash conflict occurs, it is stored as a linked list. If the linked list is too long, HashMap will convert the linked list into a red-black tree for storage, as shown in the figure:

Before we look at the source code, we need to look at some basic attributes.

/ / the default initial capacity is 16static final int DEFAULT_INITIAL_CAPACITY = 1 return o! = null? O.hashCode (): 0;} public final V setValue (V newValue) {V oldValue = value; value = newValue; return oldValue;} public final boolean equals (Object o) {if (o = = this) return true; if (o instanceof Map.Entry) {Map.Entry e = (Map.Entry) o; / / Objects.equals (1memb)-> return (a = = b) | (a! = null & a.equals (b)) If (Objects.equals (key, e.getKey ()) & & Objects.equals (value, e.getValue ()) return true;} return false;}}

Summary

Default initial capacity is 16, default load factor is 0.75

Threshold = array length * loadFactor. When the number of elements is greater than or equal to threshold (capacity threshold), HashMap will expand the capacity

The table array holds references to linked lists

One thing to note here is that the table array is not initialized in the constructor, it is initialized in the resize (expansion) method.

A digression here: a tricky interviewer may ask why the default initial capacity is set to 16. Why is the load factor set to 0.75?

We all know that the length of the HashMap array is designed to the power of 2 (we'll talk about it below), so why not design the initial capacity as 4, 8, or 32. In fact, this is a reasonable number obtained by the JDK designer after weighing. If the default capacity is 8, the expansion operation will be triggered when the sixth element is added, and the expansion operation will consume CPU very much. 32, if only a small number of elements are added, memory will be wasted, so it is more appropriate to design as 16, and the load factor is the same.

The length of the table array is always the power of 2.

It is well known that the length of the HashMap array is always to the power of 2 (referring to the size of the table array). Have you ever wondered why?

First, we need to know that HashMap ensures that the length of the HashMap array is always to the power of 2 through a method called tableSizeFor. The source code is as follows:

/ * find a power greater than or equal to the minimum 2 of cap and use it as the capacity threshold * / static final int tableSizeFor (int cap) {int n = cap-1; n | = n > 1; n | = n > 2; n | = n > 4; n | = n > 8; n | = n > 16; return (n)

= MAXIMUM_CAPACITY)? MAXIMUM_CAPACITY: n + 1;}

The function of tableSizeFor (regardless of cases greater than the maximum capacity) is to return a number greater than or equal to the input parameter and the nearest integer power of 2. For example, 10 returns 16.

The algorithm changes all the bits after the highest bit 1 to 1. Finally, let the result n = 1, that is, you get the value of the integer power of 2.

The purpose of having cap-1 assign to n is to find another target value that is greater than or equal to the original value. For example, binary 1000, the decimal value is 8. If you operate directly without subtracting 1 from it, you will get the answer 10000, or 16. It's obviously not the result. Minus 1, the binary is 111, and then you get the original value of 1000, that is, 8. The efficiency is greatly improved through a series of bit operations.

So where can I use the tableSizeFor method?

The answer is to call this method in the constructor to set the threshold, which is the capacity threshold.

Here you may have another question: why set it to threshold?

This is because the length of the table array will be set when the threshold is initialized for the first time in the expansion method, which will be described later when we talk about the expansion method.

/ * input initial capacity and load factor * / public HashMap (int initialCapacity, float loadFactor) {if (initialCapacity)

MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.