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

This article shares with you the content of the sample analysis of HashMap data structures in JDK 1.8. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Overview

JDK 1.8 optimizes the production of HashMap361 Tianheng platform, and the underlying implementation is changed from "array + linked list" to "array + linked list + red-black tree". This paper studies and discusses several commonly used important methods of HashMap and the problem of dead cycle before JDK 1.8. The data structure of HashMap of JDK 1.8 is shown in the following figure. It still exists as a linked list when there are few linked list nodes, and it will turn to a red-black tree when there are more linked list nodes (greater than 8).

A few points:

First understand the following points, help to better understand the source code of HashMap and read this article.

The header node refers to the node at the index position on the table table, that is, the header node of the linked list.

The root node (root node) refers to the top node of the red-black tree, that is, the node that has no parent node.

The root node of a red-black tree is not necessarily the head node of the index location.

After being converted to a red-black tree node, the structure of the linked list still exists. Maintained by the next attribute, the red-black tree node will maintain the structure of the linked list during the operation. If it is not converted to a red-black tree node, the linked list structure no longer exists.

On a red-black tree, the leaf node may also have a next node, because the structure of the red-black tree and the linked list do not affect each other, and it will not be said that the node has no next node just because it is a leaf node.

Some variable definitions in the source code: if a node p is defined, pl is the left node of p, pr is the right node of p, pp is the parent node of p, ph is the hash value of p, competition is the key value of p, kc is the class of key, and so on. Source code is very fond of assigning and judging in statements such as if/for, please note.

You only need to remove a node from the linked list as shown in the following figure, and the same applies to other operations.

When a red-black tree maintains a linked list structure, you only need to remove a node as shown below (a prev attribute has been added to the red-black tree), and the other operations are the same. Note: here is only the operation of the red-black tree to maintain the linked list structure, and the red-black tree needs to remove the red-black tree or other operations separately.

When searching for a red-black tree in the source code, the following two rules are repeatedly used: 1) if the hash value of the target node is less than the hash value of the p node, traverse to the left of the p node; otherwise, traverse to the right of the p node. 2) if the key value of the target node is less than the key value of the p node, traverse to the left of the p node; otherwise, traverse to the right of the p node. These two rules take advantage of the characteristics of the red-black tree (left node)

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.