硬核破解HashMap源码
一、什么是HashMap
1.1 Hash是什么
Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值（也可以称之为哈希值）。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
Hash算法也被称为散列算法，Hash算法虽然被称为算法，但实际上它更像是一种思想。Hash算法没有一个固定的公式，只要符合散列思想的算法都可以被称为是Hash算法。
所以hash算法并不是唯一，只要尽量满足hash规则一般都可以称之为hash算法。
比如：
Integer的hash函数： public static int hashCode(int value) { return value; } String的hash函数： private int hash; //（全局变量） public int hashCode() { // eg1: hash=0 h=0 int h = hash; // Default to 0 // eg1: value={'k','1'} value.length=2 /** 只有第一次计算hash值时，才进入下面逻辑中。此后调用hashCode方法，都直接返回hash*/ if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { // eg1: val[0]=107 val[1]=49 h = 31 * h + val[i]; } // eg1: 31(31*0+107)+49=3366 hash = h; } return h; }
可见，hash算法完全可以自己定义和实现。一些特定场合可能需要不同的规则来处理不同的情况。
需要注意的是：哈希算法和哈希函数不是一个东西，哈希函数是哈希算法的一种实现，以后说哈希函数就行。计算哈希值的过程就叫哈希。
1.2 Map是什么
Java中的map是一种依照键存储元素的容器。map就是用于存储键值对（<key,value>）的集合类，也可以说是一组键值对的映射（数学概念）。注意，我这里说的只是map的概念，是为了通俗易懂，面试时候方便记忆，但是你自己一定要明白，在Java中map是一个接口，是和collection接口同一等级的集合根接口。
map的存储结构是这样的：
看起来就像是数据库中的关系表，有两个字段（或者说属性），keyset（键的集合）和values（值的集合），每一条记录都是一个entry（一个键值对）。
Map的特点
- 没有重复的key。一方面，key用set保存，所以key必须是唯一，无序的；另一方面，map的取值基本上是通过key来获取value，如果有两个相同的key，计算机将不知道到底获取哪个对应值；这时候有可能会问，那为什么我编程时候可以用put()方法传入两个key值相同的键值对？那是因为源码中，传入key值相同的键值对，将作为覆盖处理。
- 每个key只能对应一个value，多个key可以对应一个value。（这就是映射的概念，最经典的例子就是射箭，一排射手，一排箭靶，一个射手只能射中一个箭靶，而每个箭靶可能被不同射手射中。这里每个射手只有一根箭，不存在三箭齐发还都中靶这种骚操作。将射手和射中的靶子连线，这根线加射手加靶子就是一个映射）
- key,value都可以是任何引用类型（包括null）的数据（只能是引用类型）
- 赋值的时候必须同时给key和value赋值（其实也不算特点，就放在这吧）
Map和Hash的结合
在将键值对存入数组之前，将key通过哈希算法计算出哈希值，把哈希值作为数组下标，把该下标对应的位置作为键值对的存储位置，通过该方法建立的数组就叫做哈希表，而这个存储位置就叫做桶（bucket）。数组是通过整数下标直接访问元素，哈希表是通过字符串key直接访问元素，也就说哈希表是一种特殊的数组（关联数组），哈希表广泛应用于实现数据的快速查找（在map的key集合中，一旦存储的key的数量特别多，那么在要查找某个key的时候就会变得很麻烦，数组中的key需要挨个比较，哈希的出现，使得这样的比较次数大大减少。）
哈希表选用哈希函数计算哈希值时，可能不同的 key 会得到相同的结果，一个地址怎么存放多个数据呢？这就是哈希冲突（碰撞）。解决哈希冲突有两种方法，拉链法（链接法）和开放定址法。
拉链法：将键值对对象封装为一个node结点，新增了next指向，这样就可以将碰撞的结点链接成一条单链表，保存在该地址（数组位置）中。
HashMap是用哈希表（直接一点可以说数组加单链表）+红黑树实现的map类。
二、HashMap部分源码理解
接下来将介绍一下我对HashMap的put方法（也是关键）的一些理解。
2.1 关键变量
1.全局变量 //默认初始化容量:16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //最大容量:2^30 static final int MAXIMUM_CAPACITY = 1 << 30; //默认加载因子:0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; //树化阈值 static final int TREEIFY_THRESHOLD = 8; //非树化阈值（个人理解为不需要树化的最大阈值） static final int UNTREEIFY_THRESHOLD = 6; //最小树化容量 static final int MIN_TREEIFY_CAPACITY = 64; // 存储Node数组，可以理解为哈希表（的数组部分） transient Node<K, V>[] table; // 数据大小（多少个数据（key、value键值对）put进来了） transient int size; // 改动次数 transient int modCount; // 阈值 = capacity*loadFactor （容量*加载因子） int threshold; // 加载因子 final float loadFactor; 2.局部变量 // 存储数据的Node数组 Node<K, V>[] oldTab -> newTable // 阈值 threshold int oldThr -> newThr // 容量 capacity int oldCap -> newCap 3.Node对象 static class Node<K, V> implements Map.Entry<K, V> { final int hash; final K key; V value; Node<K, V> next; Node(int hash, K key, V value, Node<K, V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } （……一些方法） }
Node对象可以看成一个保存上下节点位置信息和本身内容的的一个节点！
创建一个HashMap其实只是创建一个空数组，没啥可说的。
这里记录一下transient的作用。简单地说，就是让某些被修饰的成员属性变量不被序列化，这一看好像很好理解，就是不被序列化，那么反序列化的时候，使用transient关键字修饰的变量会使用默认值（如果存在）或者直接为null。为什么这样做呢？主要是为了节省存储空间，也有可能是某些字段需要进行重新计算才能得到具体值等。
2.2 关键逻辑
往HashMap往里放一个元素的逻辑大致如下：
- 先计算key的哈希值
- 首先如果是空的table（数组），则初始化一个容量为16、阈值为12的新table。构建Node对象并计算应该对象存放的数组位置（下标、桶），然后把数据填入到该位置。
- 如果是非空table，构建Node对象并计算位置后，如果该位置为空，则把当前Node放在该位置；如果该位置被占用了，则进行链表操作。
- 链表操作：循环遍历该条链表，若有某个节点的key和当前Node的key相同，或者key相同且hash值也相同，则将该节点内容更新为最新的插入值；否则直接将该Node链接在该链表的最后。但是有可能进行resize()操作。
- resize()扩容
①当某个链表的长度大于8时，那么链表就会试图变为**红黑树**，如果当前数组table的长度小于64，就只进行resize()不转红黑树。或者当map里的数据要**大于阈值**的时候，也会进行resize()。 ②resize的过程：首先根据情况，调整新表的容量**newCap**和阈值**newThr**。**一般情况下是将容量提高一倍，阈值提高一倍**。若是老的表太大（>= `MAXIMUM_CAPACITY= 1 << 30`），那么将新的阈值设置为`Integer.MAX_VALUE=2^31-1`，并且表不进行扩容了。然后进行第二步，根据newCap和newThr，构建新数组，构建新数组的过程中，有可能会进行hash计算然后**位置重排**，最后**得到一个扩容好的新数组table**。这里的重新排列规则是这样的：每个节点的新位置要么在table数组的原下标位置，要么在**<原下标+原容量>**的位置，位置被占用则往后拉链表。
红黑树因为本人不了解，等了解了再更新。有兴趣的小伙伴可以自行学习。
以上介绍就是put方法的大致逻辑，要特别注意初始化容量的大小、加载因子默认是多少、初始化阈值是多少，怎么扩容何时扩容扩容多少等。
2.3 关键细节
2.3.1 hash()
// egx: key="k1" // eg1: key=0 static final int hash(Object key) { int h; /** * 按位异或运算（^）：两个数转为二进制，然后从高位开始比较，如果相同则为0，不相同则为1。 * * 扰动函数————(h = key.hashCode()) ^ (h >>> 16) 表示： * 将key的哈希code一分为二。其中： * 【高半区16位】数据不变。 * 【低半区16位】数据与高半区16位数据进行异或操作，以此来加大低位的随机性。 * 注意：如果key的哈希code小于等于16位，那么是没有任何影响的。只有大于16位，才会触发扰动函数的执行效果。 * todo 如果key的哈希code大于16位，那么前16位是没有任何影响的。后面剩余的的（originSize-16）位是：前（originSize-16）和后（originSize-16）位进行异或的结果 * */ // egx: 110100100110^000000000000=110100100110，由于k1的hashCode都是在低16位，所以原样返回3366 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); /** * case1: * h=高16位(全是0) and 低16位(有1) * h >>> 16 = 低16位全部消失，那么变成了32位(全是0) * h ^ (h >>> 16) = 原样输出 * case2： * h=高16位(有1) and 低16位(有1) * h >>> 16 = 低16位全部消失，那么变成了高16位(全是0)and低16位(有1) * h ^ (h >>> 16) = 不是原样输出 将原高16位于原低16位进行扰动。 */ }
扰动函数
计算key的哈希函数关键在于扰动函数。
(h = key.hashCode()) ^ (h >>> 16) >>> 表示无符号右移
扰动函数将key的哈希code一分为二。其中： * 【高半区16位】数据不变。 * 【低半区16位】数据与高半区16位数据进行异或操作，以此来加大低位的随机性。 可以这样理解：如果key的哈希code大于16位，那么前16位是没有任何影响的，后面剩余的的（originSize-16）位是：前（originSize-16）和后（originSize-16）位进行异或的结果，最后组成hash结果值。如果key的哈希code小于16位，那么key的哈希code值就是最后的hash结果值。
以下是扰动函数的具体计算例子，可以参考着理解。
2.3.2 resize()
resize()方法的逻辑在上文已经介绍过了，这里给一个具体的流程图便于大家理解。
2.3.3 put()
同样给一个具体的put实例和相关流程来便于大家理解。egx表示第几次put数据。
// eg1: hashMap.put(0, "a0"); // eg2: hashMap.put(1, "a1"); // eg3: hashMap.put(16, "a16"); // eg4: hashMap.put(32, "a32"); // eg5: hashMap.put(48, "a48");hashMap.put(64, "a64");hashMap.put(80, "a80");hashMap.put(96, "a96");hashMap.put(112, "a112"); // eg6: hashMap.put(128, "a128"); public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
// eg1: hash=0 key=0 value="a0" onlyIfAbsent=false evict=true // eg2: hash=1 key=1 value="a1" onlyIfAbsent=false evict=true // eg3: hash=16 key=16 value="a16" onlyIfAbsent=false evict=true // eg4: hash=32 key=32 value="a32" onlyIfAbsent=false evict=true // eg5: 由于执行步骤与eg4相似，故略过。 // eg6: hash=128 key=128 value="a128" onlyIfAbsent=false evict=true final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // todo tab是数组链表 Node<K, V>[] tab; //todo p是干嘛的? p是暂存该数组位置的头node Node<K, V> p; //todo n,i是干嘛的? 初步理解n是数组长度，i是临时数组下标 int n, i; // eg1: table=null // eg2: table是长度为16的Node数组，且table[1]=Node(1, 1, "a1", null) // eg3: table是长度为16的Node数组，且table[1]=Node(1, 1, "a1", null) ... table[6]=Node(6, 6, "a6", null) // eg4: table是长度为16的Node数组，且table[1]=Node(1, 1, "a1", null) ... table[6]=Node(6, 6, "a6", null) // eg6: table是长度为16的Node数组，且table[1]=Node(1, 1, "a1", null) ... table[6]=Node(6, 6, "a6", null) /** 如果是空的table，那么默认初始化一个长度为16的Node数组*/ if ((tab = table) == null || (n = tab.length) == 0) { // eg1: resize返回(Node<K, V>[]) new Node[16]，所以：tab=(Node<K, V>[]) new Node[16]， n=16 // todo 注意 resize()是关键 n = (tab = resize()).length; } // eg1: i = (n-1)&hash = (16-1)&0 = 1111&0000 = 0000 = 0; 即:p=tab[0]=null // eg2: i = (n-1)&hash = (16-1)&1 = 1111&0001 = 0001 = 1; 即:p=tab[1]=null // eg3: i = (n-1)&hash = (16-1)&16 = 1111&10000 = 0000 = 0; 即:p=tab[0]=Node(0, 0, "a0", null) // eg4: i = (n-1)&hash = (16-1)&32 = 1111&100000 = 0000 = 0; 即:p=tab[0]=Node(0, 0, "a0", null) // eg6: i = (n-1)&hash = (16-1)&128 = 1111&10000000 = 0000 = 0; 即:p=tab[0]=Node(0, 0, "a0", null) /** 如果计算后的下标i，在tab数组中没有数据，那么则新增Node节点*/ // todo (n - 1) & hash 因为n是2的n次幂，n-1的2进制一定是1111，所以可以判断当前节点应该放在哪个位置 if ((p = tab[i = (n - 1) & hash]) == null) { // eg1: tab[0] = newNode(0, 0, "a0", null) // eg2: tab[1] = newNode(1, 1, "a1", null) tab[i] = newNode(hash, key, value, null); } else { /** 如果计算后的下标i，在tab数组中已存在数据，则执行以下逻辑 */ // todo e 节点是什么节点，只是个中间节点 Node<K, V> e; // todo 临时的头结点的key K k; // eg3: p.hash==0, hash==16，所以返回false // eg4: p.hash==0, hash==32，所以返回false // eg6: p.hash==0, hash==128，所以返回false if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) { /** 如果与已存在的Node(第一个节点)是相同的key值*/ e = p; /** todo 就把头结点赋值给e */ } // eg3: p instanceof Node，所以为false // eg4: p instanceof Node，所以为false // eg6: p instanceof Node，所以为false else if (p instanceof TreeNode) { /** 如果p是树节点*/ // todo 红黑树节点这里不懂 e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value); } else { /** 如果与已存在的Node(第一个节点)不是相同的key值，并且是普通节点，则循环遍历链式Node，并对比hash和key，如果都不相同，则将新的Node拼装到链表的末尾。如果相同，则进行更新。*/ for (int binCount = 0; ; ++binCount) { // eg3: p.next == null // eg4-loop1: p.next == Node(16, 16, "a16", null) 不为空 // eg4-loop2: p.next == null /** 获得p节点的后置节点，赋值给e。直到遍历到横向链表的最后一个节点，即：该节点的next后置指针为null */ if ((e = p.next) == null) { // eg3: p.next = newNode(16, 16, "a16", null); // eg4-loop2: p.next == newNode(32, 32, "a32", null); // eg6: p.next == newNode(128, 128, "a128", null); p.next = newNode(hash, key, value, null); // eg3: binCount == 0 // eg4-loop2: binCount == 1 /** binCount从0开始，如果Node链表大于8个Node，那么试图变为红黑树 */ if (binCount >= TREEIFY_THRESHOLD - 1) { // eg6: tab={newNode(0, 0, "a0", ［指向后面1个链表中的7个node］), newNode(1, 1, "a1", null)}, hash=128 // todo 横向链表试图变为红黑树, 注意128已经加到链表后面了 treeifyBin(tab, hash); } // eg3: break // eg4-loop2: break break; } // eg4-loop1: e.hash==16 hash==32 所以返回false /** 针对链表中的每个节点，都来判断一下，是否待插入的key与已存在的链表节点相同，如果相同，则跳出循环，并在后续的操作中，将该节点内容更新为最新的插入值 */ if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { break; } // eg4-loop1: p=e=Node(16, 16, "a16", null) // todo e赋值给p，进行下一个节点的遍历（对比） p = e; } } // eg3: e = null // eg4: e = null /** 如果存在相同的key值,e就不是为null*/ if (e != null) { // egx: String oldValue = "v1" V oldValue = e.value; // egx: onlyIfAbsent=false if (!onlyIfAbsent || oldValue == null) { // egx: e = Node(3366, "k1", "v2", null) /** 则将新的value值进行更新*/ e.value = value; } afterNodeAccess(e); // egx: 返回oldValue="v1" return oldValue; } } // eg1: modCount==0 ++modCount==1 // eg2: modCount==1 ++modCount==2 // eg3: modCount==7 ++modCount==8 // eg4: modCount==8 ++modCount==9 ++modCount; // eg1: size=0, threshold=12 // eg2: size=1, threshold=12 // eg3: size=7, threshold=12 // eg4: size=8, threshold=12 //todo 添加数据后是否超过了阈值，超过了就重新resize if (++size > threshold) { resize(); } afterNodeInsertion(evict); /** doing nothing */ return null; }
/** * table扩容 * 常量命名解释： * Tab——>Table 表 * Cap——>Capacity 容量 * Thr——>Threshold 阈值 */ final Node<K, V>[] resize() { // eg1: table=null // eg6: table != null Node<K, V>[] oldTab = table; // eg1: oldCap=0 // eg6: oldCap=16 int oldCap = (oldTab == null) ? 0 : oldTab.length; // eg1: oldThr=threshold=0 // eg6: oldThr=threshold=12 int oldThr = threshold; int newCap = 0; int newThr = 0; /** 第一步：根据情况，调整新表的容量newCap和阈值newThr*/ if (oldCap > 0) { /** 如果老table的长度大于等于2^30(1 << 30) 1后面有30个0 todo 表到了最大默认容量后就不扩容了 */ if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; /** 2^31-1 1后面有30个1 */ return oldTab; } /** 如果 将老Table的长度增长2倍作为新的容量长度(newCap)，是否小于2^30(1 << 30) 并且 老Table长度是否大于等于16(1 << 4)*/ // todo 新容量提高一倍，新阈值提高一倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) { // eg6: newCap=32, newThr=24 // 新阈值提高一倍 newThr = oldThr << 1; } } else if (oldThr > 0) { newCap = oldThr; } else { // eg1: oldCap=0 newCap=16 newThr=0.75f*16=12 newCap = DEFAULT_INITIAL_CAPACITY; /** 默认【表容量】为16(1 << 4) */ newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); /** 默认【阈值因子】为0.75f */ } //todo 这是什么情况？应该是位溢出判断 if (newThr == 0) { float ft = (float) newCap * loadFactor; //算出来的阈值 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE); } // eg1: threshold=newThr=12 // eg6: threshold=newThr=24 threshold = newThr; /** 第二步：根据newCap和newThr，构建新数组 todo 构建新数组的过程中，有可能会进行hash计算然后位置重排 */ /** 初始化新表*/ @SuppressWarnings({"rawtypes", "unchecked"}) Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap]; // eg1: table=newTab=(Node<K, V>[]) new Node[16]; // eg6: table=newTab=(Node<K, V>[]) new Node[32]; table = newTab; // eg1: oldTab=null if (oldTab != null) { /** 如果老的table里有数据，则进行数据迁移*/ // eg6: oldCap=16 /** 循环纵向数组中的每个槽位Cap进行数据迁移计算 */ for (int j = 0; j < oldCap; ++j) { Node<K, V> e; // eg6-loop1: j=0, e=oldTab[0]=Node(0, 0, "a0", nodeRef) // eg6-loop2: j=1, e=oldTab[1]=Node(1, 1, "a1", null) if ((e = oldTab[j]) != null) { //todo e为老数组的首节点，如果首节点有数据 // eg6-loop1: oldTab[0] = null // eg6-loop2: oldTab[1] = null oldTab[j] = null; // todo 老的首节点置为null // eg6-loop1: e.next=Node(16, 16, "a16", nodeRef) // eg6-loop2: e.next==null if (e.next == null) { /** 没有后置节点，说明e是最后一个节点*/ // eg6-loop2: e.hash==1, newCap=32, 1&(32-1)==1 即：newTab[1]=Node(1, 1, "a1", null) // todo 最后一个节点会重新计算新的槽位 newTab[e.hash & (newCap - 1)] = e; } else if (e instanceof TreeNode) { /** e是树节点*/ ((TreeNode<K, V>) e).split(this, newTab, j, oldCap); } else { // todo 如果还有后续节点 Node<K, V> loHead = null; Node<K, V> loTail = null; Node<K, V> hiHead = null; Node<K, V> hiTail = null; Node<K, V> next; do { // todo 计算链表 // eg6-loop1-loop1: next=e.next=Node(16, 16, "a16", nodeRef) // eg6-loop1-loop2: next=e.next=Node(32, 32, "a32", nodeRef) // eg6-loop1-loop3: next=e.next=Node(48, 48, "a48", nodeRef) // eg6-loop1-loop4: next=e.next=Node(64, 64, "a64", nodeRef) // eg6-loop1-loop5: next=e.next=Node(80, 80, "a80", nodeRef) // eg6-loop1-loop6: next=e.next=Node(96, 96, "a96", nodeRef) // eg6-loop1-loop7: next=e.next=Node(112, 112, "a112", nodeRef) // eg6-loop1-loop8: next=e.next=Node(128, 128, "a128", nodeRef) // eg6-loop1-loop9: next=e.next=null next = e.next; /** 获得oldTab数组下标的Node列表的下一个节点*/ // eg6-loop1-loop1: e.hash=0, oldCap=16, 00000000&10000==00000==0 // eg6-loop1-loop2: e.hash=16, oldCap=16, 00010000&10000==10000==16 // eg6-loop1-loop3: e.hash=32, oldCap=16, 00100000&10000==00000==0 // eg6-loop1-loop4: e.hash=48, oldCap=16, 00110000&10000==10000==16 // eg6-loop1-loop5: e.hash=64, oldCap=16, 01000000&10000==00000==0 // eg6-loop1-loop6: e.hash=80, oldCap=16, 01010000&10000==00000==16 // eg6-loop1-loop7: e.hash=96, oldCap=16, 01100000&10000==00000==0 // eg6-loop1-loop8: e.hash=112, oldCap=16, 01110000&10000==10000==16 // eg6-loop1-loop9: e.hash=128, oldCap=16, 10000000&10000==10000==0 if ((e.hash & oldCap) == 0) { /** 计算e在老表oldTab的下标，如果是第一个Node，即：下标index==0 todo 这里是为啥？*/ if (loTail == null) { // eg6-loop1-loop1: loHead=e=Node(0, 0, "a0", nodeRef) loHead = e; /** 将loHead指向oldTab数组第一个下标的第一个元素e */ } else { // eg6-loop1-loop3: loTail.next=e=Node(32, 32, "a32", nodeRef) // eg6-loop1-loop5: loTail.next=e=Node(64, 64, "a64", nodeRef) // eg6-loop1-loop7: loTail.next=e=Node(96, 96, "a96", nodeRef) // eg6-loop1-loop9: loTail.next=e=Node(128, 128, "a128", nodeRef) loTail.next = e; /** 建立新的链表 */ } // eg6-loop1-loop1: loTail=e=Node(0, 0, "a0", nodeRef) // eg6-loop1-loop3: loTail=e=Node(32, 32, "a32", nodeRef) // eg6-loop1-loop5: loTail=e=Node(64, 64, "a64", nodeRef) // eg6-loop1-loop7: loTail=e=Node(96, 96, "a96", nodeRef) // eg6-loop1-loop9: loTail=e=Node(128, 128, "a128", nodeRef) loTail = e; /** 将loTail指向oldTab数组第一个下标的最后一个元素e*/ } else { /** 如果不是oldTab中的第一个下标Node*/ if (hiTail == null) { // eg6-loop1-loop2: hiHead=e=Node(16, 16, "a16", nodeRef) hiHead = e; } else { // eg6-loop1-loop4: hiTail.next=e=Node(48, 48, "a48", nodeRef) // eg6-loop1-loop6: hiTail.next=e=Node(80, 80, "a80", nodeRef) // eg6-loop1-loop8: hiTail.next=e=Node(112, 112, "a112", nodeRef) hiTail.next = e; /** 建立新的链表 */ } // eg6-loop1-loop2: hiTail=e=Node(16, 16, "a16", nodeRef) // eg6-loop1-loop4: hiTail=e=Node(48, 48, "a48", nodeRef) // eg6-loop1-loop6: hiTail=e=Node(80, 80, "a80", nodeRef) // eg6-loop1-loop8: hiTail=e=Node(112, 112, "a112", nodeRef) hiTail = e; } } // eg6-loop1-loop1: e=next=Node(16, 16, "a16", nodeRef) // eg6-loop1-loop2: e=next=Node(32, 32, "a32", nodeRef) // eg6-loop1-loop3: e=next=Node(48, 48, "a48", nodeRef) // eg6-loop1-loop4: e=next=Node(64, 64, "a64", nodeRef) // eg6-loop1-loop5: e=next=Node(80, 80, "a80", nodeRef) // eg6-loop1-loop6: e=next=Node(96, 96, "a96", nodeRef) // eg6-loop1-loop7: e=next=Node(112, 112, "a112", nodeRef) // eg6-loop1-loop8: e=next=Node(128, 128, "a128", nodeRef) // eg6-loop1-loop9: e=next=null while ((e = next) != null); /** do-while */ // eg6-loop1: loTail=Node(128, 128, "a128", null) if (loTail != null) { loTail.next = null; // eg6-loop1: j=0, newTab[0]=loHead=Node(0, 0, "a0", nodeRef) newTab[j] = loHead; } // eg6-loop1: loTail=Node(112, 112, "a112", nodeRef) if (hiTail != null) { // eg6-loop1: loTail=Node(112, 112, "a112", null) hiTail.next = null; // eg6-loop1: j=0, oldCap=16, newTab[16]=hiHead=Node(16, 16, "a16", nodeRef) newTab[j + oldCap] = hiHead; } } } } } // eg1: newTab = (Node<K, V>[]) new Node[16] // eg6: newTab = (Node<K, V>[]) new Node[32] return newTab; }
/** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */ // eg6: hash=128 // tab[0]= Node(0, 0, "a0", nodeRef) // ——>Node(16, 16, "a16", nodeRef) // ——>Node(32, 32, "a32", nodeRef) // ——>Node(48, 48, "a48", nodeRef) // ——>Node(64, 64, "a64", nodeRef) // ——>Node(80, 80, "a80", nodeRef) // ——>Node(96, 96, "a96", nodeRef) // ——>Node(112, 112, "a112", nodeRef) // ——>Node(128, 128, "a128", null) // tab[1]= Node(1, 1, "a1", null) final void treeifyBin(Node<K, V>[] tab, int hash) { int n; int index; Node<K, V> e; // eg6: tab !=null, tab.length=16 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) { /** 当表tab的长度小于64时，只扩展数组大小，不转换为树 todo 所以转为树的条件是：①（横向）链表的长度大于等于8时 ②表tab的长度大于64时 */ // eg6: 执行resize() todo 条件 ：（横向）链表的长度大于等于8，并且数组长度小于64 resize(); } else if ((e = tab[index = (n - 1) & hash]) != null) { /** 如果新增的node要插入的数组位置已经有node存在了，取出该位置的node节点*/ TreeNode<K, V> hd = null; /** 头节点*/ TreeNode<K, V> tl = null; /** 尾节点*/ do { /** do while 只是把node转为TreeNode */ /** 将Node转化为TreeNode——> new TreeNode<>(p.hash, p.key, p.value, next);*/ TreeNode<K, V> p = replacementTreeNode(e, null); /** 将每个Node转换为TreeNode，并且用prev和next指针进行链接，并以hd为头节点*/ if (tl == null) { hd = p; } else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); /** 如果头节点hd不为null，则进行树型化操作*/ if ((tab[index] = hd) != null) { hd.treeify(tab); } } }
三、注意事项
- 在构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算。哈希table的初始化容量为16，初始化阈值为12。
- 扩容一般是把容量扩容到原来的2倍，阈值也是扩大到原来的2倍。
- 扩容时机：当某个链表的长度大于8时会尝试转为红黑树，但是当数组table小于64时只进行扩容resize()。当map的size大于阈值时也会进行扩容。
- 转为红黑树的时机：数组长度大于64，且某条链表长度大于8。
- 扩容时数组重新排列的规则是这样的：每个节点的新位置要么在table数组的原下标位置，要么在<原下标+原容量>的位置，位置被占用则往后拉链表。
- 若是老的表太大（>= MAXIMUM_CAPACITY= 1 << 30），那么将新的阈值设置为Integer.MAX_VALUE=2^31-1，并且table表不进行扩容。
- 计算某个数组的位置的方法：(n - 1) & hash，n是数组table的容量。eg: i = (n-1)&hash = (16-1)&0 = 1111&0000 = 0000 = 0;
本人能力有限，红黑树的部分等学习了再来更新。还有一些面试题问题就不在这整理了，这里只记录一些原理和分析过程。
#Java##程序员##计算机##Java学习#
投递深圳同为数码等公司10个岗位