HashMap常见知识点（持续更新...）

文章目录

• • 前言
  • HashMap的底层数据结构
  • 解决Hash冲突的方法有哪些，HashMap用哪种
  • 为什么Hash冲突时，先用链表，再转为红黑树
  • HashMap默认加载因子为什么是0.75
  • HashMap中，key的存储索引计算方式
  • HashMap数组的长度为什么是2的幂次方
  • HashMap的put方法流程
  • 一般使用什么类型作为Key
  • HashMap为什么线程不安全
  • HashMap如何扩容
  • HashMap和Hashtable的区别
  • 待更新...
  • 结尾

前言

Java面试必备知识点，HashMap常见知识点。(Java interview essential knowledge points, common knowledge points of HashMap)

在学习Java编程的过程中，我整理了一些常见的 HashMap 基础面试题。这些题目帮助我回顾了学习过程中的关键知识点。

HashMap的底层数据结构

在 JDK1.8 中，HashMap 由数组+链表+红黑树组成的。
由于链表过长会影响 HashMap的性能，因此引进和红黑树，但红黑树转化也需要一定的条件。

• 当链表长度超过阈值（默认为8） ，并且数据总量超过 64 时会转化为红黑树。
• 如果当前数组的长度小于 64 ，则进行扩容，而不是先转化为红黑树，以减少搜索的时间。

结构大概的样子：

解决Hash冲突的方法有哪些，HashMap用哪种

解决hash冲突的方法主要有四种：链地址法（也称为拉链法）、再哈希法、建立公共溢出区和开放定址法。

1. 链地址法（拉链法）：
   • 在HashMap中，每个哈希表位置（桶）都包含一个链表头节点。当发生冲突时，新的键值对会添加到该链表的尾部。从 Java8 开始，当链表长度超过阈值（默认为8）时，链表会转换为红黑树。
2. 再哈希法：
   • 当哈希冲突发生时，使用另一个哈希函数计算地址，直到冲突不再发生。
3. 建立公共溢出区：
   • 一旦哈希表中的空闲位置不再存在，就在哈希表之外另辟一个存储区，专门用于存放产生冲突的元素。
4. 开放定址法：
   • 一旦发生哈希冲突，就寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将记录存入。
   • 开放定址法包括线性探测再散列、平方探测再散列、伪随机探测再散列等方法。

HashMap主要使用的是链地址法（拉链法），通过链表和红黑树来解决哈希冲突。

为什么Hash冲突时，先用链表，再转为红黑树

红黑树也有一些缺点。它的操作（如插入、删除、左旋、右旋）相对复杂，这会导致操作的开销比链表大。

当哈希桶（bucket）中的元素数量少于阈值（默认为8）时，HashMap链表的优势在于其插入和删除操作的时间复杂度为 O(1)，并且当元素数量较少时，遍历链表进行查找的效率也是可以接受的。

当链表长度超过阈值（默认为8）时，红黑树会提供时间复杂度（O(log n)）的查找、插入和删除操作，这可以提高查询性能。

HashMap默认加载因子为什么是0.75

选择 0.75 作为加载因子是基于对 HashMap 性能和空间利用率的权衡考虑。它具有一定的数学意义，以便 HashMap 在扩容时能够保持较好的哈希分布，降低哈希冲突的概率。

可以参考这篇文章# 转载和积累系列 - 为什么 HashMap 加载因子是0.75？而不是0.8，0.6？

HashMap中，key的存储索引计算方式

1. 计算key的哈希值：使用 hashCode() 方法计算 key 的哈希值。
2. 处理哈希值的高位冲突（JDK1.8）：为了增加哈希值的随机性并减少哈希冲突，它使用了一种“扰动函数”的方法，将哈希值的高16位与低16位进行异或操作（^）。
3. 计算索引（取模）：HashMap 使用处理过的哈希值与哈希表的长度减一进行位与操作（&），即 hash & (n-1)，得到的结果就是key在哈希表中的索引。 n 是哈希表的长度，通常是2的幂（如16、32）
   补充： 这样位与操作（&）就等同于对哈希值进行模运算，但通常比模运算更快。

HashMap数组的长度为什么是2的幂次方

均匀分布：当数组长度是2的幂次方时，(n - 1) 二进制表示中所有位都是1（如，当 n=16 时，(n - 1) = 15，其二进制表示为 1111）。当进行（hash & (n - 1)）操作时，哈希值的每个位都参与了确定索引的过程。以便均匀地分布哈希值到各个桶中，减少了哈希冲突。

HashMap的put方法流程

1. 初始化或扩容：
   • 如果当前哈希表为空，或当前哈希表的大小大于或等于阈值（capacity * loadFactor），则进行扩容操作。
2. 计算哈希值和索引：
   • 使用 hashCode() 方法计算 key 的哈希值。
   • 使用 (n - 1) & hash 计算哈希值的索引， n 是哈希表的长度。
3. 处理哈希冲突：
   • 如果发生了哈希冲突，则遍历该位置处的链表或红黑树。
   • 如果链表中存在相同哈希值和相等键（通过 equals(Object obj) 方法判断），则更新该元素的值（即替换旧值）。
   • 否则，将新元素添加到链表或红黑树的末尾。
   • 如果链表长度超过了树化阈值（默认为 8），并且哈希表的大小超过 64，则将链表转换为红黑树。
4. 插入新元素：
   • 如果没有哈希冲突，则创建一个新节点，并将新元素插入。
5. 更新元素数量：
   • 更新哈希表中元素的数量 size。
6. 返回旧值（如果存在）：
   • 如果在插入新元素之前，已经存在相同键的元素，则返回该元素的旧值；否则返回 null。

一般使用什么类型作为Key

HashMap 的 key 通常使用不可变对象，如 Integer、String、枚举类型（enum）或者自定义的实现了正确 hashCode() 和 equals() 方法的不可变类。

因为 String 是不可变的，所以在创建的时候 hashcode 就被缓存了，不需要重新计算。

HashMap为什么线程不安全

1. 无同步机制：HashMap 的内部没有使用任何同步机制（如 synchronized）来保证多线程环境下操作的原子性。
2. 扩容非原子：当 HashMap 的容量不足时，会进行扩容操作，这是一个非原子的过程。在扩容期间，如果其他线程尝试访问或修改 HashMap，可能会导致数据不一致或异常。
3. 哈希冲突解决：HashMap 使用链表或红黑树（JDK 1.8）来解决哈希冲突。在并发环境下，如果多个线程同时修改同一个哈希桶（bucket）中的元素，可能会导致链表或红黑树的结构被破坏。
4. 可见性问题：由于 Java 内存模型（JMM）的原因，在没有同步的情况下，一个线程对 HashMap 的修改可能对其他线程不可见。可能导致线程之间看到的数据状态不一致。

HashMap如何扩容

1. 检查是否需要扩容：检查当前 HashMap 的实际元素数量（size）是否超过了阈值 threshold = capacity * loadFactor 。
2. 确定新的容量：新容量通常是当前容量的两倍。
3. 创建新的哈希表：根据新容量，创建一个新的哈希表数组。
4. 重新哈希和迁移元素：遍历旧哈希表中的每个元素，重新计算其在新哈希表中的索引位置，并将其插入到新的哈希表中。这个过程被称为 ReHashing。对于每个元素，根据其 key 的哈希值和新哈希表的大小，通过 (n - 1) & hash（ n 是新哈希表的大小）计算它在新哈希表中的位置。
5. 更新引用：当所有的元素都被插入到新的哈希表中后，将原哈希表的引用更新为新的哈希表。原哈希表就被垃圾回收器回收了。

HashMap和Hashtable的区别

1. 线程是否安全：HashMap 非线程安全，而 HashTable 线程安全。HashTable 内部基本都使用了 synchronized 修饰（现在推荐使用 ConcurrentHashMap）。
2. 效率： 由于线程安全问题，HashMap 效率比 HashTable 高。HashTable 基本被淘汰了，不推荐使用。
3. 空值：HashMap 允许 null 作为键（key）和值（value），而 Hashtable 不允许。
4. 内部实现：在计算 hash 值时，HashMap 会重新计算，而 Hashtable 直接使用对象的hashCode。在扩容方式上，HashMap 默认容量为16（JKD1.8），扩容时容量会变为2n。Hashtable 默认容量为11，并且扩容时将容量变为原来的 2n+1。
5. 底层数据结构：HashMap 使用数组+链表+红黑树（JDK1.8），HashTable 则没有。

待更新…

结尾

如果您觉得今天的文章对您有帮助，我相信您一定会喜欢我的博客。
哈利の小屋 - Kang Yao Coding - 努力有时候战胜不了天分，但至少能让别人看得起你。
在那里，我会定期更新关于计算机类的文章，并与您分享更多实用的经验和知识。欢迎您来访问和留言交流。