|
（一）hash算法
static final int hash(Object key) {
? ? ? ? int h;
? ? ? ? return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); ?// 这是key的hash算法，首先得到hashcode，然后hashcode右移16位得到高16位，接着进行异或操作，
?? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ? ? // 使原来hashcode的低16位与右移后的高16位尽可能计算，减少hash冲突的概率，称之为扰动处理
? ? }
（二）put存入数据
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
? ? ? ? ? ? ? ? ? ?boolean evict) { ? ? ? ? ? ? ? ? ? ? ? ? ? // hashmap存入数据
? ? ? ? Node<K,V>[] tab; Node<K,V> p; int n, i; ? ? ? ? ? ? ? // 初始化操作，tab初始是空的，p作为hash寻址的节点
? ? ? ? if ((tab = table) == null || (n = tab.length) == 0) ? // 第一次插入数据，hashmap的数组是空的
? ? ? ? ? ? n = (tab = resize()).length; ? ? ? ? ? ? ? ? ? ? ?// 数组是空的，所以扩容，并创建新的数组tab
? ? ? ? if ((p = tab[i = (n - 1) & hash]) == null) ? ? ? ? ? ?// hash寻址算法，即对hash%n-1 取模计算得到所在位置的数组元素p，并判断该位置有没有填充数据
? ? ? ? ? ? tab[i] = newNode(hash, key, value, null); ? ? ? ? // 如果该位置没有填充数据，就根据key value创建新的节点元素并放在该位置
? ? ? ? else { ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 数组不为空，hash寻址的位置已经有节点元素了
? ? ? ? ? ? Node<K,V> e; K k;
? ? ? ? ? ? if (p.hash == hash &&
? ? ? ? ? ? ? ? ((k = p.key) == key || (key != null && key.equals(k)))) ?// 节点元素p的hash值和传入的相同，节点元素p的key值也和传入的相同
? ? ? ? ? ? ? ? e = p; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 将节点元素p 赋值给新的变量e，e代表要替换p的新节点，并在底下e.value = value做更新操作，即更新节点元素的值，返回节点的旧值
? ? ? ? ? ? else if (p instanceof TreeNode) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 节点元素p是红黑树节点，即树的根节点root
? ? ? ? ? ? ? ? e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); ?// 将key value插入到红黑树中，可能是更新红黑树的旧节点的值，可能是增加新节点，并得到新的节点e
? ? ? ? ? ? else { ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 说明节点元素p不是红黑树节点，只有是链表结构上的节点
? ? ? ? ? ? ? ? for (int binCount = 0; ; ++binCount) { ? ? ? ? ? ? ? ? ? // binCount代表在链表上寻址的次数，一条链表上的节点的数量<=7，如果>=8该链表就要转换为红黑树结构，所有节点转为TreeNode
? ? ? ? ? ? ? ? ? ? if ((e = p.next) == null) { ? ? ? ? ? ? ? ? ? ? ? ? ?// 链表节点的next是空的，并且e代表链表的尾节点
? ? ? ? ? ? ? ? ? ? ? ? p.next = newNode(hash, key, value, null); ? ? ? ?// 尾节点是空的，就创建新的节点并作为尾节点
? ? ? ? ? ? ? ? ? ? ? ? if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st ? // 一条链表上的插入节点的数量>=8
? ? ? ? ? ? ? ? ? ? ? ? ? ? treeifyBin(tab, hash); ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 链表转换为红黑树结构，所有节点转为TreeNode
? ? ? ? ? ? ? ? ? ? ? ? break; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 跳出循环再链表上寻址
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? if (e.hash == hash &&
? ? ? ? ? ? ? ? ? ? ? ? ((k = e.key) == key || (key != null && key.equals(k)))) ?// 在链表上找到一个hash值相同、key也相同的节点，跳出循环后直接用传入的值更新旧节点的值
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? p = e; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 说明本次循环既没有找到空的尾节点，也不是key相同的，则将e赋值给p，使p节点成为链表的下一个节点，跟e = p.next构成循环往后寻址，直到更新旧节点或插入新节点 ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? if (e != null) { // existing mapping for key ? ? ?// e代表新的节点元素，可以是更新后的节点，也可以是新插入的节点
? ? ? ? ? ? ? ? V oldValue = e.value; ? ? ? ? ? ? ? ? ? ? ? ? // 得到节点元素的旧值，对于更新的节点代表旧值，对于插入的节点代表新值
? ? ? ? ? ? ? ? if (!onlyIfAbsent || oldValue == null) ? ? ? ?
? ? ? ? ? ? ? ? ? ? e.value = value; ? ? ? ? ? ? ? ? ? ? ? ? ?// 用传入的值作为新节点的值
? ? ? ? ? ? ? ? afterNodeAccess(e); ? ? ? ? ? ? ? ? ? ? ? ? ? // 这是linkedhashmap的扩展
? ? ? ? ? ? ? ? return oldValue;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? ++modCount; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// modCount代表修改的次数，每更新节点或插入新节点都代表一次修改
? ? ? ? if (++size > threshold) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// size代表节点数量，即节点数量超过阈值，就要扩容
? ? ? ? ? ? resize(); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 扩大数组tab的容量，否则hash碰撞太频繁、插入的节点都最终挂载红黑树上导致树的层级过高，降低索引的效率
? ? ? ? afterNodeInsertion(evict); ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 这是linkedhashmap的扩展
? ? ? ? return null;
? ? }
?? ?
（三）扩容和rehash
final Node<K,V>[] resize() {
? ? ? ? Node<K,V>[] oldTab = table; ? ? ? ? ? ? ? ? ? ? ? ? // 扩容之前的旧数组
? ? ? ? int oldCap = (oldTab == null) ? 0 : oldTab.length; ?// 旧数组的容量，取实际元素的个数
? ? ? ? int oldThr = threshold;
? ? ? ? int newCap, newThr = 0;
? ? ? ? if (oldCap > 0) { ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 旧数组已有数据
? ? ? ? ? ? if (oldCap >= MAXIMUM_CAPACITY) { ? ? ? ? ? ? ? // 如果旧数组的数据量已经超过最大容量，无法再扩容直接return现有的数组
? ? ? ? ? ? ? ? threshold = Integer.MAX_VALUE;
? ? ? ? ? ? ? ? return oldTab;
? ? ? ? ? ? }
? ? ? ? ? ? else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
? ? ? ? ? ? ? ? ? ? ?oldCap >= DEFAULT_INITIAL_CAPACITY) ? ? ? ? ? ? ? ? ? ? ? // 旧数组的容量乘以2仍然小于最大容量，那么新数组的容量和阈值都扩大2倍
? ? ? ? ? ? ? ? newThr = oldThr << 1; // double threshold
? ? ? ? }
? ? ? ? else if (oldThr > 0) // initial capacity was placed in threshold ? ? ? // 旧数组没有插入过数据，但在创建hashmap的时候初始化过阈值，则以阈值作为新的容量
? ? ? ? ? ? newCap = oldThr;
? ? ? ? else { ? ? ? ? ? ? ? // zero initial threshold signifies using defaults ? // 首次扩容，初始化数组的容量为16，阈值为16*0.75=12
? ? ? ? ? ? newCap = DEFAULT_INITIAL_CAPACITY;
? ? ? ? ? ? newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
? ? ? ? }
? ? ? ? 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<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; ? ? ? ? ? ? ? ? ? ? ? ?// 根据新的容量创建新的空数组
? ? ? ? table = newTab;
? ? ? ? if (oldTab != null) { ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 旧数组存在
? ? ? ? ? ? for (int j = 0; j < oldCap; ++j) { ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 对旧数组进行遍历
? ? ? ? ? ? ? ? Node<K,V> e;
? ? ? ? ? ? ? ? if ((e = oldTab[j]) != null) { ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 将数组的节点赋值给e 进行保存
? ? ? ? ? ? ? ? ? ? oldTab[j] = null; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 释放数组节点的空间，以便被GC回收
? ? ? ? ? ? ? ? ? ? if (e.next == null) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 节点e的next为空，说明数组的这个位置上是个单节点
? ? ? ? ? ? ? ? ? ? ? ? newTab[e.hash & (newCap - 1)] = e; ? ? ? ? ? ? ? ? ? ? ? ? // 节点e用旧的hash值对新的容量取模，并保存到新数组中
? ? ? ? ? ? ? ? ? ? else if (e instanceof TreeNode) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 节点e是红黑树节点的话，说明这个节点挂的是棵红黑树
? ? ? ? ? ? ? ? ? ? ? ? ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); ? ? ? ? // 节点e作为根节点root，对红黑树进行拆分，分为两个更小的链表或红黑树
?? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ? ? //将原来的红黑树更均匀的插入到新数组中并降低树的高度
? ? ? ? ? ? ? ? ? ? else { // preserve order ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 既不是单节点，也不是树节点，那必然是链表节点
? ? ? ? ? ? ? ? ? ? ? ? Node<K,V> loHead = null, loTail = null; ? ? ? ? ? ? ? ? ? ?// 定义高位链表的头、尾节点，将链表进行拆分成更小的链表
? ? ? ? ? ? ? ? ? ? ? ? Node<K,V> hiHead = null, hiTail = null; ? ? ? ? ? ? ? ? ? ?// 定义低位链表的头、尾节点
? ? ? ? ? ? ? ? ? ? ? ? Node<K,V> next; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 链表的下一个节点
? ? ? ? ? ? ? ? ? ? ? ? do {
? ? ? ? ? ? ? ? ? ? ? ? ? ? next = e.next;
? ? ? ? ? ? ? ? ? ? ? ? ? ? if ((e.hash & oldCap) == 0) { ? ? ? ? ? ? ? ? ? ? ? ? ?// 对旧容量取模为0的则作为低位链表
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if (loTail == null)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loHead = e; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 循环第一个节点作为低位链表的头节点
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loTail.next = e; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 有了头节点就开始链接下一个节点
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? loTail = e; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 循环过的节点作为尾节点，用于链接下一个节点
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? ? ? else { ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 对旧容量取模不为0的则作为高位链表
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 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;
? ? }
?? ?
（四）红黑树rehash
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { ? ? ? ? // 对红黑树进行拆分，分为两个更小的链表或红黑树
? ? ? ? ? ? TreeNode<K,V> b = this;?? ??? ??? ??? ??? ??? ??? ??? ? ? ? ? ? ? ? ? ? ?// this代表红黑树的根节点
? ? ? ? ? ? // Relink into lo and hi lists, preserving order
? ? ? ? ? ? TreeNode<K,V> loHead = null, loTail = null; ? ? ? ? ? ? ? ? ? ? ? ? ? // 定义低位树的头、尾节点，其实此处仍然是高位链表，真正的转为红黑树在后面
? ? ? ? ? ? TreeNode<K,V> hiHead = null, hiTail = null; ? ? ? ? ? ? ? ? ? ? ? ? ? // 定义高位树的头、尾节点，其实此处仍然是高位链表，真正的转为红黑树在后面
? ? ? ? ? ? int lc = 0, hc = 0; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 高、低位链表的节点数量，根据数据进行红黑树转化
? ? ? ? ? ? for (TreeNode<K,V> e = b, next; e != null; e = next) { ? ? ? ? ? ? ? ?// 从根节点进行遍历，通过红黑树节点的next指针对节点顺序遍历，而不是对左右子树进行遍历
? ? ? ? ? ? ? ? next = (TreeNode<K,V>)e.next;
? ? ? ? ? ? ? ? e.next = null;
? ? ? ? ? ? ? ? if ((e.hash & bit) == 0) { ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 对旧容量bit取模为0的节点则作为低位链表
? ? ? ? ? ? ? ? ? ? if ((e.prev = loTail) == null)
? ? ? ? ? ? ? ? ? ? ? ? loHead = e;?? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ??? ? ?// 循环第一个节点作为低位链表的头节点
? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? ? ? loTail.next = e;?? ??? ??? ??? ??? ??? ??? ??? ??? ??? ? ?// 后续遍历到的节点以链表的结构串联
? ? ? ? ? ? ? ? ? ? loTail = e;
? ? ? ? ? ? ? ? ? ? ++lc;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else { ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 对旧容量bit取模不为0的节点则作为高位链表
? ? ? ? ? ? ? ? ? ? if ((e.prev = hiTail) == null) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? ? ? ? ? ? ? ? ? hiHead = e;
? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? ? ? hiTail.next = e;
? ? ? ? ? ? ? ? ? ? hiTail = e;
? ? ? ? ? ? ? ? ? ? ++hc;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? if (loHead != null) {
? ? ? ? ? ? ? ? if (lc <= UNTREEIFY_THRESHOLD) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 低位链表的节点数量<=6，不转为红黑树
? ? ? ? ? ? ? ? ? ? tab[index] = loHead.untreeify(map);?? ??? ??? ??? ??? ??? ??? ? ?// 将链表存到跟旧数组下标index 相同位置的新数组中
? ? ? ? ? ? ? ? else {
? ? ? ? ? ? ? ? ? ? tab[index] = loHead; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 如果节点数量>6，并且高、低位链表都存在，则先将链表存到跟旧数组下标index 相同位置的新数组中，然后将链表转为红黑树
? ? ? ? ? ? ? ? ? ? if (hiHead != null) // (else is already treeified)
? ? ? ? ? ? ? ? ? ? ? ? loHead.treeify(tab); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? if (hiHead != null) {
? ? ? ? ? ? ? ? if (hc <= UNTREEIFY_THRESHOLD) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 高位链表的节点数量<=6，不转为红黑树
? ? ? ? ? ? ? ? ? ? tab[index + bit] = hiHead.untreeify(map); ? ? ? ? ? ? ? ? ? ?// 将链表存到(旧数组下标index+旧容量)所在位置的新数组中
? ? ? ? ? ? ? ? else {
? ? ? ? ? ? ? ? ? ? tab[index + bit] = hiHead;
? ? ? ? ? ? ? ? ? ? if (loHead != null)
? ? ? ? ? ? ? ? ? ? ? ? hiHead.treeify(tab); ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 高位链表转为红黑树
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
|