HashMap source code reading

Hongchen's blog 2021-01-24 11:53:31
hashmap source code reading


This article is based on JDK1.8  > After reading this article, it is expected that 25 minute ( Because there is a lot of source code , Better viewing experience on the computer screen )

Abstract

HashMap I believe this is one of the most frequent interview sites , It should be one of the bad interview questions , It's also Java The most common data type used to handle key value pairs in . So let's focus on JDK8 Of HashMap Let's learn together !

The main method

Key variables :

 /**
* The default initial capacity - MUST be a power of two.
* Initial capacity Must be 2 Power of power
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
* Maximum capacity size
* Beyond this value will threshold It is amended as follows Integer.MAX_VALUE, The array is not expanded
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
* Load factor Why 0.75? Because in Statistics hash The conflicts fit the Poisson distribution ,7-8 The conflict between them is minimal
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
* If the linked list is greater than this value, it will be treelized
* Be careful : Treeing is not the whole map Linked list , It's a linked list that's greater than this threshold
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
* Less than this value will reverse the tree
*/
static final int UNTREEIFY_THRESHOLD = 6;

Four construction methods :

// Construction method 1
// Specify the initial capacity size , Load factor
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) //1<<30 The maximum capacity is Integer.MAX_VALUE;
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//tableSizeFor This method is used to find greater than or equal to initialCapacity The smallest 2 The power of
this.threshold = tableSizeFor(initialCapacity);
}
// Construction method 2
// In fact, the above construction method is called 1 The default value given by the load factor 0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// Construction method 3
// Space parameter structure , All use default values
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// Construction method 4
// Compared to the other three , Initialize the
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;//0.75f
// Called putVal Method , and putVal Methods include resize Method , There is initialization
putMapEntries(m, false);
}

A brief summary of the four construction methods :

1、 The first three constructors are not initialized , It is used to initialize
2、 Construction method 4 It's equivalent to using put Method , So it's initialized

hashmap->hash()

/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
* Calculation key.hashCode() And the higher bit of the hash (XOR) Expand to lower .
* Because the table uses 2 The power mask of , So hash sets that only change in the bits above the current mask will always conflict .
* ( The well-known example is to include continuous integers in a small table Float Key set .) therefore , We applied a transformation ,
* Will expand down to the higher impact . At speed , There is a trade-off between practicality and bit expansion quality .
* Since many common hash sets have been reasonably distributed ( So you can't benefit from expansion ),
* And because we use trees to handle a lot of conflicts in containers , Therefore, we only use the cheapest way to process some shifted bits XOR,
* To reduce system losses , And the impact of merging the highest positions , Otherwise, due to the limitation of table scope , These bits will never be used in index calculations .
*/
static final int hash(Object key) {
int h;
// Why? ^ (h >>> 16) More hashing , Performance considerations , Convenient bit operation
// Convenient in put,get In the method (n - 1) & hash Compute array subscripts
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
//HashMap in key The value can be null, notice 0 So we can judge null The value must be stored in the first position of the array
}

hashmap->put()

The main logic :

Here is the source code ( Annotated ):


/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
* // Associate the specified value with the specified key in this map . If the mapping previously contains the mapping of the key , Then the old value will be replaced .
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
// hold key Go first hash Get it in a minute hash value
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value //if true The original value is not changed
* @param evict if false, the table is in creation mode.//if false Then the table is in creation mode
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// Array + Linked list + Red and black trees , List type (Node Generic ) Array , Each element represents a linked list , Then each element is called a bucket
//HashMap Every element of , They are all a node of the linked list (Entry<K,V>) So this right here is Node<K,V>
//tab: bucket p: bucket n: Hash table array size i: The array subscript ( Location of barrel )
Node<K,V>[] tab; Node<K,V> p; int n, i;
//1. Determine whether the current bucket is empty , Empty calls resize() Method (resize Will determine whether to initialize )
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2. To determine if there is hash Conflict , According to the reference key And key Of hash Value to find the specific bucket and empty it , Empty is no conflict Just build a new barrel
//? Why use (n - 1) & hash Compute array subscripts , Those who are interested can learn more about
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//3. There is a conflict , Handle hash Conflict
else {
Node<K,V> e; K k;// They are all temporary variables
//4. Judge the current bucket's key Whether it is related to the participation key Agreement , Consistency exists , Put the current bucket p Assign a value to e, Covering the original value Steps in 10 Conduct
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//5. If the current bucket is a red black tree , use putTreeVal() Method write Assign a value to e
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//6. Then the current bucket is a linked list Traversing the linked list
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//7. The tail interpolation , The next node in the list is null( End of list ), Just new A new node is written after the current linked list node
p.next = newNode(hash, key, value, null);
//8. Judge whether it is greater than the threshold , Need linked list to red black tree
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//binCount from 0 At the beginning , So when binCount by 7 when , The length of the list is 8( Count the node at the beginning of the array slot , The total length of 9), You need a tree barrel
treeifyBin(tab, hash);
break;
}
//9. And steps 4 Agreement , If the list key Being is jumping out step 10 Cover the original value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//10. There is the same key Of Node node , Then cover the original value
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent by true: Don't change the original value ;false: Change the original value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//LinkedHashMap The callback method used
afterNodeAccess(e);
return oldValue;
}
}
/* Record the number of modifications, and identify
be used for fast-fail, because HashMap Non-thread safety , In the face of HashMap When you iterate ,
If the participation of other threads causes during HashMap The structure has changed ( such as put,remove Wait for the operation ),
You need to throw an exception ConcurrentModificationException
*/
++modCount;
//11. Capacity exceeds threshold , Capacity expansion
if (++size > threshold)
resize();
//LinkedHashMap The callback method used
afterNodeInsertion(evict);
return null;
}

So let's summarize put Method :

1、 Start , Enter the reference key、value
2、 Judge the present table Is it empty or length=0?
yes , To expand ,(resize() Method to determine whether to initialize )
no , according to key Work out hash Value and get the index of the inserted array
Judge the one you found table[i] Is it empty ?
yes , Directly inserted into the , Go to the next step
no , Judge key Whether there is ?
yes , Directly covering the corresponding value, Go to the next step 3
no , To judge the current table[i] Is it right? treeNode?
yes , Use the red black tree to insert key、value
no , Start traversing the list, ready to insert
Determine whether the length of the linked list is greater than 8?
yes , Linked list to red black tree insert key、value
no , Insert as a linked list key、value If key Existence directly covers correspondence value
3、 Judge map Of size() Is it greater than the threshold ?
yes Just expand the capacity resize()
4、 end 

hashmap->get()


public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods.
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//1、 Judge that the current array is not empty and the length is greater than 0 && from key Of hash Value to find the bucket under the corresponding array ( It could be a red black tree or a linked list )
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//2、 First determine the first node of the bucket If key Agreement return
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//3、 The next node is not empty && The judgment is that the red black tree is still a linked list
if ((e = first.next) != null) {
//4、 If it's a red-black tree The value is determined by the way of red black tree
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// Otherwise it's a linked list , Ergodic value
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}

So let's summarize get() Method :

1、 Start , Enter the reference key
2、 Judge that the current array length is not empty &&length>0
yes return null;
no , To determine the first node , If key accord with , return
Then judge whether the next node is empty
yes ,return null
no , Judge whether it is a red black tree ?
yes , Take the value according to the way of red black tree
no , Traversing linked list values
3、 end 

hashmap->resize()

/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
* Initialize or increase table size . If it is empty , The allocation is based on the initial capacity target maintained in the field threshold .
* otherwise , Because we're using 2 The power of , So each bin The elements in must maintain the same index , Or in the new table 2 The power shift of .
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//1、 Original array expansion
if (oldCap > 0) {
// If the length of the original array is greater than the maximum capacity , Maximize the threshold ,return
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// The size of the original array 、 The thresholds are doubled
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// The specified initialCapacity Construction method of , The original threshold is used as the new capacity
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// Use empty parameters to construct , By default
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//0.75*16=12
}
// The specified initialCapacity Construction method of , The new threshold is 0, Then calculate the new threshold
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"})
//2、 Initialize the array with the new array size
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// If it's just the initialization process , To this end return newTab
table = newTab;
//3、 Start the main work of capacity expansion , Data migration
if (oldTab != null) {
// Traverse the original array and start copying the old data
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;// Clear the old table with
// A single element in the original array , Copy directly to the new table
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// If the element type is red black tree , In the form of a red black tree
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// This code is cleverly designed , It's all connected
// Two types of linked lists are defined first And head and tail nodes High order linked list and low order linked list
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// Traverse the nodes of the original list in order
do {
next = e.next;
// This is a core judgment condition , Those who are interested can learn more about ? Why do you do this
//=0 Then put it in the low linked list
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// Otherwise, put it in the high-level list
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
// The above is actually split the original linked list into two high and low linked lists
} while ((e = next) != null);
// Put the whole low order list in the new array j Location
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// Put the whole high-order list in the top of the new array j+oldCap position
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

To sum up resize() Method :

1、 Start , Get the original array
2、 Expand the original array
2.1 If the capacity of the original array reaches the maximum , No more expansion ,return Original array
2.2 Double the capacity and threshold of the original array
3、 As specified for initialization initialCapacity Construction method of , The original threshold is used as the new capacity
4、 Such as null parameter construction used in initialization , With default capacity and default threshold
5、 As specified for initialization initialCapacity Construction method of , threshold =0, Calculate the new threshold
6、 Initialize the array with the new capacity , If it's initialization , End returns the new array
7、 Start expanding , Do data migration
7.1 Iterate over the original array copy Data to a new array
7.1.1 If there is only one element in the array , Copy directly
7.1.2 If the element is a red black tree number type , It is treated as a red black tree
7.1.3 Processing the linked list of the original array
Define a high-order list 、 A low order list ( Split the original list )
Start a cycle , Traverse the original list
Judge the condition e.hash & oldCap == 0?
yes , Put these linked list nodes in the lower linked list
no , Put it in a high-level list
The loop ends , Traverse the list to complete
Put the whole low list into a new array j Location
Put the whole high-order list into a new array j+oldCap Location
7.2 The loop ends , Traversing the old array completes
8、 Return a new array 

I think it's going to be right after reading HashMap Have a certain understanding , I hope I can help you in the interview or work !

Hongchen Gossip

Doesn't it look a little cool , Its name is ” The house “, Wenyuhe Park in Beijing .

I was bored at home with my girlfriend last week and went out for a walk , So we found a park , The park is still bleak in autumn and winter .

It's the end of the year , The epidemic is scattered , I hope it will be over soon !peaceeeee

Thank you for reading

Pretty good , If you find something wrong , It can be put forward backstage or in comments , I'll change it .
Thank you for reading , Welcome and thank you for your attention !

版权声明
本文为[Hongchen's blog]所创,转载请带上原文链接,感谢
https://javamana.com/2021/01/20210124115156691e.html

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云