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

This article introduces the relevant knowledge of "what is the underlying principle of HashMap". In the operation of actual cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

HashMap storage structure

Here we need to distinguish between the HashMap storage structure after JDK1.7 and JDK1.8. Before JDK1.7, it was stored as an array plus a linked list.

However, it is well known that when the length of the linked list is very long, the query efficiency will plummet, and the time complexity of the query is O (n). Therefore, JDK1.8 designed it to convert the linked list into a red-black tree after reaching a certain threshold.

Here is a brief description of the characteristics of the red-black tree:

Each node has only two colors: red or black

The root node must be black

Each NIL is a black empty node

There cannot be two consecutive red nodes from the root node to the leaf node.

From any node, the path to the child nodes below it contains the same number of black nodes

Because the red-black tree is a self-balanced binary search tree, the time complexity of the query can be reduced to O (logn). (the red and black tree is not the focus of this article. Children's shoes that you don't know can consult the relevant materials on your own.)

Schematic diagram of HashMap structure:

Commonly used variables

In the HashMap source code, the more important commonly used variables are mainly the following. There are also two inner classes to represent the nodes of the normal linked list and the red-black tree nodes.

/ / the default initialization capacity is 16, which must be 2 to the n power static final int DEFAULT_INITIAL_CAPACITY = 1

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.