HashSet扩容优化

这行初始化 HashSet 容量的代码：

new HashSet<>(Math.max((int)(list.size()/.75f) + 1, 16))

这是在优化 HashSet 的初始容量，让我们逐部分分析：

1. 为什么要设置初始容量？
   • HashSet 默认初始容量是 16
   • 如果元素数量超过容量 * 负载因子，就会触发扩容
   • 扩容操作会重新分配内存并重新哈希所有元素，性能开销大
   • 提前设置合适的容量可以避免不必要的扩容
2. 公式解析：list.size()/.75f
   • 0.75f 是 HashSet 的默认负载因子(load factor)
   • 当元素数量超过容量 * 0.75 时会触发扩容
   • 所以用预期元素数量除以 0.75 可以得到所需的最小容量
3. 完整公式说明：

// 示例解析
int expectedSize = 100;  // 假设list.size()为100
float loadFactor = 0.75f;  // 负载因子
​
// 计算过程
int minCapacity = (int)(expectedSize / loadFactor) + 1;  // ≈ 134
int finalCapacity = Math.max(minCapacity, 16);  // 取134和16中的较大值
​
// 最终创建HashSet
new HashSet<>(finalCapacity);

4. 为什么要 +1？
   • 为了处理除法的向上取整
   • 确保有足够空间容纳所有元素
5. 为什么要 Math.max(..., 16)？
   • 16 是 HashSet 的默认初始容量
   • 当预期元素很少时，没必要设置太小的容量
   • 保证容量至少为 16

使用场景示例：

// 不优化的版本
Set<String> set1 = new HashSet<>();  // 默认容量16，可能多次扩容
​
// 优化的版本
Set<String> set2 = new HashSet<>(Math.max((int)(expectedSize/.75f) + 1, 16));
// 直接使用合适的容量，避免扩容
​
// 如果确切知道大小，也可以直接使用
Set<String> set3 = new HashSet<>(expectedSize);  // HashSet内部会自动计算合适的容量

性能对比：

// 性能测试示例
long start = System.nanoTime();
Set<String> setWithoutSizing = new HashSet<>();
for (int i = 0; i < 1000000; i++) {
    setWithoutSizing.add("item" + i);
}
// 会发生多次扩容
​
long start2 = System.nanoTime();
Set<String> setWithSizing = new HashSet<>(Math.max((int)(1000000/.75f) + 1, 16));
for (int i = 0; i < 1000000; i++) {
    setWithSizing.add("item" + i);
}
// 避免扩容，性能更好

这种优化在处理大量数据时特别有用，可以显著提高性能。但对于小数据量（比如少于16个元素），这种优化的效果可能并不明显。