本文目录 4 个章节
Java HashMap 的结构与复杂度
基本性质
java.util.HashMap 基于哈希表实现 Map 接口。它允许一个 null 键和多个 null 值，不保证遍历顺序，也不保证顺序长期不变。若多个线程并发修改，必须在外部同步或改用合适的并发容器。
在哈希分布合理时，get 与 put 的预期成本为常数时间。最坏情况取决于碰撞、容量以及具体 JDK 实现，不能无条件写成始终 O(1)。
warning · 实现细节 Java 8 及后续 OpenJDK 实现会在满足容量和碰撞阈值等条件时，把过长桶结构树化以改善严重碰撞下的性能；阈值和节点布局属于实现细节，不是使用
Map接口时应依赖的行为契约。
容量与负载因子
- capacity：桶数组容量。
- load factor：触发扩容的装载比例，默认值通常在时间与空间之间折中。
- rehash/resize：扩容会重新组织桶，成本较高。
能预估元素数量时，可设置足够的初始容量以减少扩容，但过大的容量会浪费空间，并使遍历成本增加，因为遍历与容量和元素数都有关。
正确使用自定义键
作为键的对象必须保持 equals 与 hashCode 契约一致：相等对象必须有相同哈希值。键参与比较的字段在放入映射后不应改变，否则对象可能仍在表中却无法按新状态查到。