HashSet 黑名单校验达 O(1) 关键在于合理初始化、均匀哈希分布及只读使用：预设容量避免扩容，用不可变类型或正确重写 hashCode/equals，必要时加盐扰动；只读场景线程安全，动态更新用 ConcurrentHashMap.newKeySet()。
HashSet 在 Java 中实现 O(1) 平均时间复杂度的黑名单校验，关键不在于“自己重写哈希表”，而在于正确利用其封装好的哈希映射机制——底层是 HashMap（JDK 8+），元素作为 key 存入，value 固定为 Presentation（即 PRESENT 对象）。只要哈希函数分布均匀、负载因子合理、无大量哈希冲突，contains() 就能接近常数时间完成判断。
用 HashSet 构建高性能黑名单集合
直接初始化一个容量充足、初始负载因子合理的 HashSet，避免频繁扩容和链表/红黑树转换带来的开销：
- 预估黑名单大小（如 100 万手机号），设置初始容量：`new HashSet(1_000_000 / 0.75 + 1)`（默认负载因子 0.75）
- 使用 `String` 或 `Long` 等天然不可变且哈希分布良好的类型作元素；若自定义对象（如黑名单实体），必须重写
hashCode()和equals()，且保证逻辑一致 - 批量加载时用
addAll()而非循环add()，减少内部结构调整次数
规避哈希冲突导致的性能退化
当大量元素哈希值相同（如全为 "0" 的字符串、或未重写 hashCode 的自定义类），HashSet 会退化为链表甚至红黑树遍历，contains() 可能变为 O(n) 或 O(log n)：
- 检查黑名单数据特征：若含大量前缀相同字符串（如 "138****1234"），考虑对原始值做简单扰动（如拼接盐值、取 MD5 前 8 位）再存入，提升散列均匀性
- 避免使用 `new String("xxx")` 重复构造对象，优先复用字符串常量池或使用
intern() - 可通过
HashSet.size()与底层HashMap的桶数量（反射获取）粗略估算冲突率，但生产环境更推荐用 JFR 或 Arthas 观察实际contains()耗时分布
内存与扩展性平衡策略
千万级黑名单下，纯内存 HashSet 可能占用数百 MB，需兼顾速度与资源：
立即学习“Java免费学习笔记（深入）”；
- 启用 JVM 压缩指针（
-XX:+UseCompressedOops）降低对象头开销 - 考虑分片：按哈希值高位分 4–8 个子集（如
hash & 0x3），校验时先定位子集再查，降低单个集合锁竞争（若多线程访问）并便于后续水平扩展 - 对超大规模场景（亿级），可结合布隆过滤器（Bloom Filter）做前置快速否定判断，HashSet 仅承载精确校验，两者组合兼顾内存与精度
线程安全下的高效校验
若黑名单只读（加载后不再变更），无需同步——HashSet 本身非线程安全，但**只读访问天然线程安全**：
- 确保所有元素在构建完成后不再修改（包括内部状态），可用
Collections.unmodifiableSet()包装增强语义 - 若需运行时动态增删黑名单，改用
ConcurrentHashMap.newKeySet()（JDK 8+），它提供近似 O(1) 的并发contains()，且无全局锁 - 避免在循环中反复调用
contains()前加锁——应将整个校验逻辑放入同步块，或改用无锁结构
不复杂但容易忽略：真正决定 O(1) 的不是 HashSet 名字，而是数据分布、初始化配置和使用方式。把黑名单当成纯粹的“存在性集合”来用，别试图从 HashSet 里取顺序、做范围查询或依赖迭代顺序——它只为 add/contains/remove 这三个操作而优化。
