默认容量在 Java 中如果你使用HashMap并且不指定容量它会使用默认的初始容量为 16负载因子load factor为 0.75。MapString,StringmapnewHashMap();等价于MapString,StringmapnewHashMap(16,0.75f);默认初始容量Initial Capacity16默认负载因子Load Factor0.75当HashMap中的元素数量超过容量 × 负载因子即 16 × 0.75 12时就会触发**扩容resize**操作容量会翻倍为 32。注意这只是HashMap的行为其他Map实现类如TreeMap,LinkedHashMap,ConcurrentHashMap的默认容量或行为可能不同。如果你在 Java 中使用HashMap并指定容量为 50例如MapString,StringmapnewHashMap(50);这表示你希望这个HashMap至少能容纳 50 个键值对而不发生扩容但这并不意味着底层数组大小就是 50。实际上Java 的HashMap底层会将你指定的容量向上调整为最近的 2 的幂次方作为实际的初始容量。你指定new HashMap(50)HashMap 会找到大于等于 50 的最小 2 的幂64所以底层实际容量是64默认负载因子仍然是0.75所以触发扩容的阈值为64 × 0.75 48也就是说当你放入第 49 个元素时就会触发扩容。扩容时容量变为原来的两倍。所以 64 → 128 → 256 依次扩展。如果你关心性能可以预估元素数量然后设置合理的初始容量以避免频繁扩容。ConcurrentModificationExceptionConcurrentModificationException 的发生条件HashMap的迭代器是快速失败fail-fast机制的。这意味着如果你在一个线程中对HashMap进行结构性修改例如添加或删除元素并且在同一时刻有另一个线程正在迭代HashMap那么在迭代过程中会抛出ConcurrentModificationException。但是HashMap的迭代器并不是线程安全的所以如果你在一个线程中修改HashMap比如在迭代过程中它会触发ConcurrentModificationException无论是在哪个线程修改的。这是因为HashMap内部通过一个字段modCount来跟踪修改次数当迭代器的modCount与HashMap的modCount不匹配时就会抛出ConcurrentModificationException。总结ConcurrentModificationException是发生在“结构修改”时而不是由于“并发修改”本身。并发修改与结构修改结构修改向HashMap中添加、删除或清空元素等操作会改变它的内部结构可能会影响迭代器的行为。并发修改当多个线程同时对同一个HashMap进行结构修改时会造成并发问题但并不意味着每次并发修改都会抛出ConcurrentModificationException。实际上ConcurrentModificationException仅在某个线程在迭代期间修改了集合的结构时才会抛出而并非并发修改时就一定会发生异常。如果你需要在并发环境下安全地修改HashMap你可以使用ConcurrentHashMap它专门设计为线程安全的并且可以在多个线程中同时进行修改而不会抛出ConcurrentModificationException。使用Collections.synchronizedMap包装HashMap也可以提供线程安全的访问但它并不会完全解决迭代时修改的问题因为迭代过程本身是没有被同步的所以仍然需要同步访问。synchronized(map){for(Map.EntryString,Stringentry:map.entrySet()){// 迭代逻辑}}这样可以确保迭代操作是线程安全的避免其他线程在迭代时修改Map的结构。扩容HashMap在 Java 中的扩容机制是其性能优化的关键部分。它通过动态调整数组大小来保持较低的哈希冲突和高性能查询。 一、扩容的触发条件HashMap会在满足以下条件时自动扩容当前元素数量当前容量 × 负载因子loadFactor默认初始容量16默认负载因子0.75默认扩容阈值16 × 0.75 12当元素数超过 12HashMap会扩容。 二、扩容时发生了什么当触发扩容时HashMap会做以下几件事1.容量翻倍newCapacityoldCapacity*2比如从 16 → 32 → 64…2.重新计算 hash 并重新分布元素Rehashing旧的桶数组NodeK,V[] table被替换为新的、更大的数组然后将原有元素重新分布到新的桶中。Java 8 开始做了一些优化在旧桶索引 i 的链表中元素要么仍然落在i位置要么落到i oldCapacity位置。无需重新计算 hash 值只需要判断原 hash 的某一位是否为 1 即可。这个优化大大提升了扩容时的效率。3.节点转化优化树化/链化如果单个桶中元素过多默认超过 8 个且当前容量大于 64链表会转成红黑树以提高查找效率。 三、示意图简化原数组容量16: 扩容后数组容量32: bucket[0] → A bucket[0] → A bucket[1] → B → C bucket[1] → null ... ... bucket[8] → X → Y bucket[8] → X bucket[24] → Y (i oldCapacity)⚠️ 四、注意事项扩容代价高涉及数组拷贝和元素再分配应尽量避免频繁扩容。建议估算初始容量在已知元素数量时手动指定容量可提高性能。intexpectedSize1000;MapString,StringmapnewHashMap((int)(expectedSize/0.75)1);树化条件 如果容量 ≤ 64即使单个桶中元素 8也不会立刻树化这是HashMap的设计优化策略之一只有当桶中链表长度 8 且 HashMap 的总容量 ≥ 64 时链表才会被转化为红黑树。 为什么要这么做节省内存红黑树比链表更复杂占用更多内存。对于小容量HashMap红黑树的开销可能得不偿失。性能平衡在容量较小时哈希冲突相对少链表查找的成本尚可接受。没有必要启用红黑树。避免过早优化如果HashMap最终不会增长太大就没必要引入红黑树结构。 官方源码Java 8在HashMap的putVal()方法中有如下判断if(binCountTREEIFY_THRESHOLD-1){// TREEIFY_THRESHOLD 默认为 8if(tab.lengthMIN_TREEIFY_CAPACITY)resize();// 容量小于 64触发扩容elsetreeifyBin(tab,hash);}TREEIFY_THRESHOLD 8MIN_TREEIFY_CAPACITY 64逻辑含义链表长度超过 8 时如果当前数组长度 64先扩容不树化如果数组长度 ≥ 64执行树化操作代码中判断的是binCount TREEIFY_THRESHOLD - 1也就是binCount 7但这是因为这个binCount是从 0 开始计数的并且判断发生在添加新元素之前所以实际树化是在第 9 个元素插入时发生的。 那么问题来了为什么不直接判断binCount 8呢因为binCount是在循环过程中统计已存在的节点数即当前桶已有元素的数量。此时新元素还没有加入桶。换句话说当桶中已有 7 个节点你要插入第 8 个节点时binCount 7加上这次插入的新节点总数达到 8刚好满足树化条件所以条件写成binCount TREEIFY_THRESHOLD - 1是正确的 所以我们常说“链表长度超过8 时会树化”意思是第 9 个元素插入后才树化但实际上在插入第 8 个元素之前判断条件已经成立所以在第 8 个元素插入时就执行树化逻辑了。⚠️ 注意还要满足容量 ≥ 64 才真正树化否则会优先扩容。退化为链表树化后的桶在特定条件下是会退化回链表的这种退化机制也是HashMap的一种自我调整策略目的是节省资源、适应数据规模变化。✅会退化发生在删除元素之后当一个桶bucket中原本是红黑树的结构但由于大量元素被删除导致红黑树的节点数低于阈值就会自动退化为链表结构。 退化触发条件当红黑树中节点数UNTREEIFY_THRESHOLD默认为6也就是说当树中节点数少于 6HashMap会将这个红黑树退化为普通的链表。源码中的常量staticfinalintUNTREEIFY_THRESHOLD6; 退化发生的位置退化逻辑通常在remove()或resize()等操作中被触发。例如if(binCountUNTREEIFY_THRESHOLD)tab[index]untreeify(bin);这会把该桶的红黑树节点转换成链表节点替换掉原来的树结构。 为什么要退化红黑树有结构维护的开销如旋转、平衡等操作。如果节点很少链表比树更轻量、高效。保持结构简洁、减少不必要的资源占用。退化为链表后不会保留原来红黑树时的父子红黑树引用关系所有节点会被重新组织为普通链表节点结构。 具体来说当HashMap中的某个桶是红黑树Java 8其节点类型是staticfinalclassTreeNodeK,VextendsLinkedHashMap.EntryK,V{TreeNodeK,Vparent;TreeNodeK,Vleft;TreeNodeK,Vright;booleanred;...}这些字段构成了红黑树结构。 退化时会发生什么当节点数降到低于UNTREEIFY_THRESHOLD6时会调用untreeify()方法将这些TreeNode转换为普通Node链表✅ 核心逻辑简化NodeK,Vuntreeify(HashMap.NodeK,Vb){NodeK,Vhdnull,tlnull;for(HashMap.NodeK,Vqb;q!null;qq.next){NodeK,VpnewNode(q.hash,q.key,q.value,null);if(tlnull)hdp;elsetl.nextp;tlp;}returnhd;} 可以看出它是将TreeNode逐个转换为普通的Node。丢弃了parent,left,right,red等红黑树结构信息。最终只保留链表所需的hash,key,value,next。 所以退化后是纯链表不保留红黑树结构节点按链表方式连接不再有树形父子关系实现是为了节省内存、简化结构无需重新计算 hash 值只需要判断原 hash 的某一位是否为 1 即可这句话的意思是HashMap在扩容时为了决定元素应该放在新数组的哪个位置并不需要重新计算整个 hash 值只需要根据 hash 值的某些位通常是高位或低位来决定元素应该放在新数组中的哪个位置。在HashMap中元素的存储位置是由hash 值决定的。扩容时容量翻倍数组的大小发生了变化这意味着元素的位置可能会发生变化。在扩容时由于数组大小变了原来元素的位置可能会发生变化但它的 hash 值仍然是一样的。因此我们并不需要重新计算整个 hash 值即对原始 hash 值进行某种 hash 函数计算只需要通过原 hash 值的某些位信息来决定元素的新位置。通常HashMap会用hash (newCapacity - 1)来判断元素在新数组中的位置。这个操作可以通过检查 hash 值的某些位来确定它应该被放入的新位置。假设有一个容量为16的HashMap数组大小为 16然后扩容为32容量翻倍。原数组的大小是 16hash 值的低 4 位0000到1111决定了元素的位置。假设某个元素的 hash 值是123456789二进制表示。为了决定它在新数组中的位置我们只需要检查原 hash 值的低 4 位。当扩容为 32 时newCapacity - 1 31其二进制表示为11111这相当于原来数组大小的二进制长度被扩展影响元素放置的位置。通过检查原 hash 值的某些位例如hash (newCapacity - 1)HashMap可以确定元素的新位置。在扩容前元素的存储位置取决于hash (oldCapacity - 1)例如hash 15。扩容后新的容量是32所以会根据hash 31来重新定位元素。在这一过程中HashMap并没有重新计算 hash 值只是通过原 hash 值的某些位来确定新位置。 为什么HashMap的容量是 2 的次幂HashMap的数组长度总是 2 的次幂这背后有几个性能优化的原因主要与哈希函数和位运算的效率有关。位运算提高性能当HashMap使用 2 的次幂作为数组容量时计算元素存放位置时使用的掩码运算会非常高效。这是因为对于任何整数n使用n (size - 1)来计算其位置时size为 2 的次幂时size - 1的二进制表示仅包含连续的 1例如16 - 1 15对应二进制1111这种运算速度非常快。这种操作比求模运算%要快得多因为位运算是硬件支持的原子操作而求模运算则需要较为复杂的计算。避免哈希冲突哈希冲突的概率与数组的大小有关系。由于哈希值是通过哈希函数生成的而哈希函数的输出是一个整数它可能在某些情况下分布不均匀。如果HashMap的容量不是 2 的次幂哈希值的高位和低位可能会对存放位置产生较大的影响。通过使用 2 的次幂大小可以更有效地利用哈希值的低位这有助于避免不均匀的桶分布。例如对于一个容量为10的数组哈希值与10进行求模时可能会导致很多哈希冲突。而如果使用16它能更均匀地分布桶的索引位置。扩容优化HashMap的扩容机制是容量翻倍。而因为容量是 2 的次幂每次扩容时所有元素的位置只需要通过高效的位运算重新计算一次。扩容时新的容量为旧容量的两倍。例如16-32-64等等。由于数组容量是 2 的次幂扩容时只需要将哈希值的高几位改变剩下的位置低几位保持不变这大大减少了计算量。这种扩容机制使得在大多数情况下扩容时的性能开销比较低。‍位运算的好处举个例子假设哈希值是123456789数组大小是16即2^4我们需要计算元素放在哪个位置hash123456789size16indexhash(size-1);// 等价于 hash 15size - 1 15二进制为1111hash 15就是获取hash的低 4 位直接决定了元素的存放位置。位运算是非常快速的操作能够有效地计算索引位置。这种设计优化了HashMap的性能尤其是在元素数量较大时可以避免一些性能瓶颈。