I. Introduction to Map

1.1 Why is Map Needed

The Collection we learned earlier is called a Collection, which can quickly find existing elements.

The Map in Core Java is called –> mapping..

The mapping model diagram looks like this:

So why do we need this data storage structure?? For example

• As students, we distinguish different students according to their student numbers. As long as we know the student number, we can obtain the corresponding student information. That’s what maps are for!

There are many examples in our life: as long as you take out your ID card, you can prove that it is you.

1.2 Differences between Map and Collection

1.3 the function of the Map

Let’s look at the Map source code:

Simple commonly used Map functions are as follows:

Below, circled in red, are the subclasses of Map of interest:

Two, hash table introduction

For both sets and maps, we’ll find the corresponding –>HashSet,HashMap

First, let’s review the data and linked lists:

• Both lists and arrays can be arranged in any desired order, so they can be said to be ordered (stored in the same order as retrieved)
• At the same time, however, there is a disadvantage: to get an element, you have to access all elements until you find one.
• This will cost us a lot of time inside, iterating through the access elements ~

There are other storage structures that don’t care about the order of the elements and can quickly find their data

• One of these is very common: hash tables

2.1 Working principle of hash table

A hash table computes an integer for each object, called a hash code. The calculated integers (hash codes) are stored in their respective locations!

In Java, hash tables are implemented as linked list arrays, each list called buckets. Bucket sorting is so simple that you can review it.

It is inevitable that a bucket will be occupied (the hashCode will be stored in the same location if the hashCode is the same). This phenomenon is called hash conflicts

• In this case, the object needs to be compared with the object on the bucket to see if the object exists on the bucket ~ if it does, the object is not added; if not, the object is added to the bucket
• Of course, if the HashCode function is well designed and the number of buckets is large enough, this comparison is small
• In JDK1.8, when buckets are full, a linked list becomes a balanced binary tree

If the hash table is too full, create a hash table with more buckets, insert the original elements into the new table, and discard the original table ~

• The load factor determines when to rehash ~ from the hash table
• The default loading factor is 0.75, and if more than 75% of the table is filled with elements, the table is automatically rehashed with double the number of buckets

Of course, in the back of the reading source will continue to explain, now a simple understanding can ~

Read more:

• www.cnblogs.com/s-b-b/p/620…
• www.cnblogs.com/chinajava/p…

Three, red black tree introduction

As mentioned in the hash table above: if the bucket count is full, JDK8 converts the linked list into a red-black tree. In addition, our TreeSet and TreeMap are implemented by red-black trees.

So, learn what a wave of red black trees really is.

Previous articles on binary trees:

• Binary trees are that simple
• Heap sorting is that simple

We’ve probably heard of red-black trees before, but there are other types of B/B+ trees and so on

Various common tree uses:

Source: www.zhihu.com/question/30…

3.1 Review binary search trees

First, let’s review: with the binary search tree, we can generally find the corresponding element very quickly.

• Binary trees are that simple

However, binary search trees also have ** cases (worst)** (linear) :

This is a binary tree, but it is linear and has no use as a tree

A tree has to be “balanced” to show its benefits, such as the following:

Hence, the concept of a balanced tree – a red-black tree is a balanced tree, which ensures that binary trees conform to the short, fat (balanced) structure

3.2 Know new 2-3 trees

When we talk about balanced trees, we have to say that the most basic 2-3 trees, 2-3 trees look like this:

In a binary search tree, we insert a node like this: less than the value of the node continues to the right with the left child, greater than the right child continue with the right child, until the left or right child of a node is empty, insert the value. There is no way to avoid bias problems

The 2-3 tree is different: it inserts to keep the tree balanced!

In the case of 2-3 tree insertion, it can be summarized as two operations:

• Merge the 2-node to 3-node, and expand the 3-node to a 4-node
• Decompose the 4-node into 3-node and the 3-node into 2-node
• . To make the tree balanced

The operation of merge decomposition is still more complex, should be divided into several cases, the amount of code is very large ~ here I will not introduce, because to learn is a lot of, very troublesome ~

3.3 From 2-3 trees to red-black trees

In order to maintain the balance of 2-3 trees, a large number of nodes need to be swapped during maintenance! These transformations are complicated in real code, and the big guys invented red-black trees based on the theory of 2-3 trees (the same goes for 2-3-4 trees, except that 2-3 is the simplest case, so I won’t say 2-3-4).

• The red-black tree is an improvement on the 2-3 search tree, which can perform all transformations in a uniform way.

A red-black tree is a balanced binary tree, so it has no 3-nodes. So how does a red-black tree take 3-nodes and make them all binary trees?

A red-black tree is literally a tree with red nodes and black nodes:

We can flatten the left link of the red node:

A typical binary tree:

After the left link of the red node is drawn flat, the balance tree of 2-3 is obtained:

3.4 Basic knowledge of red-black tree

As mentioned earlier, a red-black tree is a tree implemented on a 2-3 basis that performs all transformations in a uniform manner. A red black tree is a balanced tree. It has to balance the tree when inserting elements. What does a red black tree do to balance the tree?

Red-black trees replace the constant node switching of 2-3 trees in two ways:

• Rotation: clockwise and counterclockwise rotation
• Invert colors: Swap red and black colors
• This two implementation is a little more convenient than the nodes (merge, decompose) swapped in 2-3 trees

In order to maintain balance, there are also some constraints, which are called red black trees:

1. Red-black trees are binary search trees.
2. The root node is black.
3. Each leaf node is a black empty node (NIL node).
4. Two children of each red node are black. (No two consecutive red nodes on all paths from each leaf to the root)
5. All paths from any node to each of its leaves contain the same number of black nodes (the number of black nodes on each tree chain (called “black heights”) must be equal).

3.5 Red-black Tree summary

Red black tree is very complex, I did not carefully look at the processing details in the study, just go through the general, know the whole ~

With a lot of high quality information of predecessors, I believe that if you want to understand the details, you can still master them with some effort and time.

Red black tree References:

• Blog.csdn.net/chen_zhang_…
• Riteme. Making. IO/blog / 2016-3…
• www.sohu.com/a/201923614…
• www.jianshu.com/p/37c845a5a…
• www.cnblogs.com/nullzx/p/61…
• Blog.csdn.net/fei33423/ar…

Four,

This chapter describes the basic knowledge of Map sets and the common subclasses of Map

Hashxxx and Treexxx are the base of Hashxxx and Treexxx. They are the base of Hashxxx and Treexxx

Later, we will look at the source code of Map common subclasses. Please look forward to the article at ~~~~

Open source project (6 K STAR) :Github.com/ZhongFuChen…

If you want to follow my updated articles and shared dry goods in real time, you can search Java3y on wechat.

The content of the PDF document is typed by hand. If you don’t understand anything, you can ask me directly (the official account has my contact information).