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

This article mainly introduces "the introduction of the principle and internal storage structure of HashMap". In the daily operation, I believe that many people have doubts about the principle and internal storage structure of HashMap. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts about the principle and internal storage structure of HashMap. Next, please follow the editor to study!

This article will analyze the change process of the internal data structure of HashMap through the following simple code.

Public static void main (String [] args) {Map map = new HashMap (); for (int I = 0; I

The following explains the meaning of several fields

1.1 this array is used internally by table// HashMap to store all key-value pairs transient Node [] table

The structure of Node is as follows:

As you can see, Node is actually a linked list that points to the next element through next.

1.2 size

Records the number of key-value pairs in HashMap

1.3 modCount

Records the number of structural changes made by HashMap, including operations that can change the number of key-value pairs, such as put, remove, and operations that can modify internal structures, such as rehash.

1.4 threshold

Record a critical value that needs to be expanded when the number of stored key-value pairs is greater than this critical value.

1.5 loadFactor

Load factor, which is usually used to calculate the total capacity of threshold,threshold= * loadFactor.

2 new HashMap

The source code of new HashMap is as follows:

/ * The load factor used when none specified in constructor.* load factor. When used capacity > total capacity * load factor, the capacity needs to be expanded * / static final float DEFAULT_LOAD_FACTOR = 0.75f / public HashMap () {this.loadFactor = DEFAULT_LOAD_FACTOR; / / all other fields defaulted}

At this point, HashMap initializes only the load factor (using the default of0.75) and does not initialize the table array. In fact, HashMap uses a deferred initialization strategy, initializing the table only when it is the first time put (when table is null).

3 initialization of table array

When you first put, HashMap determines whether the current table is empty, and if so, it calls the resize method to initialize it. The resize method initializes an array of capacity 16 and assigns a value to table.

And calculate the threshold=16*0.75=12.

The status of the table array is as follows:

4 put process map.put ("key0", "value0")

First calculate the hash value of key, hash ("key0") = 3288451

Calculate the index value of the location of the put to be stored in the array this time: index= (array size-1) & hash = 3

Determine that if (table [index] = = null) is new and put a Node here. This time it is null, so new Node is directly placed on 3, and the table is as follows:

Then determine whether the current used capacity (size) has exceeded the critical value threshold. In this case, size=1 is less than 12, no action is taken, and the put method ends (if the critical value is exceeded, resize expansion is required).

Go ahead, put.

Map.put ("key1", "value1")

Map.put ("key1", "value1"); map.put ("key2", "value2"); map.put ("key3", "value3"); map.put ("key4", "value4"); map.put ("key5", "value5"); map.put ("key6", "value6"); map.put ("key8", "value7"); map.put ("key9", "value9"); map.put ("key10", "value10") Map.put ("key11", "value11")

At this point, size=12, the size after the next put is 13, which is larger than the current threshold, and the capacity expansion (resize) will be triggered.

Map.put ("key12", "value12")

Calculate the hash value of Key, hash ("key12") = 101945043, and calculate the index value to be stored in the table location = (total size-1) & hash = (16-1) & 101945043 = 3

From the current table status, table [3]! = null, but if the key of put is not equal to table [3] .key, we have to save it, and there is a hash conflict (hash collision).

At this point, linked lists come in handy, and HashMap solves hash conflicts through linked lists.

HashMap creates a new Node and places it at the end of the table [3] linked list.

The table status is as follows:

5 resize capacity expansion

At this time, there are a total of 13 elements in table, which have exceeded threshold (12). You need to expand the capacity by calling the resize method on table.

HashMap creates a table with twice the previous capacity (162 to 32) and copies the old Node to the new table with a new critical value (threshold) of 24 (320.75).

The following is mainly about the process of replication (it is not the original copy, the location of the Node may change)

Let's first take a look at the source code:

For (int j = 0; j < oldCap; + + j) {/ / oldCap: size of the old table = 16 Node e; if ((e = oldTab [j])! = null) {/ / oldTab: backup oldTab of the old table [j] = null / / if the element in the array does not have a successor node, calculate the new index value directly and put Node in the new array if (e.next = = null) newTab [e.hash & (newCap-1)] = e; / / ignore the else if. In fact, if the length of the linked list exceeds 8PowerHashMap, it will turn the linked list into a tree structure. The elements in the tree structure are TreeNode else if (e instanceof TreeNode) ((TreeNode) e) .split (this, newTab, j, oldCap); / / if there are successor nodes, else {/ / preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null Node next; do {next = e.next1] if ((e.hash & oldCap) = = 0) {if (loTail = = null) loHead = e; else loTail.next = e LoTail = e;} else {if (hiTail = = null) hiHead = e; else hiTail.next = e; hiTail = e }} while ((e = next)! = null); if (loTail! = null) {loTail.next = null; newTab [j] = loHead;} if (hiTail! = null) {hiTail.next = null / / [description 2] newTab [j + oldCap] = hiHead;}

[description 1] iterate through the linked list and calculate the position of each node in the new table.

The location is calculated as follows:

1) if the node's (hash & oldCap) = = 0, then the node is still in its original position, why?

Because of oldCap=16, the expression of binary is 0001 0000. Any number & 16, if equal to 0, then the fifth binary bit of this number must be 0.

In the current state, the new capacity is 32, so the maximum index of table is 31, and the binary representation of 31 is 00011111.

Index is calculated by hash & (capacity-1), that is, the new index is calculated by hash & (32-1)

Suppose the hash of Node is 01101011, then

01101011 & 00011111-00001011 = 11

2) compare (hash & oldCap)! = 0 again below

If the node's (hash & oldCap)! = 0, then the node's location = old index + old capacity size

Suppose the hash of Node is 01111011, then

01111011 & 00011111-00011011 = 27

The hash value of 01101011 in the previous example is different from the hash value of 01111011 in this example only in bit 5 binary. You can find that these two values are in the same index in the old table, as follows:

01101011 & 00001111-00001011 = 11 01111011 & 00001111-00001011 = 11

Because the expansion is always carried out in a double way, that is, the old capacity.

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.