源码仓库Gitee · GitHubHashMap 作为最常用的 Map 类是基于哈希表实现的继承了 AbstractMap 并且实现了 Map 接口。哈希表将键的 Hash 值映射到内存地址即根据键获取对应的值并将其存储到内存地址。也就是说 HashMap 是根据键的 Hash 值来决定对应值的存储位置。通过这种索引HashMap 获取数据的速度会非常快。例如存储键值对xa时哈希值会通过哈希函数 f(x) 得到 a 的实现存储位置但也会有新的问题。如果再来一个 yb哈希函数 f(y) 的哈希值跟之前 f(x) 是一样的这样两个对象的存储地址就冲突了这种现象被称为哈希冲突。解决哈希冲突的方法有开放地址法、再哈希函数法、链地址法开放地址法当地址冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把 key 存放到冲突位置后面的空位置上去。但这种方法存在很多缺点比如查找、扩容等再哈希函数法产生地址冲突时再计算另一个哈希函数地址直到冲突不再发生这种方法不易产生”聚集”但却增加了计算时间。如果我们不考虑添加元素的时间成本且对查询元素的要求极高可以考虑这种算法HashMap 则综合了所有因素采用链地址法解决哈希冲突问题这种方法是采用了数组哈希表链表的数据结构当发生哈希冲突时就用一个链表结构存储相同 hash 值的数据。要点源码分析HashMap允许键值对为nullHashTable则不允许会报空指针异常HashMapString, String map new HashMap(2); map.put(null,null); map.put(1,null);HashMap是由一个 Node 数组组成的每个 Node 包含了一个 key-value 键值对transient NodeK,V[] table;Node 类作为 HashMap 中的一个内部类除了 key、value 两个属性外还定义了一个next 指针当有哈希冲突时HashMap 会用之前数组当中相同哈希值对应存储的 Node 对象通过指针指向新增的相同哈希值的 Node 对象的引用。static class NodeK,V implements Map.EntryK,V { final int hash; final K key; V value; NodeK,V next; Node(int hash, K key, V value, NodeK,V next) { this.hash hash; this.key key; this.value value; this.next next; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } .......... }HashMap 初始容量是16扩容方式为2N在 JDK1.7 中HashMap 整个扩容过程就是分别取出数组元素一般该元素是最后一个放入链表中的元素然后遍历以该元素为头的单向链表元素依据每个被遍历元素的 hash 值计算其在新数组中的下标然后进行交换。这样的扩容方式会将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部。而在 JDK1.8 后HashMap 对扩容操作做了优化。由于扩容数组的长度是2倍关系所以对于假设初始 tableSize4 要扩容到8来说就是 0100 到 1000 的变化左移一位就是2倍在扩容中只用判断原来的 hash 值和 oldCap旧数组容量按位与操作是 0 或 1 就行0的话索引不变1的话索引变成原索引加扩容前数组。之所以能通过这种“与”运算来重新分配索引是因为 hash 值本来是随机的而 hash 按位与上 oldCap 得到的 0 和 1 也是随机的所以扩容的过程就能把之前哈希冲突的元素再随机分布到不同的索引中去。static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16默认大小 //元素的位置要么是在原位置要么是在原位置再移动2次幂的位置 final NodeK,V[] resize() { NodeK,V[] 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; } //进行2倍扩容后的新数组容量小于最大容量和旧数组长度大于等于16 else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) newThr oldThr 1; // double threshold重新计算阀值为原来的2倍 } //初始化数组 else if (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);//重新计算阀值 } //有阀值定义了新数组的容量重新计算阀值 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}) NodeK,V[] newTab (NodeK,V[])new Node[newCap];//创建新数组 table newTab; if (oldTab ! null) {//如果旧数组有数据进行数据移动如果没有数据返回一个空数组 for (int j 0; j oldCap; j) {//对旧数组进行遍历 NodeK,V e; if ((e oldTab[j]) ! null) { oldTab[j] null;//将旧数组的所属位置的旧元素清空 if (e.next null)//当前节点是在数组上后面没有链表重新计算槽位 newTab[e.hash (newCap - 1)] e; else if (e instanceof TreeNode)//当前节点是红黑树红黑树重定位 ((TreeNodeK,V)e).split(this, newTab, j, oldCap); else { // preserve order当前节点是链表 NodeK,V loHead null, loTail null; NodeK,V hiHead null, hiTail null; NodeK,V 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;//移动到当前hash槽位 oldCap的位置即在原位置再移动2次幂的位置 } } } } } return newTab; }当前节点是数组后面没有链表重新计算槽位:位与操作的效率比效率高定位槽位e.hash (newCap - 1) 我们用长度16, 待插入节点的hash值为21举例: (1)取余: 21 % 16 5 (2)位与: 21: 0001 0101 15: 0000 1111 5: 0000 0101遍历链表对链表节点进行移位判断(e.hash oldCap) 0比如oldCap8,hash是3111927时 1JDK1.8中(e.hash oldCap)的结果是0808这样319组成新的链表index为3而1127组成新的链表新分配的index为38 2JDK1.7中是(e.hash newCap-1)newCap是oldCap的两倍也就是3111927对(16-1)与计算也是0808但由于是使用了单链表的头插入方式即同一位置上新元素总会被放在链表的头部位置这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话这样index为3的链表是193index为38的链表是 2711。 也就是说1.7中经过resize后数据的顺序变成了倒叙而1.8没有改变顺序。构造方法HashMap有两个重要的属性加载因子loadFactor和边界值threshold。loadFactor 属性是用来间接设置 Entry 数组哈希表的内存空间大小在初始 HashMap 不设置参数的情况下默认 loadFactor 为0.75。为什么是0.75这个值呢这是因为对于使用链表法的哈希表来说查找一个元素的平均时间是 O(1n)这里的 n 指的是遍历链表的长度因此加载因子越大对空间的利用就越充分这就意味着链表的长度越长查找效率也就越低。如果设置的加载因子太小那么哈希表的数据就过于稀疏对空间造成严重浪费。那有什么办法可以来解决因链表过长而导致的查询时间复杂度高的问题呢在JDK1.8后就使用了将链表转换为红黑树来解决这个问题。Entry 数组的 threshold 是通过初始容量和 loadFactor计算所得在初始 HashMap 不设置参数的情况下默认边界值为1216*0.75。如果我们在初始化时设置的初始化容量较小HashMap 中 Node 的数量超过边界值HashMap 就会调用 resize() 方法重新分配 table 数组。这将导致 HashMap 的数组复制迁移到另一块内存中去从而影响 HashMap 的效率。public HashMap() {//默认初始容量为16加载因子为0.75 this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(int initialCapacity) {//指定初始容量为initialCapacity this(initialCapacity, DEFAULT_LOAD_FACTOR); } static final int MAXIMUM_CAPACITY 1 30;//最大容量 //当size到达threshold这个阈值时会扩容下一次扩容的值根据capacity * load factor进行计算 int threshold; /**由于HashMap的capacity都是2的幂因此这个方法用于找到大于等于initialCapacity的最小的2的幂initialCapacity如果就是2的幂则返回的还是这个数 * 通过5次无符号移位运算以及或运算得到 * n第一次右移一位时相当于将最高位的1右移一位再和原来的n取或就将最高位和次高位都变成1也就是两个1 * 第二次右移两位时将最高的两个1向右移了两位取或后得到四个1 * 依次类推右移16位再取或就能得到32个1 * 最后通过加一进位得到2^n。 * 比如initialCapacity 10 那就返回16 initialCapacity 17那么就返回32 * 10的二进制是1010减1就是1001 * 第一次右移取或 1001 | 0100 1101 * 第二次右移取或 1101 | 0011 1111 * 第三次右移取或 1111 | 0000 1111 * 第四次第五次同理 * 最后得到 n 1111返回值是 n1 2 ^ 4 16 ; * 让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。这是为了防止cap已经是2的幂。如果cap已经是2的幂又没有执行这个减1操作则执行完后面的几条无符号右移操作之后返回的capacity将是这个cap的2倍。 * 例如十进制数值8二进制为1000如果不对它减1而直接操作将得到答案10000即16。显然不是结果。减1后二进制为111再进行操作则会得到原来的数值1000即8。 * 问题tableSizeFor()最后赋值给threshold但threshold是根据capacity * load factor进行计算的这是不是有问题 * 注意在构造方法中并没有对table这个成员变量进行初始化table的初始化被推迟到了put方法中在put方法中会对threshold重新计算。 * 问题既然put会重新计算threshold那么在构造初始化threshold的作用是什么 * 答在put时会对table进行初始化如果threshold大于0会把threshold当作数组的长度进行table的初始化否则创建的table的长度为16。 */ static final int tableSizeFor(int cap) { int n cap - 1; n | n 1; n | n 2; n | n 4; n | n 8; n | n 16; return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1; } 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 || Float.isNaN(loadFactor))//加载因子小于等于0或为NaN抛出异常 throw new IllegalArgumentException(Illegal load factor: loadFactor); this.loadFactor loadFactor; this.threshold tableSizeFor(initialCapacity);//边界值 }put/get/remove/containsKey/containsValue/putAll/clear/replace源码分析put当将一个 key-value 对添加到 HashMap 中首先会根据该 key 的 hashCode() 返回值再通过 hash() 方法计算出 hash 值再通过 putVal 方法中的 (n-1) hash 决定该 Node 的存储位置之所以要 设计为 (n-1)hash 这样的计算方式是因为 n 代表哈希表的长度哈希表习惯将长度设置为2的 n 次方这样可以恰好保证 (n-1)hash 计算得出的索引值总是位于 table 数组的索引之内。public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }hash计算key的hash值高16位不变低16位与高16位异或作为key的最终hash值。即取 int 类型的一半刚好可以将该二进制数对半切开利用异或运算如果两个数对应的位置相反则结果为1反之为0这样可以避免哈希冲突。简而言之就是尽量打乱 hashCode 真正参与运算的低16位。h 16表示无符号右移16位高位补0任何数跟0异或都是其本身因此key的hash值高16位不变。static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }之所以要无符号右移16位是跟table的下标有关上面的扩容中对数组槽位的重新计算方式是e.hash (newCap - 1)假如newCap16从下图可以看出table的下标仅与hash值的低n位有关hash值的高位都被与操作置为0了只有hash值的低4位参与了运算。putVal而当链表长度太长默认超过 8时链表就进行转换红黑树的操作。我们可以利用红黑树快速增删改查的特点提高 HashMap 的性能。当红黑树结点个数少于 6 个的时候又会将红黑树转化为链表。因为在数据量较小的情况下红黑树要维护平衡比起链表来性能上的优势并不明显。final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { NodeK,V[] tab; NodeK,V p; int n, i; //此时 table 尚未初始化通过 resize 方法得到初始化的table if ((tab table) null || (n tab.length) 0) n (tab resize()).length; // n-1)hash 计算 Node 的存储位置如果判断 Node 不在哈希表中(链表的第一个节点位置新增一个 Node并加入到哈希表中 if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null); else {//hash冲突了 NodeK,V e; K k; if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) e p;//判断key的条件是key的hash相同和eqauls方法符合p.key等于插入的key将p的引用赋给e else if (p instanceof TreeNode)// p是红黑树节点插入后仍然是红黑树节点所以直接强制转型p后调用putTreeVal返回的引用赋给e e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); else {//链表 // 循环直到链表中的某个节点为null或者某个节点hash值和给定的hash值一致且key也相同则停止循环。 for (int binCount 0; ; binCount) {//binCount是一个计数器来计算当前链表的元素个数 if ((e p.next) null) {//next为空将添加的元素置为next p.next newNode(hash, key, value, null); //插入成功后要判断是否需要转换为红黑树因为插入后链表长度1而binCount并不包含新节点所以判断时要将临界阀值-1.【链表长度达到了阀值TREEIFY_THRESHOLD8即链表长度达到了7】 if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st // 如果链表长度达到了8且数组长度小于64那么就重新散列resize(),其中如果有红黑树且节点小于等于6将树分割转换为链表如果大于64则创建红黑树将链表转换为红黑树 treeifyBin(tab, hash); //结束循环 break; } //节点hash值和给定的hash值一致且key也相同停止循环 if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) break; //如果给定的hash值不同或者key不同。将next值赋给p为下次循环做铺垫。即结束当前节点对下一节点进行判断 p e; } } //如果e不是null该元素存在了(也就是key相等) if (e ! null) { // existing mapping for key // 取出该元素的值 V oldValue e.value; // 如果 onlyIfAbsent 是 true就不用改变已有的值如果是false(默认)或者value是null将新的值替换老的值 if (!onlyIfAbsent || oldValue null) e.value value; //什么都不做 afterNodeAccess(e); //返回旧值 return oldValue; } } //修改计数器1为迭代服务 modCount; //达到了边界值需要扩容 if (size threshold) resize(); //什么都不做 afterNodeInsertion(evict); //返回null return null; }get当 HashMap 只存在数组而数组中没有 Node 链表时是 HashMap 查询数据性能最好的时候。一旦发生大量的哈希冲突就会产生 Node 链表这个时候每次查询元素都可能遍历 Node 链表从而降低查询数据的性能。特别是在链表长度过长的情况下性能明显下降红黑树的使用就很好地解决了这个问题使得查询的平均复杂度降低到了 O(log(n))链表越长使用红黑树替换后的查询效率提升就越明显。public V get(Object key) { NodeK,V e; return (e getNode(hash(key), key)) null ? null : e.value; } final NodeK,V getNode(int hash, Object key) { NodeK,V[] tab; NodeK,V first, e; int n; K k; //数组不为null数组长度大于0根据hash计算出来的槽位的元素不为null if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { //查找的元素在数组中返回该元素 if (first.hash hash // always check first node ((k first.key) key || (key ! null key.equals(k)))) return first; if ((e first.next) ! null) {//查找的元素在链表或红黑树中 if (first instanceof TreeNode)//元素在红黑树中返回该元素 return ((TreeNodeK,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); } } //找不到返回null return null; }removepublic V remove(Object key) { NodeK,V e; return (e removeNode(hash(key), key, null, false, true)) null ? null : e.value; } final NodeK,V removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { NodeK,V[] tab; NodeK,V p; int n, index; //数组不为null数组长度大于0要删除的元素计算的槽位有元素 if ((tab table) ! null (n tab.length) 0 (p tab[index (n - 1) hash]) ! null) { NodeK,V node null, e; K k; V v; //当前元素在数组中 if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) node p; //元素在红黑树或链表中 else if ((e p.next) ! null) { if (p instanceof TreeNode)//是树节点从树种查找节点 node ((TreeNodeK,V)p).getTreeNode(hash, key); else { do { //hash相同并且key相同找到节点并结束 if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) { node e; break; } p e; } while ((e e.next) ! null);//遍历链表 } } //找到节点了并且值也相同 if (node ! null (!matchValue || (v node.value) value || (value ! null value.equals(v)))) { if (node instanceof TreeNode)//是树节点从树中移除 ((TreeNodeK,V)node).removeTreeNode(this, tab, movable); else if (node p)//节点在数组中 tab[index] node.next;//当前槽位置为nullnode.next为null else//节点在链表中 p.next node.next;//将节点删除 modCount;//修改计数器1为迭代服务 --size;//数量-1 afterNodeRemoval(node);//什么都不做 return node;//返回删除的节点 } } return null; }containsKeypublic boolean containsKey(Object key) { return getNode(hash(key), key) ! null;//查看上面的get的getNode }containsValuepublic boolean containsValue(Object value) { NodeK,V[] tab; V v; //数组不为null并且长度大于0 if ((tab table) ! null size 0) { for (int i 0; i tab.length; i) {//对数组进行遍历 for (NodeK,V e tab[i]; e ! null; e e.next) { //当前节点的值等价查找的值返回true if ((v e.value) value || (value ! null value.equals(v))) return true; } } } return false;//找不到返回false }putAllpublic void putAll(Map? extends K, ? extends V m) { putMapEntries(m, true); } final void putMapEntries(Map? extends K, ? extends V m, boolean evict) { int s m.size();//获得插入整个m的元素数量 if (s 0) { if (table null) { // pre-size当前map还没有初始化数组 float ft ((float)s / loadFactor) 1.0F;//m的容量 //判断容量是否大于最大值MAXIMUM_CAPACITY int t ((ft (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); //容量达到了边界值比如插入的m的定义容量是16但当前map的边界值是12需要对当前map进行重新计算边界值 if (t threshold) threshold tableSizeFor(t);//重新计算边界值 } else if (s threshold)//存放的数量达到了边界值扩容 resize(); //对m进行遍历放到当前map中 for (Map.Entry? extends K, ? extends V e : m.entrySet()) { K key e.getKey(); V value e.getValue(); putVal(hash(key), key, value, false, evict); } } }clearpublic void clear() { NodeK,V[] tab; modCount;//修改计数器1为迭代服务 if ((tab table) ! null size 0) { size 0;//将数组的元素格式置为0然后遍历数组将每个槽位的元素置为null for (int i 0; i tab.length; i) tab[i] null; } }replacepublic boolean replace(K key, V oldValue, V newValue) { NodeK,V e; V v; //根据hash计算得到槽位的节点不为null并且节点的值等于旧值 if ((e getNode(hash(key), key)) ! null ((v e.value) oldValue || (v ! null v.equals(oldValue)))) { e.value newValue;//覆盖旧值 afterNodeAccess(e); return true; } return false; } public V replace(K key, V value) { NodeK,V e; //根据hash计算得到槽位的节点不为null if ((e getNode(hash(key), key)) ! null) { V oldValue e.value;//节点的旧值 e.value value;//覆盖旧值 afterNodeAccess(e); return oldValue;//返回旧值 } return null;//找不到key对应的节点 }总结HashMap 通过哈希表数据结构的形式存储键值对这种设计的好处就是查询键值对的效率高我们在编码中可以优化 HashMap的性能例如重写 key 的 hashCode 方法降低哈希冲突从而减少链表的产生高效利用哈希表达到提高性能的效果。我们在使用 HashMap 时可以结合自己的场景来设置初始容量和加载因子两个参数。当查询操作较为频繁时可以适当地减少加载因子如果对内存利用率要求比较高可以适当的增加加载因子我们可以在预知存储数据量的情况下提前设置初始容量初始容量预知数据量/加载因子这样做的好处是可以减少 resize() 操作提高 HashMap 的效率HashMap 使用了数组链表这两种数据结构相结合的方式实现了链地址法当有哈希值冲突时就可以将冲突的键值对链成一个链表。但这种方式存在一个性能问题如果链表过长查询数据的时间复杂度就会增加。所以 HashMap 在JDK1.8中使用了红黑树来解决链表过长导致的查询性能下降问题。问题分析HashMap遍历中修改出现ConcurrentModificationException并发修改异常解析Exception in thread main java.util.ConcurrentModificationException at java.util.HashMap$HashIterator.nextNode(HashMap.java:1442) at java.util.HashMap$KeyIterator.next(HashMap.java:1466)遍历的几种方式//1 for (String key : map.keySet()) { System.out.println(map.get(key)); map.remove(key); } //编译后 Iterator var2 map.keySet().iterator(); while(var2.hasNext()) { String key (String)var2.next(); System.out.println((String)map.get(key)); map.remove(key); } //2 for(Map.EntryString,String entry:map.entrySet()){ System.out.println(entry.getKey():entry.getValue()); map.remove(entry.getKey()); } //编译后 Iterator var2 map.entrySet().iterator(); while(var2.hasNext()) { Map.EntryString, String entry (Map.Entry)var2.next(); System.out.println((String)entry.getKey() : (String)entry.getValue()); map.remove(entry.getKey()); } //3 for(String values:map.values()){ System.out.println(values); map.remove(values); } //编译后 Iterator var2 map.values().iterator(); while(var2.hasNext()) { String values (String)var2.next(); System.out.println(values); map.remove(values); }解析从上面编译后的代码可以看到hasNext - next//1 final class KeySet extends AbstractSetK { public final IteratorK iterator() { return new KeyIterator(); } } final class KeyIterator extends HashIterator implements IteratorK { public final K next() { return nextNode().key; }//调用HashIterator的nextNode() } abstract class HashIterator { HashIterator() {//构造方法 expectedModCount modCount;//将当前的期望计数器值进行赋值 NodeK,V[] t table;//得到数组 current next null;//当前节点和下一个节点为null index 0;//当前节点的下标 //通过while循环,得到数组中的第一个不为空的元素下标以及值,并将此元素值赋给next if (t ! null size 0) { // advance to first entry do {} while (index t.length (next t[index]) null); } } public final boolean hasNext() { return next ! null; } //返回下一节点 final NodeK,V nextNode() { NodeK,V[] t; NodeK,V e next;//返回的节点 //问题在这里计数器跟期望的计数器不一致导致异常每次的remove和put都会重新对计数器进行1但期望的计数器在HashIterator初始化时就定义了后面的调用HashIterator的nextNode就没有重新对期望的计数器进行重置 if (modCount ! expectedModCount) throw new ConcurrentModificationException(); if (e null)//节点为null返回异常 throw new NoSuchElementException(); //当前节点遍历结束while遍历其他节点的将下一节点赋予next直到数组为空结束 if ((next (current e).next) null (t table) ! null) { do {} while (index t.length (next t[index]) null); } return e; } } //2 final class EntrySet extends AbstractSetMap.EntryK,V { public final IteratorMap.EntryK,V iterator() { return new EntryIterator(); } } final class EntryIterator extends HashIterator implements IteratorMap.EntryK,V { public final Map.EntryK,V next() { return nextNode(); }//调用HashIterator的nextNode() } //3 final class Values extends AbstractCollectionV { public final IteratorV iterator() { return new ValueIterator(); } } final class ValueIterator extends HashIterator implements IteratorV { public final V next() { return nextNode().value; }//调用HashIterator的nextNode() }解决方式从下面的代码可以看出将map.keySet转换为ArrayList后获取到的是ArrayList的迭代器这样迭代next和删除remove操作的是不同的对象(ArrayList和HashMap)没有并发修改异常上面的三种方式迭代和删除的对象都是HashMap导致出现问题。ArrayListString strings new ArrayList(map.keySet()); for(String key : strings){ System.out.println(map.get(key)); System.out.println(map.remove(key)); } //编译后 ArrayListString strings new ArrayList(map.keySet()); Iterator var3 strings.iterator(); while(var3.hasNext()) { String key (String)var3.next(); System.out.println((String)map.get(key)); System.out.println((String)map.remove(key)); }或可以使用ConcurrentHashMap解决并发修改异常使用ConcurrentHashMap后上面的三种方式都不会出现并发异常问题。ConcurrentHashMapString, String map new ConcurrentHashMap(2);ArrayList的遍历中修改同样出现ConcurrentModificationException并发修改异常解析使用Iterator迭代器(增强for循环也是使用Iterator)在next进行判断然后使用ArrayList的add()、remove()进行修改操作public IteratorE iterator() { return new Itr(); } private class Itr implements IteratorE { public E next() { checkForComodification(); int i cursor; if (i size) throw new NoSuchElementException(); Object[] elementData ArrayList.this.elementData; if (i elementData.length) throw new ConcurrentModificationException(); cursor i 1; return (E) elementData[lastRet i]; } final void checkForComodification() { //判断计数器和期望的计数器是否一致由于ArrayList的add()、remove()、trimToSize()都会对modCount1导致遍历时修改会抛出异常 if (modCount ! expectedModCount) throw new ConcurrentModificationException(); } }解决方式直接使用普通for同时遍历和修改for(int i0;ilist.size();i){ String str list.get(i); if(str.equals(str)){ list.remove(str); i i-1; } } public E get(int index) { rangeCheck(index);//检查索引范围 return elementData(index);//直接从数组中获取元素 } private void rangeCheck(int index) { if (index size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } E elementData(int index) { return (E) elementData[index]; }使用ListIterator列表迭代器进行遍历时添加使用ListIterator的add()(只有添加操作)替换ArrayList的add()//案例 ArrayList list new ArrayList(); list.add(1); ListIterator lit list.listIterator(); while (lit.hasNext()){ System.out.println(lit.next()); lit.add(2); } //解析 public ListIteratorE listIterator() { return new ListItr(0); } private class ListItr extends Itr implements ListIteratorE { public void add(E e) { checkForComodification(); try { int i cursor; ArrayList.this.add(i, e); cursor i 1; lastRet -1; //将期望的计数器更新为修改计数器值这样下次next判断就不会出现问题 expectedModCount modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } }使用Iterator迭代器进行遍历时删除使用Iterator的remove()(只有删除操作)替换ArrayList的remove()//案例 ArrayList list new ArrayList(); list.add(1); list.add(2); Iterator lit list.iterator(); while (lit.hasNext()){ Integer i (Integer)lit.next(); if(1i) { lit.remove(); } } System.out.println(list); //解析 public IteratorE iterator() { return new Itr(); } private class Itr implements IteratorE { public void remove() { if (lastRet 0) throw new IllegalStateException(); checkForComodification(); try { //删除当前遍历到的元素 ArrayList.this.remove(lastRet); cursor lastRet; lastRet -1; //将期望的计数器更新为修改计数器值这样下次next判断就不会出现问题 expectedModCount modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } } 
长河君 · 2026/10/21 20:07:18 · 阅读 1.2k HashMap源码和并发异常问题分析
源码仓库Gitee · GitHubHashMap 作为最常用的 Map 类是基于哈希表实现的继承了 AbstractMap 并且实现了 Map 接口。哈希表将键的 Hash 值映射到内存地址即根据键获取对应的值并将其存储到内存地址。也就是说 HashMap 是根据键的 Hash 值来决定对应值的存储位置。通过这种索引HashMap 获取数据的速度会非常快。例如存储键值对xa时哈希值会通过哈希函数 f(x) 得到 a 的实现存储位置但也会有新的问题。如果再来一个 yb哈希函数 f(y) 的哈希值跟之前 f(x) 是一样的这样两个对象的存储地址就冲突了这种现象被称为哈希冲突。解决哈希冲突的方法有开放地址法、再哈希函数法、链地址法开放地址法当地址冲突时如果哈希表未被装满说明在哈希表中必然还有空位置那么可以把 key 存放到冲突位置后面的空位置上去。但这种方法存在很多缺点比如查找、扩容等再哈希函数法产生地址冲突时再计算另一个哈希函数地址直到冲突不再发生这种方法不易产生”聚集”但却增加了计算时间。如果我们不考虑添加元素的时间成本且对查询元素的要求极高可以考虑这种算法HashMap 则综合了所有因素采用链地址法解决哈希冲突问题这种方法是采用了数组哈希表链表的数据结构当发生哈希冲突时就用一个链表结构存储相同 hash 值的数据。要点源码分析HashMap允许键值对为nullHashTable则不允许会报空指针异常HashMapString, String map new HashMap(2); map.put(null,null); map.put(1,null);HashMap是由一个 Node 数组组成的每个 Node 包含了一个 key-value 键值对transient NodeK,V[] table;Node 类作为 HashMap 中的一个内部类除了 key、value 两个属性外还定义了一个next 指针当有哈希冲突时HashMap 会用之前数组当中相同哈希值对应存储的 Node 对象通过指针指向新增的相同哈希值的 Node 对象的引用。static class NodeK,V implements Map.EntryK,V { final int hash; final K key; V value; NodeK,V next; Node(int hash, K key, V value, NodeK,V next) { this.hash hash; this.key key; this.value value; this.next next; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } .......... }HashMap 初始容量是16扩容方式为2N在 JDK1.7 中HashMap 整个扩容过程就是分别取出数组元素一般该元素是最后一个放入链表中的元素然后遍历以该元素为头的单向链表元素依据每个被遍历元素的 hash 值计算其在新数组中的下标然后进行交换。这样的扩容方式会将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部。而在 JDK1.8 后HashMap 对扩容操作做了优化。由于扩容数组的长度是2倍关系所以对于假设初始 tableSize4 要扩容到8来说就是 0100 到 1000 的变化左移一位就是2倍在扩容中只用判断原来的 hash 值和 oldCap旧数组容量按位与操作是 0 或 1 就行0的话索引不变1的话索引变成原索引加扩容前数组。之所以能通过这种“与”运算来重新分配索引是因为 hash 值本来是随机的而 hash 按位与上 oldCap 得到的 0 和 1 也是随机的所以扩容的过程就能把之前哈希冲突的元素再随机分布到不同的索引中去。static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16默认大小 //元素的位置要么是在原位置要么是在原位置再移动2次幂的位置 final NodeK,V[] resize() { NodeK,V[] 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; } //进行2倍扩容后的新数组容量小于最大容量和旧数组长度大于等于16 else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) newThr oldThr 1; // double threshold重新计算阀值为原来的2倍 } //初始化数组 else if (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);//重新计算阀值 } //有阀值定义了新数组的容量重新计算阀值 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}) NodeK,V[] newTab (NodeK,V[])new Node[newCap];//创建新数组 table newTab; if (oldTab ! null) {//如果旧数组有数据进行数据移动如果没有数据返回一个空数组 for (int j 0; j oldCap; j) {//对旧数组进行遍历 NodeK,V e; if ((e oldTab[j]) ! null) { oldTab[j] null;//将旧数组的所属位置的旧元素清空 if (e.next null)//当前节点是在数组上后面没有链表重新计算槽位 newTab[e.hash (newCap - 1)] e; else if (e instanceof TreeNode)//当前节点是红黑树红黑树重定位 ((TreeNodeK,V)e).split(this, newTab, j, oldCap); else { // preserve order当前节点是链表 NodeK,V loHead null, loTail null; NodeK,V hiHead null, hiTail null; NodeK,V 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;//移动到当前hash槽位 oldCap的位置即在原位置再移动2次幂的位置 } } } } } return newTab; }当前节点是数组后面没有链表重新计算槽位:位与操作的效率比效率高定位槽位e.hash (newCap - 1) 我们用长度16, 待插入节点的hash值为21举例: (1)取余: 21 % 16 5 (2)位与: 21: 0001 0101 15: 0000 1111 5: 0000 0101遍历链表对链表节点进行移位判断(e.hash oldCap) 0比如oldCap8,hash是3111927时 1JDK1.8中(e.hash oldCap)的结果是0808这样319组成新的链表index为3而1127组成新的链表新分配的index为38 2JDK1.7中是(e.hash newCap-1)newCap是oldCap的两倍也就是3111927对(16-1)与计算也是0808但由于是使用了单链表的头插入方式即同一位置上新元素总会被放在链表的头部位置这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话这样index为3的链表是193index为38的链表是 2711。 也就是说1.7中经过resize后数据的顺序变成了倒叙而1.8没有改变顺序。构造方法HashMap有两个重要的属性加载因子loadFactor和边界值threshold。loadFactor 属性是用来间接设置 Entry 数组哈希表的内存空间大小在初始 HashMap 不设置参数的情况下默认 loadFactor 为0.75。为什么是0.75这个值呢这是因为对于使用链表法的哈希表来说查找一个元素的平均时间是 O(1n)这里的 n 指的是遍历链表的长度因此加载因子越大对空间的利用就越充分这就意味着链表的长度越长查找效率也就越低。如果设置的加载因子太小那么哈希表的数据就过于稀疏对空间造成严重浪费。那有什么办法可以来解决因链表过长而导致的查询时间复杂度高的问题呢在JDK1.8后就使用了将链表转换为红黑树来解决这个问题。Entry 数组的 threshold 是通过初始容量和 loadFactor计算所得在初始 HashMap 不设置参数的情况下默认边界值为1216*0.75。如果我们在初始化时设置的初始化容量较小HashMap 中 Node 的数量超过边界值HashMap 就会调用 resize() 方法重新分配 table 数组。这将导致 HashMap 的数组复制迁移到另一块内存中去从而影响 HashMap 的效率。public HashMap() {//默认初始容量为16加载因子为0.75 this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(int initialCapacity) {//指定初始容量为initialCapacity this(initialCapacity, DEFAULT_LOAD_FACTOR); } static final int MAXIMUM_CAPACITY 1 30;//最大容量 //当size到达threshold这个阈值时会扩容下一次扩容的值根据capacity * load factor进行计算 int threshold; /**由于HashMap的capacity都是2的幂因此这个方法用于找到大于等于initialCapacity的最小的2的幂initialCapacity如果就是2的幂则返回的还是这个数 * 通过5次无符号移位运算以及或运算得到 * n第一次右移一位时相当于将最高位的1右移一位再和原来的n取或就将最高位和次高位都变成1也就是两个1 * 第二次右移两位时将最高的两个1向右移了两位取或后得到四个1 * 依次类推右移16位再取或就能得到32个1 * 最后通过加一进位得到2^n。 * 比如initialCapacity 10 那就返回16 initialCapacity 17那么就返回32 * 10的二进制是1010减1就是1001 * 第一次右移取或 1001 | 0100 1101 * 第二次右移取或 1101 | 0011 1111 * 第三次右移取或 1111 | 0000 1111 * 第四次第五次同理 * 最后得到 n 1111返回值是 n1 2 ^ 4 16 ; * 让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。这是为了防止cap已经是2的幂。如果cap已经是2的幂又没有执行这个减1操作则执行完后面的几条无符号右移操作之后返回的capacity将是这个cap的2倍。 * 例如十进制数值8二进制为1000如果不对它减1而直接操作将得到答案10000即16。显然不是结果。减1后二进制为111再进行操作则会得到原来的数值1000即8。 * 问题tableSizeFor()最后赋值给threshold但threshold是根据capacity * load factor进行计算的这是不是有问题 * 注意在构造方法中并没有对table这个成员变量进行初始化table的初始化被推迟到了put方法中在put方法中会对threshold重新计算。 * 问题既然put会重新计算threshold那么在构造初始化threshold的作用是什么 * 答在put时会对table进行初始化如果threshold大于0会把threshold当作数组的长度进行table的初始化否则创建的table的长度为16。 */ static final int tableSizeFor(int cap) { int n cap - 1; n | n 1; n | n 2; n | n 4; n | n 8; n | n 16; return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1; } 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 || Float.isNaN(loadFactor))//加载因子小于等于0或为NaN抛出异常 throw new IllegalArgumentException(Illegal load factor: loadFactor); this.loadFactor loadFactor; this.threshold tableSizeFor(initialCapacity);//边界值 }put/get/remove/containsKey/containsValue/putAll/clear/replace源码分析put当将一个 key-value 对添加到 HashMap 中首先会根据该 key 的 hashCode() 返回值再通过 hash() 方法计算出 hash 值再通过 putVal 方法中的 (n-1) hash 决定该 Node 的存储位置之所以要 设计为 (n-1)hash 这样的计算方式是因为 n 代表哈希表的长度哈希表习惯将长度设置为2的 n 次方这样可以恰好保证 (n-1)hash 计算得出的索引值总是位于 table 数组的索引之内。public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }hash计算key的hash值高16位不变低16位与高16位异或作为key的最终hash值。即取 int 类型的一半刚好可以将该二进制数对半切开利用异或运算如果两个数对应的位置相反则结果为1反之为0这样可以避免哈希冲突。简而言之就是尽量打乱 hashCode 真正参与运算的低16位。h 16表示无符号右移16位高位补0任何数跟0异或都是其本身因此key的hash值高16位不变。static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }之所以要无符号右移16位是跟table的下标有关上面的扩容中对数组槽位的重新计算方式是e.hash (newCap - 1)假如newCap16从下图可以看出table的下标仅与hash值的低n位有关hash值的高位都被与操作置为0了只有hash值的低4位参与了运算。putVal而当链表长度太长默认超过 8时链表就进行转换红黑树的操作。我们可以利用红黑树快速增删改查的特点提高 HashMap 的性能。当红黑树结点个数少于 6 个的时候又会将红黑树转化为链表。因为在数据量较小的情况下红黑树要维护平衡比起链表来性能上的优势并不明显。final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { NodeK,V[] tab; NodeK,V p; int n, i; //此时 table 尚未初始化通过 resize 方法得到初始化的table if ((tab table) null || (n tab.length) 0) n (tab resize()).length; // n-1)hash 计算 Node 的存储位置如果判断 Node 不在哈希表中(链表的第一个节点位置新增一个 Node并加入到哈希表中 if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null); else {//hash冲突了 NodeK,V e; K k; if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) e p;//判断key的条件是key的hash相同和eqauls方法符合p.key等于插入的key将p的引用赋给e else if (p instanceof TreeNode)// p是红黑树节点插入后仍然是红黑树节点所以直接强制转型p后调用putTreeVal返回的引用赋给e e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); else {//链表 // 循环直到链表中的某个节点为null或者某个节点hash值和给定的hash值一致且key也相同则停止循环。 for (int binCount 0; ; binCount) {//binCount是一个计数器来计算当前链表的元素个数 if ((e p.next) null) {//next为空将添加的元素置为next p.next newNode(hash, key, value, null); //插入成功后要判断是否需要转换为红黑树因为插入后链表长度1而binCount并不包含新节点所以判断时要将临界阀值-1.【链表长度达到了阀值TREEIFY_THRESHOLD8即链表长度达到了7】 if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st // 如果链表长度达到了8且数组长度小于64那么就重新散列resize(),其中如果有红黑树且节点小于等于6将树分割转换为链表如果大于64则创建红黑树将链表转换为红黑树 treeifyBin(tab, hash); //结束循环 break; } //节点hash值和给定的hash值一致且key也相同停止循环 if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) break; //如果给定的hash值不同或者key不同。将next值赋给p为下次循环做铺垫。即结束当前节点对下一节点进行判断 p e; } } //如果e不是null该元素存在了(也就是key相等) if (e ! null) { // existing mapping for key // 取出该元素的值 V oldValue e.value; // 如果 onlyIfAbsent 是 true就不用改变已有的值如果是false(默认)或者value是null将新的值替换老的值 if (!onlyIfAbsent || oldValue null) e.value value; //什么都不做 afterNodeAccess(e); //返回旧值 return oldValue; } } //修改计数器1为迭代服务 modCount; //达到了边界值需要扩容 if (size threshold) resize(); //什么都不做 afterNodeInsertion(evict); //返回null return null; }get当 HashMap 只存在数组而数组中没有 Node 链表时是 HashMap 查询数据性能最好的时候。一旦发生大量的哈希冲突就会产生 Node 链表这个时候每次查询元素都可能遍历 Node 链表从而降低查询数据的性能。特别是在链表长度过长的情况下性能明显下降红黑树的使用就很好地解决了这个问题使得查询的平均复杂度降低到了 O(log(n))链表越长使用红黑树替换后的查询效率提升就越明显。public V get(Object key) { NodeK,V e; return (e getNode(hash(key), key)) null ? null : e.value; } final NodeK,V getNode(int hash, Object key) { NodeK,V[] tab; NodeK,V first, e; int n; K k; //数组不为null数组长度大于0根据hash计算出来的槽位的元素不为null if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { //查找的元素在数组中返回该元素 if (first.hash hash // always check first node ((k first.key) key || (key ! null key.equals(k)))) return first; if ((e first.next) ! null) {//查找的元素在链表或红黑树中 if (first instanceof TreeNode)//元素在红黑树中返回该元素 return ((TreeNodeK,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); } } //找不到返回null return null; }removepublic V remove(Object key) { NodeK,V e; return (e removeNode(hash(key), key, null, false, true)) null ? null : e.value; } final NodeK,V removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { NodeK,V[] tab; NodeK,V p; int n, index; //数组不为null数组长度大于0要删除的元素计算的槽位有元素 if ((tab table) ! null (n tab.length) 0 (p tab[index (n - 1) hash]) ! null) { NodeK,V node null, e; K k; V v; //当前元素在数组中 if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) node p; //元素在红黑树或链表中 else if ((e p.next) ! null) { if (p instanceof TreeNode)//是树节点从树种查找节点 node ((TreeNodeK,V)p).getTreeNode(hash, key); else { do { //hash相同并且key相同找到节点并结束 if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) { node e; break; } p e; } while ((e e.next) ! null);//遍历链表 } } //找到节点了并且值也相同 if (node ! null (!matchValue || (v node.value) value || (value ! null value.equals(v)))) { if (node instanceof TreeNode)//是树节点从树中移除 ((TreeNodeK,V)node).removeTreeNode(this, tab, movable); else if (node p)//节点在数组中 tab[index] node.next;//当前槽位置为nullnode.next为null else//节点在链表中 p.next node.next;//将节点删除 modCount;//修改计数器1为迭代服务 --size;//数量-1 afterNodeRemoval(node);//什么都不做 return node;//返回删除的节点 } } return null; }containsKeypublic boolean containsKey(Object key) { return getNode(hash(key), key) ! null;//查看上面的get的getNode }containsValuepublic boolean containsValue(Object value) { NodeK,V[] tab; V v; //数组不为null并且长度大于0 if ((tab table) ! null size 0) { for (int i 0; i tab.length; i) {//对数组进行遍历 for (NodeK,V e tab[i]; e ! null; e e.next) { //当前节点的值等价查找的值返回true if ((v e.value) value || (value ! null value.equals(v))) return true; } } } return false;//找不到返回false }putAllpublic void putAll(Map? extends K, ? extends V m) { putMapEntries(m, true); } final void putMapEntries(Map? extends K, ? extends V m, boolean evict) { int s m.size();//获得插入整个m的元素数量 if (s 0) { if (table null) { // pre-size当前map还没有初始化数组 float ft ((float)s / loadFactor) 1.0F;//m的容量 //判断容量是否大于最大值MAXIMUM_CAPACITY int t ((ft (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); //容量达到了边界值比如插入的m的定义容量是16但当前map的边界值是12需要对当前map进行重新计算边界值 if (t threshold) threshold tableSizeFor(t);//重新计算边界值 } else if (s threshold)//存放的数量达到了边界值扩容 resize(); //对m进行遍历放到当前map中 for (Map.Entry? extends K, ? extends V e : m.entrySet()) { K key e.getKey(); V value e.getValue(); putVal(hash(key), key, value, false, evict); } } }clearpublic void clear() { NodeK,V[] tab; modCount;//修改计数器1为迭代服务 if ((tab table) ! null size 0) { size 0;//将数组的元素格式置为0然后遍历数组将每个槽位的元素置为null for (int i 0; i tab.length; i) tab[i] null; } }replacepublic boolean replace(K key, V oldValue, V newValue) { NodeK,V e; V v; //根据hash计算得到槽位的节点不为null并且节点的值等于旧值 if ((e getNode(hash(key), key)) ! null ((v e.value) oldValue || (v ! null v.equals(oldValue)))) { e.value newValue;//覆盖旧值 afterNodeAccess(e); return true; } return false; } public V replace(K key, V value) { NodeK,V e; //根据hash计算得到槽位的节点不为null if ((e getNode(hash(key), key)) ! null) { V oldValue e.value;//节点的旧值 e.value value;//覆盖旧值 afterNodeAccess(e); return oldValue;//返回旧值 } return null;//找不到key对应的节点 }总结HashMap 通过哈希表数据结构的形式存储键值对这种设计的好处就是查询键值对的效率高我们在编码中可以优化 HashMap的性能例如重写 key 的 hashCode 方法降低哈希冲突从而减少链表的产生高效利用哈希表达到提高性能的效果。我们在使用 HashMap 时可以结合自己的场景来设置初始容量和加载因子两个参数。当查询操作较为频繁时可以适当地减少加载因子如果对内存利用率要求比较高可以适当的增加加载因子我们可以在预知存储数据量的情况下提前设置初始容量初始容量预知数据量/加载因子这样做的好处是可以减少 resize() 操作提高 HashMap 的效率HashMap 使用了数组链表这两种数据结构相结合的方式实现了链地址法当有哈希值冲突时就可以将冲突的键值对链成一个链表。但这种方式存在一个性能问题如果链表过长查询数据的时间复杂度就会增加。所以 HashMap 在JDK1.8中使用了红黑树来解决链表过长导致的查询性能下降问题。问题分析HashMap遍历中修改出现ConcurrentModificationException并发修改异常解析Exception in thread main java.util.ConcurrentModificationException at java.util.HashMap$HashIterator.nextNode(HashMap.java:1442) at java.util.HashMap$KeyIterator.next(HashMap.java:1466)遍历的几种方式//1 for (String key : map.keySet()) { System.out.println(map.get(key)); map.remove(key); } //编译后 Iterator var2 map.keySet().iterator(); while(var2.hasNext()) { String key (String)var2.next(); System.out.println((String)map.get(key)); map.remove(key); } //2 for(Map.EntryString,String entry:map.entrySet()){ System.out.println(entry.getKey():entry.getValue()); map.remove(entry.getKey()); } //编译后 Iterator var2 map.entrySet().iterator(); while(var2.hasNext()) { Map.EntryString, String entry (Map.Entry)var2.next(); System.out.println((String)entry.getKey() : (String)entry.getValue()); map.remove(entry.getKey()); } //3 for(String values:map.values()){ System.out.println(values); map.remove(values); } //编译后 Iterator var2 map.values().iterator(); while(var2.hasNext()) { String values (String)var2.next(); System.out.println(values); map.remove(values); }解析从上面编译后的代码可以看到hasNext - next//1 final class KeySet extends AbstractSetK { public final IteratorK iterator() { return new KeyIterator(); } } final class KeyIterator extends HashIterator implements IteratorK { public final K next() { return nextNode().key; }//调用HashIterator的nextNode() } abstract class HashIterator { HashIterator() {//构造方法 expectedModCount modCount;//将当前的期望计数器值进行赋值 NodeK,V[] t table;//得到数组 current next null;//当前节点和下一个节点为null index 0;//当前节点的下标 //通过while循环,得到数组中的第一个不为空的元素下标以及值,并将此元素值赋给next if (t ! null size 0) { // advance to first entry do {} while (index t.length (next t[index]) null); } } public final boolean hasNext() { return next ! null; } //返回下一节点 final NodeK,V nextNode() { NodeK,V[] t; NodeK,V e next;//返回的节点 //问题在这里计数器跟期望的计数器不一致导致异常每次的remove和put都会重新对计数器进行1但期望的计数器在HashIterator初始化时就定义了后面的调用HashIterator的nextNode就没有重新对期望的计数器进行重置 if (modCount ! expectedModCount) throw new ConcurrentModificationException(); if (e null)//节点为null返回异常 throw new NoSuchElementException(); //当前节点遍历结束while遍历其他节点的将下一节点赋予next直到数组为空结束 if ((next (current e).next) null (t table) ! null) { do {} while (index t.length (next t[index]) null); } return e; } } //2 final class EntrySet extends AbstractSetMap.EntryK,V { public final IteratorMap.EntryK,V iterator() { return new EntryIterator(); } } final class EntryIterator extends HashIterator implements IteratorMap.EntryK,V { public final Map.EntryK,V next() { return nextNode(); }//调用HashIterator的nextNode() } //3 final class Values extends AbstractCollectionV { public final IteratorV iterator() { return new ValueIterator(); } } final class ValueIterator extends HashIterator implements IteratorV { public final V next() { return nextNode().value; }//调用HashIterator的nextNode() }解决方式从下面的代码可以看出将map.keySet转换为ArrayList后获取到的是ArrayList的迭代器这样迭代next和删除remove操作的是不同的对象(ArrayList和HashMap)没有并发修改异常上面的三种方式迭代和删除的对象都是HashMap导致出现问题。ArrayListString strings new ArrayList(map.keySet()); for(String key : strings){ System.out.println(map.get(key)); System.out.println(map.remove(key)); } //编译后 ArrayListString strings new ArrayList(map.keySet()); Iterator var3 strings.iterator(); while(var3.hasNext()) { String key (String)var3.next(); System.out.println((String)map.get(key)); System.out.println((String)map.remove(key)); }或可以使用ConcurrentHashMap解决并发修改异常使用ConcurrentHashMap后上面的三种方式都不会出现并发异常问题。ConcurrentHashMapString, String map new ConcurrentHashMap(2);ArrayList的遍历中修改同样出现ConcurrentModificationException并发修改异常解析使用Iterator迭代器(增强for循环也是使用Iterator)在next进行判断然后使用ArrayList的add()、remove()进行修改操作public IteratorE iterator() { return new Itr(); } private class Itr implements IteratorE { public E next() { checkForComodification(); int i cursor; if (i size) throw new NoSuchElementException(); Object[] elementData ArrayList.this.elementData; if (i elementData.length) throw new ConcurrentModificationException(); cursor i 1; return (E) elementData[lastRet i]; } final void checkForComodification() { //判断计数器和期望的计数器是否一致由于ArrayList的add()、remove()、trimToSize()都会对modCount1导致遍历时修改会抛出异常 if (modCount ! expectedModCount) throw new ConcurrentModificationException(); } }解决方式直接使用普通for同时遍历和修改for(int i0;ilist.size();i){ String str list.get(i); if(str.equals(str)){ list.remove(str); i i-1; } } public E get(int index) { rangeCheck(index);//检查索引范围 return elementData(index);//直接从数组中获取元素 } private void rangeCheck(int index) { if (index size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } E elementData(int index) { return (E) elementData[index]; }使用ListIterator列表迭代器进行遍历时添加使用ListIterator的add()(只有添加操作)替换ArrayList的add()//案例 ArrayList list new ArrayList(); list.add(1); ListIterator lit list.listIterator(); while (lit.hasNext()){ System.out.println(lit.next()); lit.add(2); } //解析 public ListIteratorE listIterator() { return new ListItr(0); } private class ListItr extends Itr implements ListIteratorE { public void add(E e) { checkForComodification(); try { int i cursor; ArrayList.this.add(i, e); cursor i 1; lastRet -1; //将期望的计数器更新为修改计数器值这样下次next判断就不会出现问题 expectedModCount modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } }使用Iterator迭代器进行遍历时删除使用Iterator的remove()(只有删除操作)替换ArrayList的remove()//案例 ArrayList list new ArrayList(); list.add(1); list.add(2); Iterator lit list.iterator(); while (lit.hasNext()){ Integer i (Integer)lit.next(); if(1i) { lit.remove(); } } System.out.println(list); //解析 public IteratorE iterator() { return new Itr(); } private class Itr implements IteratorE { public void remove() { if (lastRet 0) throw new IllegalStateException(); checkForComodification(); try { //删除当前遍历到的元素 ArrayList.this.remove(lastRet); cursor lastRet; lastRet -1; //将期望的计数器更新为修改计数器值这样下次next判断就不会出现问题 expectedModCount modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } }