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

In this issue, the editor will bring you about how to analyze the source code of the HashMap expansion mechanism. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.

Before we look at the source code, let's briefly talk about the underlying data structure of HashMap.

1. The underlying data structure of HashMap is array + linked list + red-black tree.

2. We need to understand the two variables at the bottom of HashMap first

2-1:loadFactor: the load factor, which defaults to .75, is the most appropriate value after repeated testing.

2-2:threshold: when the data in map is larger than this threshold, the capacity will be expanded.

Note: click here to learn more about loadFactor

2. Now let's take a look at the construction of HashMap

There are four construction methods of hashMap.

1. Empty parameter construction method. In this case, the loading factor is 0.75 by default, and no space is created.

Threshold is 0

The array is null

Public HashMap () {

This.loadFactor = DEFAULT_LOAD_FACTOR; / / all other fields defaulted

}

2. Given the initialization capacity, the third constructor is called directly in this constructor.

Threshold is already worth it.

The array is null

Public HashMap (int initialCapacity) {

This (initialCapacity, DEFAULT_LOAD_FACTOR)

}

3. Given initialization size, and loading factor.

1. It is not recommended to modify the default loading factor. Unless, of course, you know the logic well enough to find a loading factor that suits your project.

2. First, determine whether the initialization capacity you gave is legal, and if so, use this initialization capacity to calculate the threshold.

Threshold is already worth it.

The array is null

Public HashMap (int initialCapacity, float loadFactor) {

If (initialCapacity

< 0) 　　throw new IllegalArgumentException("Illegal initial capacity: " + 　　initialCapacity); 　　if (initialCapacity >

MAXIMUM_CAPACITY)

InitialCapacity = MAXIMUM_CAPACITY

If (loadFactor 0) {

If (table = = null) {/ / pre-size

Float ft = (float) s / loadFactor) + 1.0F

Int t = (ft

< (float)MAXIMUM_CAPACITY) ? 　　(int)ft : MAXIMUM_CAPACITY); 　　if (t >

Threshold)

Threshold = tableSizeFor (t)

}

Else if (s > threshold)

Resize ()

For (Map.Entry e: m.entrySet ()) {

K key = e.getKey ()

V value = e.getValue ()

PutVal (hash (key), key, value, false, evict)

}

}

}

3. Let's see how HashMap entered the expansion.

3-1: let's start with the put () method.

Public V put (K key, V value) {

Return putVal (hash (key), key, value, false, true)

}

At the bottom of this put method, a method called putVal is called, but before we do that, we need to take a look at the method hash ().

Using the object .hashCode () directly, there may be repetition, so this hash is a bit of a disturbance to the generated hashcode to make it less repetitive.

You can also see here that HashMap only allows one null key

Static final int hash (Object key) {

Int h

Return (key = = null)? 0: (h = key.hashCode ()) ^ (h > 16)

}

3-2: let's take a look at this putVal method

PutVal source code:

Final V putVal (int hash, K key, V value, boolean onlyIfAbsent

Boolean evict) {

Node [] tab; Node p; int n, i

If ((tab = table) = = null | | (n = tab.length) = = 0)

N = (tab = resize ()) .length

If ((p = tab [I = (n-1) & hash]) = = null)

Tab [I] = newNode (hash, key, value, null)

Else {

Node e; K k

If (p.hash = = hash & &

((k = p.key) = = key | | (key! = null & & key.equals (k)

E = p

Else if (p instanceof TreeNode)

E = ((TreeNode) p) .putTreeVal (this, tab, hash, key, value)

Else {

For (int binCount = 0;; + + binCount) {

If ((e = p.next) = = null) {

P.next = newNode (hash, key, value, null)

If (binCount > = TREEIFY_THRESHOLD-1) / /-1 for 1st

TreeifyBin (tab, hash)

Break

}

If (e.hash = = hash & &

((k = e.key) = = key | | (key! = null & & key.equals (k)

Break

P = e

}

}

If (e! = null) {/ / existing mapping for key

V oldValue = e.value

If (! onlyIfAbsent | | oldValue = = null)

E.value = value

AfterNodeAccess (e)

Return oldValue

}

}

+ + modCount

If (+ + size > threshold)

Resize ()

AfterNodeInsertion (evict)

Return null

}

This source code still looks a little complicated, considering that many students may not have a very good data structure like me. I'll simplify it and extract the ideas to make it easier to understand.

Final V putVal (int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {

Node [] tab; Node p; int n, i

If ((tab = table) = = null | | (n = tab.length) = = 0) {

/ / expand when the data is null or the length is 0, and the expanded length is returned to n (as mentioned earlier, the bottom layer of hashMap is an array)

N = (tab = resize ()) .length

}

/ / some students may have wondered why the default length of the HashMap array is 16 when hashcode is so long. In fact, the last subscript is processed (n-1) & hash

If ((p = tab [I = (n-1) & hash]) = = null) {

/ / if there is no data in the subscript of the current array, that is to say, the data currently added is the first, just add it directly. You don't need to sort or anything.

Tab [I] = newNode (hash, key, value, null)

}

Else {

/ / the data subscript is found, and there is already data in it.

/ / you need to find out where the current data belongs and add it.

/ / it is also necessary to determine whether the current length is greater than the length set by us, and if it is greater than that, we will convert the chain into a red-black tree for easy search.

}

+ + modCount

/ / to judge whether the current length is greater than the length that needs to be expanded, in fact, it is easy to understand that the array can be full, but the chain cannot be full, but the performance of the chain will be very poor when the length exceeds a certain length.

If (+ + size > threshold)

Resize ()

/ / the operation after the node is inserted. Currently, there is no implementation of this, and there is an empty method in it.

AfterNodeInsertion (evict)

Return null

}

3-3: summarize the two situations of capacity expansion

When adding a data, when the underlying array is empty

After adding a data, determine whether the current number of data is larger than the size of threshold (need to expand capacity). If so, expand the capacity.

Note: because the data is a linked list that is specifically added to the array, there is no array out of bounds.

4. Take a look at the expansion code.

Expand the source code:

Final Node [] resize () {

Node [] oldTab = table

Int oldCap = (oldTab = = null)? 0: oldTab.length

Int oldThr = threshold

Int newCap, newThr = 0

If (oldCap > 0) {

If (oldCap > = MAXIMUM_CAPACITY) {

Threshold = Integer.MAX_VALUE

Return oldTab

}

Else if ((newCap = oldCap = DEFAULT_INITIAL_CAPACITY)

NewThr = oldThr 0) / / initial capacity was placed in threshold

NewCap = oldThr

Else {/ / zero initial threshold signifies using defaults

NewCap = DEFAULT_INITIAL_CAPACITY

NewThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)

} http://fk.zyfuke.com/ of Zhengzhou Professional Gynecology Hospital

If (newThr = = 0) {

Float ft = (float) newCap * loadFactor

NewThr = (newCap

< MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 　　(int)ft : Integer.MAX_VALUE); 　　} 　　threshold = newThr; 　　@SuppressWarnings({"rawtypes","unchecked"}) 　　Node[] newTab = (Node[])new Node[newCap]; 　　table = newTab; 　　if (oldTab != null) { 　　for (int j = 0; j < oldCap; ++j) { 　　Node e; 　　if ((e = oldTab[j]) != null) { 　　oldTab[j] = null; 　　if (e.next == null) 　　newTab[e.hash & (newCap - 1)] = e; 　　else if (e instanceof TreeNode) 　　((TreeNode)e).split(this, newTab, j, oldCap); 　　else { // preserve order 　　Node loHead = null, loTail = null; 　　Node hiHead = null, hiTail = null; 　　Node next; 　　do { 　　next = e.next; 　　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; 　　newTab[j + oldCap] = hiHead; 　　} 　　} 　　} 　　} 　　} 　　return newTab; 　　} 　　同样的把源码进行一下简单的分享，去除复杂的内容 　　// 这个扩容方法就是 　　// 1、找到新的容量大小和新的threshold大小 　　// 2、把旧的数据全部复制到新的数组中去 　　final Node[] resize() { 　　Node[] oldTab = table; 　　int oldCap = (oldTab == null) ? 0 : oldTab.length; 　　int oldThr = threshold; 　　int newCap, newThr = 0; 　　// 非第一次扩容 　　if (oldCap >

0) {

If (oldCap > = MAXIMUM_CAPACITY) {

Threshold = Integer.MAX_VALUE

Return oldTab

}

Else if ((newCap = oldCap = DEFAULT_INITIAL_CAPACITY)

NewThr = oldThr 0) {

NewCap = oldThr

}

/ / use the empty parameter construction method to expand the capacity for the first time, and use the construction method with the parameter of map to enter this expansion method for the first time.

Else {

NewCap = DEFAULT_INITIAL_CAPACITY

NewThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)

}

/ / use the construction method of initializing capacity or initializing capacity + initializing loading factor parameters to expand capacity for the first time

If (newThr = = 0) {

Float ft = (float) newCap * loadFactor

NewThr = (newCap < MAXIMUM_CAPACITY & & ft < (float) MAXIMUM_CAPACITY? (int) ft: Integer.MAX_VALUE)

}

Threshold = newThr

@ SuppressWarnings ({"rawtypes", "unchecked"})

Node [] newTab = (Node []) new Node [newCap]

Table = newTab

/ / copy all the old data to the new array

If (oldTab! = null) {

/ /

}

Return newTab

}

5. Summary (during the interview: please tell me about the expansion of HashMap):

The underlying data structure of HashMap is array + linked list + red-black tree.

The real data is stored in the linked list, and the length of the linked list is infinite. So at this point, a variable threshold is introduced.

When the data is added to the map for the first time, or the size of the data is larger than the size of the threshold, the capacity will be expanded.

First of all, let's talk about the non-first expansion, which is relatively simple.

1. If the current capacity is greater than or equal to the maximum capacity specified by HashMap, you can directly make threshold equal to the maximum value of Integer.

2. In general, the length of the current array will not be greater than the maximum, so the length of the new array is equal to 2 times that of the old array. If the new array length is less than the maximum specified by HashMap, and the old array length is greater than or equal to the default size and capacity size specified by HashMap (16), then the threshold is expanded by two times, otherwise it remains the same.

Not the first time to expand capacity

1. HashMap, there are four construction methods. The threshold variable of the empty parameter construction method is 0, and other construction methods threshold have initial values.

2. When the old threshold is greater than 0, the new array capacity size is equal to the old threshold size. The new threshold size is equal to the new array size of the load factor.

3. When the old threshold is less than 0, the new array size is equal to the default size (16), and the new threshold size is equal to the default capacity size and default load factor size.

The above is the editor for you to share how to carry out the HashMap expansion mechanism source code analysis, if you happen to have similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

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.