共计 8318 个字符，预计需要花费 21 分钟才能阅读完成。
HashMap 简介
本篇文章是本人在学习 HashMap 的过程中本人的总结，并不一定完全正确，次要是记录本人的学习过程。
- HashMap 是一种映射关系，是 hash 值与理论存储对象之间的映射，也就是键值对的关系，通过关键字 key 找到理论存储的值 value，是一种数据结构
- 什么是 hash：实质上是把任意长度的输出，通过算法变换成固定长度的输入
-
在学习 Java 的过程中，最常见的两种数据结构是数组和链表，那么数组和链表各有什么优缺点？
- 数组：数组在物理空间中是间断的，数组对象间接指向数组首地址，在查找的时候效率高，然而因为空间是间断的，所以当物理空间的碎片比拟多时，当咱们想存入比拟大的数组的时候，即便可能空间足够，但因为这些空间不是间断的，就无奈存入
- 链表：链表在物理空间中不是间断的，在存放数据的同时还须要寄存下一个链节点的地址，相比于数组，不受空间是否是碎片化的影响，只有有空间，就能存储数据。然而查找效率没有数组高，插入和删除的效率比数组高
- HashMap：HashMap 将数组和链表联合起来，既可能进步查找效率，删除和插入的效率也进步了。
外部组成
- HashMap 的存储模式：键值对的存储模式
- 数据结构：数组 + 链表 + 红黑树
-
外部成员：
- 默认初始容量 DEFAULT_INITIAL_CAPACITY：16
- 默认负载因子 DEFAULT_LOAD_FACTOR：默认为 0.75，示意整体上 table 被占用水平
- TREEIFY_THRESHOLD：8，当数组中有某个索引地位上的链表长度大于该常量时，就将该链表转换成红黑树
- UNTREEIFY_THRESHOLD：6，当链表的长度小于该常量时，就将红黑树转换成链表
- 阈值 threshold：当数组中键值对个数大于阈值时进行扩大，计算形式是 hashmap 长度 * 负载因子
- Node<K,V>[] table：数组
构造方法
-
HashMap map = new HashMap();
- 无参的构造方法，只初始化了负载因子，默认为 0.75
-
HashMap map = new HashMap(int initialCapacity);
- 参数为 map 的初始容量，负载因子为默认值 0.75，底层实际上是调用了 HashMap(int initialCapacity, float loadFactor)
-
HashMap map = new HashMap(int initialCapacity, float loadFactor)
- 指定初始的容量以及负载因子
-
HashMap map = new HashMap(Map m);
- 初始化负载因子，默认为 0.75
- 调用 putMapEntries 办法，将汇合 m 全副都装进新的 map 汇合里
-
办法的执行步骤如下：
- 获取 m 的理论判读，判断是否大于 0，只有当大于 0 时才才执行
- 判断 map 的 table 数组是否为空，如果为空计算 map 的阈值
- 如果 table 数组不为空，判断 s 的理论长度是否大于 map 的阈值，如果大于对 map 汇合进行扩容
- 当 map 的长度确定下来之后，遍历 m 汇合，把键值对取出来存入 map 汇合当中
增删查办法源码解析
- hash 值计算过程：
| static final int hash(Object key) { | |
| int h; | |
| // 判断 key 的值是否为空 | |
| // 如果为空则返回 0 | |
| // 如果不为空则调用 key 的 hashCode 办法计算出 hash 值 | |
| // 并让 hash 值的高 16 位与低 16 位进行异或操作，得出最初的 hash 值 | |
| return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); | |
| } |
- put 办法
put 办法大抵的流程能够分为以下几点：
| * 1）计算 hash 值，依据 hash 值得出索引值，采纳的是以后 table 长度 -1 & hash 值相与得出索引值（hash 值是通过下面的 hash 办法计算得出，而不是调用 hashCode 办法）举个例子：存入两个 key 的 hash 值别离为 14 和 35，而以后 table 的长度为默认容量 16(2^n) | |
| 那么第一个 key 对应的索引值为：0000 1110 & 0000 1111，得出索引值为 14 | |
| 第二个 key 对应的索引值为：0010 0011 & 0000 1111，得出索引值为 3 | |
| 这样做能确保每个不管 hash 值有多大，都可能存入数组，截取的是 hash 值的二进制数的后 n 位 | |
| * 2）依据 hash 找到对应的索引值，有三种状况：* 以后地位为空，间接存入 | |
| * 以后地位不为空，且是链表，插入到链表的尾部 | |
| * 以后地位为空，且是红黑树，插入到红黑树当中 | |
| * 3）判断以后 table 的理论长度 size 是否超出阈值 threshold，如果超出则进行扩容 |
以下是对源码的解读：
| final V putVal(int hash, K key, V value, boolean onlyIfAbsent, | |
| boolean evict) {HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i; | |
| //2）判断 table 数组是否为空 || table 数组的长度是否 0，也就是是否是第一次寄存 | |
| if ((tab = table) == null || (n = tab.length) == 0) | |
| // 其中一个条件满足，给 table 扩容 | |
| n = (tab = resize()).length; | |
| //3）计算（数组长度 - 1 & hash 值），得出索引值，获取对应索引的值，判断是否为空 | |
| if ((p = tab[i = (n - 1) & hash]) == null) | |
| // 如果为空，在该索引地位创立一个新的节点，并放入 | |
| tab[i] = newNode(hash, key, value, null); | |
| //4）如果不为空，证实该索引地位曾经有值了 | |
| else { | |
| HashMap.Node<K,V> e; K k; | |
| // 判断是否是同一个 key | |
| if (p.hash == hash && | |
| ((k = p.key) == key || (key != null && key.equals(k)))) | |
| // 如果是同一个就赋给 e（赋给 e 是为了接下来是否要笼罩该地位的值做筹备）e = p; | |
| // 如果不是同一个 key，判断是否是树节点，如果是树节点，把节点插入到红黑树外面 | |
| else if (p instanceof HashMap.TreeNode) | |
| e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); | |
| // 如果既不是同一个 key，也不是树节点，那只可能是链表 | |
| else { | |
| // 循环链表，判断每个节点的 key 是否与要插入的 key 雷同，如果雷同则笼罩掉。//binCount 记录该链表的节点地位 | |
| for (int binCount = 0; ; ++binCount) { | |
| // 判断以后地位是否是尾结点 | |
| if ((e = p.next) == null) { | |
| // 如果是尾节点，则在为节点的下一个节点插入新的节点（尾插法）p.next = newNode(hash, key, value, null); | |
| // 判断以后链表的节点树是否大于 (TREEIFY_THRESHOLD - 1) | |
| if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st | |
| // 如果大于则将链表转换成红黑树 | |
| treeifyBin(tab, hash); | |
| // 跳出循环 | |
| break; | |
| } | |
| // 判断以后地位和咱们要存入的 key 是否雷同，如果雷同则跳出循环 | |
| if (e.hash == hash && | |
| ((k = e.key) == key || (key != null && key.equals(k)))) | |
| break; | |
| // 如果以上两个判断都不满足，持续遍历下一个节点 | |
| p = e; | |
| } | |
| } | |
| // 判断 e 是否为空 | |
| if (e != null) { // existing mapping for key | |
| // 不为空，取出 e 的 value 值 | |
| V oldValue = e.value; | |
| //onlyIfAbsent 如果为 false，则示意如果呈现的 key 雷同，则笼罩掉原来的值，反之就不笼罩 | |
| // 能够参考 HashMap 的另一个办法，putIfAbsent 的源码，外面的 onlyIfAbsent 就设为 true | |
| // 还有一种状况：原本寄存的 value 是 null, 那么不论 onlyIfAbsent 是 true 还是 false，肯定会被笼罩掉 | |
| if (!onlyIfAbsent || oldValue == null) | |
| // 笼罩掉本来的 value 值 | |
| e.value = value; | |
| afterNodeAccess(e); | |
| return oldValue; | |
| } | |
| } | |
| // 记录批改次数 | |
| ++modCount; | |
| // 判断存入之后的 size 是否大于阈值 | |
| if (++size > threshold) | |
| // 如果大于则扩容，扩容的办法能够往下翻 | |
| resize(); | |
| afterNodeInsertion(evict); | |
| return null; | |
| } |
- remove(key) 办法
remove 的办法流程大抵如下：
- 计算 hash 值，依据 hash 值计算出索引地位
- 找到要删除的索引地位的值
-
该值有如下三种状况
- 以后节点
- 链表上的几点
- 红黑树上的几点
-
依据找到的节点再做判断
- 如果是红黑树，那么将该节点从红黑树上删掉
- 如果是链表，进行断链操作
- 如果是以后节点，该索引地位指向以后节点的下一节点
具体源码如下：
| // 1）判断 key 是否为空，并计算出 hash 值 | |
| final HashMap.Node<K,V> removeNode(int hash, Object key, Object value, | |
| boolean matchValue, boolean movable) {HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, index; | |
| //1）判断外部的 table 数组是否为空 && table 数组长度是否大于 0 | |
| // && (以后 table 的长度 -1) 与 hash 值 相与，取出该索引地位的值，判断是否为空 | |
| if ((tab = table) != null && (n = tab.length) > 0 && | |
| (p = tab[index = (n - 1) & hash]) != null) { | |
| HashMap.Node<K,V> node = null, e; K k; V v; | |
| //2）如果以后索引地位的值 p 与要删除的 key 是雷同的话 | |
| // 把 p 赋给节点 node（赋给节点 node 是为了删除完之后还要返回被删除节点的值）if (p.hash == hash && | |
| ((k = p.key) == key || (key != null && key.equals(k)))) | |
| node = p; | |
| //3）如果不雷同，判断以后节点的下一个节点是否为空 | |
| // 如果不为空，可能要删除的点是链表中的某一个节点或者是树节点（红黑树）else if ((e = p.next) != null) { | |
| // 判断是否是树节点 | |
| if (p instanceof HashMap.TreeNode) | |
| // 如果是树节点，依据以后节点找到根节点，并依据根节点往下找直到找到要删除的节点 | |
| node = ((HashMap.TreeNode<K,V>)p).getTreeNode(hash, key); | |
| // 如果是链表，则遍历链表，直到找到要删除的节点 | |
| else { | |
| do { | |
| if (e.hash == hash && | |
| ((k = e.key) == key || | |
| (key != null && key.equals(k)))) { | |
| node = e; | |
| break; | |
| } | |
| p = e; | |
| } while ((e = e.next) != null); | |
| } | |
| } | |
| // 如果找到的节点 node 不等于空，判断该节点的构造 | |
| if (node != null && (!matchValue || (v = node.value) == value || | |
| (value != null && value.equals(v)))) { | |
| // 如果是树节点，则证实该链表曾经被转换成红黑树，删除树节点 | |
| if (node instanceof HashMap.TreeNode) | |
| ((HashMap.TreeNode<K,V>)node).removeTreeNode(this, tab, movable); | |
| // 如果该节点就是一个 node 对象，则把该节点的下一个节点赋给该节点对应的索引地位 | |
| //（因为如果要删除的节点等于以后节点，证实该索引地位上就一个值，// 则以后节点的下一个节点就肯定为 null，这样就相当于把以后节点对应的索引地位置空）else if (node == p) | |
| tab[index] = node.next; | |
| // 如果既不是树节点，也不是 node 对象，则要删除的节点是链表上的某一个节点，则把要删除的节点删掉（进行断链的操作）else | |
| p.next = node.next; | |
| // 批改次数加一 | |
| ++modCount; | |
| //table 的理论长度减一 | |
| --size; | |
| afterNodeRemoval(node); | |
| return node; | |
| } | |
| } | |
| return null; | |
| } |
- get(key) 办法
get 办法的大抵流程如下：
- 计算 hash 值，依据 hash 值计算出索引地位
-
判断该索引地位的值，有如下三种状况
- 是否是以后节点
- 是否是红黑树上的节点，如果是依据红黑树查找
- 是否是链表节点，如果是遍历链表
- 返回找到的节点
具体源码的正文如下：
| // 1）判断 key 是否为空，并计算出 hash 值 | |
| final HashMap.Node<K,V> getNode(int hash, Object key) {HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k; | |
| //1）判断外部的 table 数组是否为空 && table 数组长度是否大于 0 | |
| // && (以后 table 的长度 -1) 与 hash 值 相与，取出该索引地位的值 first，判断是否为空 | |
| if ((tab = table) != null && (n = tab.length) > 0 && | |
| (first = tab[(n - 1) & hash]) != null) { | |
| //2）判断找到的 first 与 key 是否雷同，如果雷同则间接返回 | |
| if (first.hash == hash && // always check first node | |
| ((k = first.key) == key || (key != null && key.equals(k)))) | |
| return first; | |
| // 如果步骤 2 的条件不满足，有一种状况是真的没有对应的值 | |
| // 还有一种状况可能是 hash 抵触造成的起因，也就是该 first 节点实际上是一个链表 | |
| // 可能所要取的值不在头节点上，这时候就要去遍历链表的每一个节点 | |
| // 判断 first 的下一个节点是否为空，如果为空证实要找的 key 没有对应的值，否则进行下一步 | |
| if ((e = first.next) != null) { | |
| // 判断 first 是不是 TreeNode 节点，也就是判断该链表是否被转化成红黑树 | |
| // 如果不是进行下一步，如果是查找红黑树节点 | |
| if (first instanceof HashMap.TreeNode) | |
| //getTreeNode 大抵的办法流程如下：// 将 first 节点转换成 TreeNode 节点，判断 first 节点的父节点是否为空 | |
| // 如果为空证实该节点是根节点，如果不为空依据以后节点往上始终找，直到找到根节点 | |
| // 依据根节点遍历每一个子节点直到找到绝对应的 key | |
| return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key); | |
| // 如果不是红黑树，循环遍历链表，对每一个节点进行判断 | |
| do { | |
| if (e.hash == hash && | |
| ((k = e.key) == key || (key != null && key.equals(k)))) | |
| return e; | |
| } while ((e = e.next) != null); | |
| } | |
| } | |
| return null; | |
| } |
扩容机制
为什么要扩容：缩小哈希抵触，进步性能
| final Node<K,V>[] resize() {Node<K,V>[] oldTab = table; | |
| int oldCap = (oldTab == null) ? 0 : oldTab.length;// 以后 map 的总长度 | |
| int oldThr = threshold;// 以后 map 的阈值 | |
| int newCap, newThr = 0; | |
| //1）判断以后容量是否大于 0 | |
| if (oldCap > 0) { | |
| // 判断以后容量是否超过最大容量，如果超过则不持续扩容 | |
| if (oldCap >= MAXIMUM_CAPACITY) { | |
| threshold = Integer.MAX_VALUE; | |
| return oldTab; | |
| } | |
| // 否则判断以后容量扩容一倍后是否小于最大容量 && 旧的容量的长度要大于默认容量 16 | |
| else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && | |
| oldCap >= DEFAULT_INITIAL_CAPACITY) | |
| // 满足这两个条件，将阈值扩容一倍 | |
| newThr = oldThr << 1; // double threshold | |
| } | |
| //2）如果以后容量不大于 0，则判断以后阈值是否大于 0 | |
| else if (oldThr > 0) // initial capacity was placed in threshold | |
| // 满足则新的容量等于以后阈值的值 | |
| newCap = oldThr; | |
| //3）如果 1 和 2 都不满足，证实这是一个新创建的 map | |
| else { // zero initial threshold signifies using defaults | |
| // 则新的容量等于默认容量 16，新的阈值等于默认的负载因子 *0.75 * 默认容量 16 | |
| newCap = DEFAULT_INITIAL_CAPACITY; | |
| newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); | |
| } | |
| // 4）判断新的阈值是否等于 0 | |
| if (newThr == 0) { | |
| // 满足的话，判断新的容量是否小于最大容量 | |
| // 满足的话判断新的容量 * 负载因子是否小于最大容量 | |
| // 如果小于，那么新的阈值等于新的容量 * 负载因子，如果不小于，则新的阈值等于最大容量 | |
| float ft = (float)newCap * loadFactor; | |
| newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? | |
| (int)ft : Integer.MAX_VALUE); | |
| } | |
| //5）创立新的 newTab 表，笼罩掉本来的 table | |
| threshold = newThr; | |
| @SuppressWarnings({"rawtypes","unchecked"}) | |
| Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; | |
| table = newTab; | |
| //6）如果旧的 table 表不等于空，遍历 oldTab | |
| if (oldTab != null) {for (int j = 0; j < oldCap; ++j) { | |
| HashMap.Node<K,V> e; | |
| // 如果以后地位上的值不等于空，则将这给地位取出来赋给 e，并把这个地位置空 | |
| if ((e = oldTab[j]) != null) {oldTab[j] = null; | |
| // 判断 e.next 是否等于空，如果等于空，从新计算索引地位并赋给 newTab | |
| if (e.next == null) | |
| newTab[e.hash & (newCap - 1)] = e; | |
| // 如果不等于空，判断是否为树节点，如果是拆分树节点并从新计算索引地位，赋给 newTab | |
| else if (e instanceof HashMap.TreeNode) | |
| ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); | |
| // 如果不是树节点，那么就是链表 | |
| 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; | |
| // 如果以后节点的 hash 值与 oldTab 的容量相与等于 0，把该节点放到 Lo 的链表上 | |
| if ((e.hash & oldCap) == 0) {if (loTail == null) | |
| loHead = e; | |
| else | |
| loTail.next = e; | |
| loTail = e; | |
| } | |
| // 如果不等于 0，把这个节点放到 Hi 的链表上 | |
| else {if (hiTail == null) | |
| hiHead = e; | |
| else | |
| hiTail.next = e; | |
| hiTail = e; | |
| } | |
| } while ((e = next) != null); | |
| // 循环完结后别离判断 Lo 和 Hi 是否为空，如果不为空则把 Lo 和 Hi 的头节点别离放入 newTab 表里 | |
| if (loTail != null) { | |
| loTail.next = null; | |
| newTab[j] = loHead; | |
| } | |
| if (hiTail != null) { | |
| hiTail.next = null; | |
| newTab[j + oldCap] = hiHead; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| //7）循环完结，扩容实现，返回新数组 | |
| return newTab; | |
| } |
正文完
