哈希与hashmap原理知识点总结（java）

1. 哈希的基本思想哈希是一种通过“关键字”快速定位数据位置的思想。基本流程key → hash 函数 → hash 值 → 数组下标 → 找到元素在 Java 的HashMap中并不是直接把key放进数组而是先计算key的hashCode()再经过扰动函数处理最后通过数组长度计算桶下标。int index (n - 1) hash;其中n是哈希表数组长度hash是经过扰动后的哈希值(n - 1) hash用位运算代替取模运算前提是数组长度必须是 2 的幂。2. 常见哈希函数常见哈希函数有2.1 直接定址法H(k) k H(k) a * k b适合关键字范围比较连续、数据分布比较均匀的情况。优点是简单缺点是如果关键字范围太大会浪费大量空间。2.2 除留余数法H(k) k % p其中p通常选择小于等于表长的质数这样可以尽量减少哈希冲突。不过 JavaHashMap没有直接用%而是让数组长度保持为 2 的幂然后使用(n - 1) hash这样定位桶下标更快。3. 哈希冲突哈希冲突指的是不同的 key 经过哈希函数计算后落到了同一个数组下标位置。例如key1 → hash → index 3 key2 → hash → index 3这两个 key 就发生了哈希冲突。哈希冲突无法完全避免因为 key 的数量可能远远大于数组长度。影响哈希冲突概率的因素主要有哈希函数设计是否合理数组容量是否足够负载因子大小key 的hashCode()实现是否均匀解决冲突的方式是否合适。4. 解决哈希冲突的常见方式4.1 开放定址法发生冲突后继续在数组中寻找下一个可用位置。常见方式线性探测冲突后依次向后找 平方探测冲突后按照平方步长跳跃查找 双重哈希使用第二个哈希函数决定探测步长开放定址法的特点是数据都存在数组中不额外使用链表。缺点是容易产生聚集问题删除元素也比较麻烦。4.2 拉链法发生冲突后把冲突的元素挂在同一个桶位后面形成链表或树。JavaHashMap使用的就是拉链法。JDK 8 之后HashMap底层结构是数组 链表 红黑树5. HashMap 的底层结构HashMap是 Java 中常用的键值对集合底层基于哈希表实现。JDK 8 之后HashMap的核心结构是数组是主干 链表解决普通哈希冲突 红黑树解决极端哈希冲突一个桶位中的结构可能是table[i] → Node → Node → Node当链表过长时可能转为红黑树table[i] → TreeNode6. HashMap 的重要参数6.1 默认初始容量HashMap默认初始容量是 16。注意new HashMap()时底层数组并不会立刻创建而是在第一次put时才真正初始化。6.2 默认负载因子默认负载因子是 0.75。负载因子表示哈希表允许被填满到什么程度后触发扩容。默认情况下capacity 16 loadFactor 0.75 threshold 12所以当第 13 个元素插入时会触发扩容。Java 官方文档也说明默认负载因子0.75是时间成本和空间成本之间比较好的折中负载因子越高空间开销越小但查找成本可能越高。7. 为什么负载因子默认是 0.75负载因子太小优点冲突少查询快 缺点空间利用率低扩容频繁负载因子太大优点空间利用率高 缺点冲突增多链表变长查询变慢所以0.75是一种折中选择既保证较好的查询效率 又避免过多空间浪费负载因子 0.75 是时间和空间之间的折中。太小会导致空间浪费和频繁扩容太大会导致哈希冲突增多查询效率下降。8. HashMap 为什么数组长度必须是 2 的幂HashMap的数组长度始终保持为 2 的幂例如16, 32, 64, 128 ...主要原因有两个。8.1 可以用位运算快速定位下标普通哈希表可能使用index hash % length;但是取模运算相对较慢。如果数组长度是 2 的幂就可以使用index (length - 1) hash;效果等价于hash % length但位运算效率更高。8.2 扩容迁移更高效HashMap每次扩容都是扩大为原来的 2 倍。例如16 → 32 32 → 64 64 → 128扩容后元素的新位置只有两种可能原下标 原下标 oldCapacity判断依据是(hash oldCapacity) 0如果结果为 0位置不变否则移动到原下标 oldCapacity。这样扩容时不需要重新完整计算哈希下标只需要看 hash 值中新增参与计算的那一位。9. HashMap 的 hash 扰动函数JDK 8 中HashMap会对 key 的hashCode()进行一次扰动处理static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }含义是高 16 位和低 16 位进行异或这样做的原因是HashMap定位数组下标时使用的是(n - 1) hash当数组长度比较小时真正参与计算的主要是 hash 的低位。如果只使用低位而某些 key 的低位分布不好就容易发生冲突。所以 JDK 8 通过h ^ (h 16)把高位信息混合到低位中让哈希分布更加均匀。OpenJDK 源码中也能看到这个扰动函数的实现。10. HashMap 的 put 流程put(key, value)的大致流程如下1. 计算 key 的 hash 值 2. 根据 hash 值计算数组下标 3. 如果 table 为空先初始化数组 4. 如果目标桶为空直接插入新节点 5. 如果目标桶不为空说明发生哈希冲突 6. 判断桶中第一个节点是否和当前 key 相同 7. 如果 key 相同覆盖旧 value 8. 如果桶中是链表遍历链表 9. 如果找到相同 key覆盖 value 10. 如果没找到相同 key插入链表尾部 11. 如果链表长度达到树化条件尝试树化 12. 如果桶中是红黑树则按照红黑树方式插入或覆盖 13. 插入后 size 14. 如果 size 超过 threshold触发扩容11. HashMap 的 get 流程get(key)的大致流程如下1. 计算 key 的 hash 值 2. 根据 hash 值定位桶下标 3. 如果桶为空返回 null 4. 如果桶中第一个节点就是目标 key直接返回 value 5. 如果桶中是链表遍历链表查找 6. 如果桶中是红黑树按照树查找 7. 找到则返回 value找不到返回 null平均情况下HashMap的查询复杂度是O(1)极端情况下链表O(n) 红黑树O(log n)12. HashMap 如何判断 key 相等HashMap判断两个 key 是否相同不是只看hashCode()而是先比较 hash再比较 key。大致逻辑if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) { // key 相同 }也就是说判断 key 相同需要满足hash 值相同 并且 key 地址相同或者 equals 返回 true所以自定义对象作为 key 时必须正确重写hashCode() equals()否则可能出现明明逻辑上是同一个对象却 get 不到 value13. HashMap 为什么允许 key 为 nullHashMap允许一个nullkey。当 key 为null时hash 值固定为 0return (key null) ? 0 : ...所以nullkey 会被放到第 0 号桶中。注意HashMap 允许一个 null key多个 null value Hashtable 不允许 null key也不允许 null value ConcurrentHashMap 不允许 null key也不允许 null value14. HashMap 的扩容机制14.1 什么时候扩容当元素个数超过扩容阈值时会触发扩容。threshold capacity * loadFactor默认情况下capacity 16 loadFactor 0.75 threshold 12当插入第 13 个元素时会触发扩容。14.2 扩容做了什么扩容过程主要做两件事1. 创建一个原来 2 倍大小的新数组 2. 把旧数组中的元素迁移到新数组例如16 → 32 32 → 64 64 → 12814.3 JDK 8 扩容迁移优化JDK 8 中扩容迁移时不需要重新完整计算每个节点的新下标。只需要判断(hash oldCap) 0如果为 0新下标 原下标如果不为 0新下标 原下标 oldCap这样可以提高扩容迁移效率。15. 链表树化条件JDK 8 之后HashMap在哈希冲突严重时会把链表转为红黑树。树化条件不是只看链表长度而是同时满足两个条件链表长度 8 数组长度 64对应源码常量static final int TREEIFY_THRESHOLD 8; static final int MIN_TREEIFY_CAPACITY 64;如果链表长度达到 8但数组长度还小于 64优先选择扩容而不是树化。OpenJDK 源码中TREEIFY_THRESHOLD 8、UNTREEIFY_THRESHOLD 6、MIN_TREEIFY_CAPACITY 64这几个阈值都是明确写死的。16. 为什么数组长度小于 64 时不树化因为数组容量较小时链表过长通常说明数组太小而不是一定需要红黑树。这时更好的办法是先扩容减少哈希冲突如果过早树化会带来额外的内存开销和维护成本。所以 HashMap 的策略是容量小优先扩容 容量足够大但冲突仍然严重再树化17. 为什么链表长度达到 8 才树化源码注释中提到这个阈值和泊松分布有关。在默认负载因子 0.75、哈希分布比较均匀的情况下同一个桶中出现 8 个节点的概率非常低。也就是说正常情况下几乎不会树化 只有在哈希冲突非常严重时才树化这样设计的目的就是能用链表就先用链表 冲突严重时再用红黑树兜底因为链表节点结构简单占用内存少红黑树查询快但节点结构更复杂。18. 为什么链表长度小于等于 6 时退化回链表红黑树退化为链表的阈值是static final int UNTREEIFY_THRESHOLD 6;也就是说当树中节点数量变少时可能会退化为链表。为什么不是小于 8 就退化因为要避免频繁转换。如果树化阈值是 8退化阈值也是 8那么节点数量在 7、8 附近波动时就可能出现链表 → 红黑树 → 链表 → 红黑树反复转换会浪费性能。所以设计成树化阈值8 退化阈值6中间留出缓冲区避免结构频繁变化。19. 为什么使用红黑树而不是 AVL 树红黑树和 AVL 树都是自平衡二叉搜索树。AVL 树平衡要求更严格 查询性能略好 插入、删除时旋转调整更多 维护成本更高红黑树平衡要求相对宽松 查询、插入、删除性能都比较稳定 维护成本相对低HashMap中红黑树只是为了解决极端冲突不是为了追求最极致的查询性能。所以红黑树更适合这种场景查询效率足够好 插入删除维护成本也可接受 综合性能更均衡20. 为什么 HashMap 不直接全部使用红黑树因为大多数情况下哈希冲突并不严重。如果每个桶一开始都用红黑树会有几个问题1. 节点结构更复杂占用内存更多 2. 插入、删除需要维护树平衡成本更高 3. 节点数量少时链表遍历反而更简单所以 HashMap 的设计是少量冲突链表 严重冲突红黑树这是一种按需优化的设计。21. JDK 7 和 JDK 8 中 HashMap 的主要区别21.1 JDK 7JDK 7 中HashMap 底层主要是数组 链表发生哈希冲突后节点以链表形式存储。JDK 7 插入链表时使用的是头插法。在多线程并发扩容时头插法可能导致链表成环从而出现死循环问题。21.2 JDK 8JDK 8 之后HashMap 做了几个重要优化1. 引入红黑树降低极端冲突下的查询复杂度 2. 优化 hash 扰动函数让高位参与低位运算 3. 扩容迁移时使用高低位拆分不再重新完整计算下标 4. 链表插入方式从头插法改为尾插法但是需要注意JDK 8 的 HashMap 仍然不是线程安全的。尾插法降低了 JDK 7 中链表成环的典型风险但不能说明 HashMap 可以在多线程下安全使用。多线程环境下应该使用ConcurrentHashMap Collections.synchronizedMap()更推荐使用ConcurrentHashMap。22. HashMap 是线程安全的吗HashMap不是线程安全的。Java 官方文档明确说明如果多个线程同时访问一个HashMap并且至少有一个线程会修改结构就必须在外部进行同步。常见风险包括1. 数据覆盖 2. 数据丢失 3. 扩容过程异常 4. 遍历时抛出 ConcurrentModificationException 5. 读到不一致的数据所以面试中可以回答HashMap 本身不是线程安全的不能在多线程写场景下直接使用。如果需要并发环境下的 Map应该使用 ConcurrentHashMap。23. HashMap 的时间复杂度理想情况下哈希分布均匀putO(1) getO(1) removeO(1)发生严重哈希冲突并且桶中是链表putO(n) getO(n) removeO(n)JDK 8 之后如果链表转为红黑树putO(log n) getO(log n) removeO(log n)不过这是单个桶内的复杂度。总体上HashMap 的平均性能仍然接近 O(1)。24. HashMap 是否有序HashMap不保证遍历顺序。也就是说遍历结果不一定等于插入顺序。Java 官方文档也明确说明HashMap不保证 map 的顺序尤其不保证顺序会一直保持不变。如果需要顺序可以选择需要插入顺序LinkedHashMap 需要访问顺序LinkedHashMap 需要 key 排序TreeMap25. HashMap 和 HashSet 的区别25.1 HashMapHashMap存储的是键值对MapString, Integer map new HashMap(); map.put(Tom, 18);结构是key → value25.2 HashSetHashSet存储的是不重复元素SetString set new HashSet(); set.add(Tom);HashSet底层实际上是基于HashMap实现的。它把元素作为HashMap的 key把一个固定的 Object 对象作为 value。可以理解为map.put(element, PRESENT);所以HashSet 不允许重复元素 本质原因是 HashMap 的 key 不允许重复25.3 二者区别总结对比项HashMapHashSet存储内容key-value 键值对单个元素底层结构数组 链表 红黑树基于 HashMap是否允许重复key 不允许重复value 可以重复元素不允许重复是否有序不保证顺序不保证顺序是否允许 null允许一个 null key多个 null value允许一个 null 元素26. HashMap 和 Hashtable 的区别对比项HashMapHashtable线程安全不安全方法使用 synchronized线程安全性能单线程性能更好性能较差null key/value允许一个 null key多个 null value不允许 null key 和 null value出现时间JDK 1.2JDK 1.0比较老推荐使用常用一般不推荐面试回答Hashtable 是早期的线程安全 Map方法上加了 synchronized性能较差HashMap 不是线程安全的但单线程性能更好。现在并发场景一般使用 ConcurrentHashMap而不是 Hashtable。27. HashMap 和 ConcurrentHashMap 的区别对比项HashMapConcurrentHashMap线程安全不安全安全并发场景不适合适合null key/value允许 null key 和 null value不允许 null key 和 null value性能单线程性能好并发性能好使用场景单线程或局部变量多线程共享 Map为什么 ConcurrentHashMap 不允许 null因为在并发环境下如果get(key)返回null无法区分1. key 不存在 2. key 存在但 value 就是 null在并发情况下这种歧义会带来问题。所以ConcurrentHashMap直接禁止 null key 和 null value。28. HashMap 和 LinkedHashMap 的区别LinkedHashMap是HashMap的子类。它在 HashMap 原有结构基础上额外维护了一条双向链表用来记录节点顺序。所以它的底层可以理解为HashMap 哈希表结构 双向链表HashMap只负责快速存取不保证遍历顺序LinkedHashMap既能快速存取又能按照一定顺序遍历Java 官方文档说明LinkedHashMap通常维护插入顺序也可以使用访问顺序。28.1 LinkedHashMap 支持两种顺序第一种插入顺序。按照 put 的顺序遍历第二种访问顺序。每次 get 或 put 访问节点后把该节点移动到链表尾部访问顺序模式可以用来实现 LRU 缓存。29. 用 LinkedHashMap 实现 LRU 缓存LRU 的意思是Least Recently Used 最近最少使用思想是最近访问过的数据放到后面 最久没有访问的数据放到前面 容量满了就删除最前面的数据LinkedHashMap可以开启访问顺序模式new LinkedHashMap(initialCapacity, loadFactor, true);第三个参数true表示按照访问顺序排序。示例class LRUCacheK, V extends LinkedHashMapK, V { private final int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); this.capacity capacity; } Override protected boolean removeEldestEntry(Map.EntryK, V eldest) { return size() capacity; } }30. TreeMap 是什么用来干什么TreeMap底层基于红黑树实现。它和HashMap最大的区别是HashMap 按 hash 存储不保证顺序 TreeMap 按 key 排序TreeMap的 key 必须能够比较大小。可以通过两种方式实现排序1. key 实现 Comparable 接口 2. 构造 TreeMap 时传入 Comparator 比较器常见使用场景1. 需要按照 key 升序或降序遍历 2. 需要范围查询 3. 对接第三方接口时需要对参数名排序后签名 4. 实现有序字典结构例如第三方接口签名先把参数按照 key 字典序排序 再拼接字符串 最后进行 MD5、SHA 或 HMAC 加密这时可以使用TreeMap。31. HashMap、LinkedHashMap、TreeMap 怎么选场景推荐只需要快速存取不关心顺序HashMap需要保持插入顺序LinkedHashMap需要实现 LRU 缓存LinkedHashMap需要按照 key 排序TreeMap多线程高并发访问ConcurrentHashMap简单记忆HashMap查找快但无序 LinkedHashMap有插入顺序或访问顺序 TreeMap按 key 排序 ConcurrentHashMap线程安全32. 重点易错点总结32.1 HashMap 不是插入时立刻创建 16 长度数组new HashMap()时只是创建对象底层数组在第一次put时才初始化。32.2 链表长度达到 8 不一定立刻树化还需要数组长度至少达到 64。如果数组长度小于 64会优先扩容。32.3 HashMap 不保证顺序即使有时候看起来像有序也不能依赖这个顺序。需要顺序应该使用LinkedHashMap TreeMap32.4 JDK 8 改成尾插法不代表线程安全JDK 8 只是优化了扩容和插入逻辑但HashMap仍然不能在多线程写场景下直接使用。32.5 hashCode 相同不代表 key 相同hashCode()相同只是说明可能在同一个桶中还需要用equals()判断是否是真正相等。32.6 equals 相同的对象必须 hashCode 相同如果两个对象equals()返回 true那么它们的hashCode()必须相同。否则放进 HashMap 后可能无法正常查询。33. 一句话总结HashMap的核心思想是用数组实现快速定位用链表解决普通哈希冲突用红黑树优化极端冲突通过负载因子和扩容机制在时间效率与空间利用率之间取得平衡。