HashMap analysis.

This is the back-end small class of the monastery. Each article is shared from

[background introduction] [knowledge analysis] [common problems] [solutions] [coding practice] [extended thinking] [more discussion] [References]

Eight aspects of in-depth analysis of back-end knowledge / skills. This article shares:

[HashMap analysis.]

Hello, I'm a student of the tenth phase of Zhengzhou branch of it Academy. I'm an honest, pure and kind java programmer

Today, I'd like to share with you the knowledge points in deep thinking -- HashMap analysis on the official website of Xiuzhen Academy.

Background introduction

The map set, that is, the K-V set, plus a hash, is hashed and unordered. HashMap is simply understood as a hash and unordered K-V set. Next, analyze HashMap in depth.

Knowledge analysis

Data structure of HashMap

Advantages and disadvantages of array: it is easy to find through subscript index, but it is difficult to insert or delete an element in the array.

Advantages and disadvantages of linked list: because finding an element in the linked list needs to find it by traversing the linked list, and insertion and deletion are fast. Therefore, the linked list is suitable for the scene of rapid insertion and deletion, which is not conducive to search.

The bottom layer of HashMap is hash array, and the array element is entry. HashMap calculates the hash value through the hashcode of the key. When the hashcodes are the same, the "zipper method" is used to solve the conflict.

The instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table. The initial capacity is only the capacity of the hash table when it is created. Load factor is a measure of how full a hash table can be before its capacity automatically increases. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the internal data structure of the hash table shall be reconstructed so that the hash table will have about twice the number of buckets.

Typically, the default load factor is 0.75, which is a compromise between time and space costs. High load factor reduces space overhead, But it also increases the query cost (this is reflected in the operations of most HashMap classes, including get and put operations). When setting the initial capacity, you should consider the number of entries required in the map and its loading factor, so as to minimize the number of refactoring operations. If the initial capacity is greater than the maximum number of entries divided by the loading factor, refactoring will not occur.

common problem

Why does the array length of HashMap must be a power of 2?

Extended thinking

Jdk1. Differences between HashMap in 7 and 1.8

The red black tree is introduced into the data structure to solve the problem of low efficiency of adding, deleting, modifying and searching when the linked list is too long;

The calculation of storage location after capacity expansion is different, jdk1 7 after capacity expansion, the key needs to be recalculated according to the original method. 1.8 Li, direct original position or original position + expanded capacity;

The methods of inserting data are also different. 1.7 uses head interpolation and 1.8 uses tail interpolation.

reference

More discussion

Q1: when the HashMap exceeds the default length, recreate the HashMap (including defining the length), copy the original content, and then destroy the original HashMap?

A1: Yes, because the array data structure can only re apply for memory space and cannot be expanded directly.

Q2: when will HashMap be expanded?

A2: according to the load factor calculation, when the currently used capacity is greater than the product of the load factor and the maximum capacity, the capacity is expanded.

Q3: as the amount of data increases, the query time complexity of HashMap?

A3: array is O (1) and linked list is O (log n). If the length of the linked list exceeds 8, it becomes a red black tree, which is O (n).

Ppt link video link