LinkedHashSet与HashSet迭代性能差异是否与存储对象类型有关？

底层结构差异基础 #

首先明确两种集合的迭代逻辑核心区别：

• HashSet底层基于HashMap实现，迭代时需要遍历完整的哈希表数组，跳过所有未存储元素的空槽，再逐个遍历槽内的链表/红黑树节点
• LinkedHashSet底层基于LinkedHashMap实现，在哈希表之外额外维护了一条贯穿所有元素的双向链表，迭代时直接遍历该双向链表即可，无需处理空槽

Integer元素场景LinkedHashSet更快的原因 #

Integer属于小内存对象，单个对象加上对象头总占用仅几十字节，此时缓存局部性的优势完全体现：
LinkedHashSet的双向链表节点内存排布相对紧凑，遍历时连续访问节点的缓存命中率极高，且完全规避了HashSet需要遍历大量空槽的开销，最终性能是HashSet的3倍左右，和你的测试结果吻合。

String元素场景HashSet更快的原因 #

你的测试用String是长度达数百字符的大对象，直接抵消了LinkedHashSet的遍历优势：

1. LinkedHashMap的Entry节点比HashMap的Entry多了before、after两个指针，单个节点内存占用更大，相同缓存行能存储的节点数量更少，缓存命中率下降
2. 大String对象的内存排布非常分散，遍历双向链表时每次访问下一个节点都需要跳转至不同的内存地址，缓存miss率飙升
3. HashSet遍历的哈希表数组是连续内存块，空槽判断仅需读取连续地址的内存，哪怕存在空槽开销，也远低于LinkedHashSet遍历分散内存的缓存miss开销，最终性能反超。

内容的提问来源于stack exchange，提问作者ddoel