Java面试必备知识点,HashMap常见知识点(Java interview essential knowledge points, common knowledge points of HashMap)。
HashMap的底层数据结构
在 JDK1.8 中,HashMap 由数组+链表+红黑树组成的。
由于链表过长会影响 HashMap的性能,因此引进和红黑树,但红黑树转化也需要一定的条件。
- 当链表长度超过阈值(默认为8) ,并且数据总量超过 64 时会转化为红黑树。
- 如果当前数组的长度小于 64 ,则进行扩容,而不是先转化为红黑树,以减少搜索的时间。
结构大概的样子:
解决Hash冲突的方法有哪些,HashMap用哪种
解决hash冲突的方法主要有四种:链地址法(也称为拉链法)、再哈希法、建立公共溢出区和开放定址法。
- 链地址法(拉链法):
- 在HashMap中,每个哈希表位置(桶)都包含一个链表头节点。当发生冲突时,新的键值对会添加到该链表的尾部。从 Java8 开始,当链表长度超过阈值(默认为8)时,链表会转换为红黑树。
- 再哈希法:
- 当哈希冲突发生时,使用另一个哈希函数计算地址,直到冲突不再发生。
- 建立公共溢出区:
- 一旦哈希表中的空闲位置不再存在,就在哈希表之外另辟一个存储区,专门用于存放产生冲突的元素。
- 开放定址法:
- 一旦发生哈希冲突,就寻找下一个空的哈希地址,只要哈希表足够大,空的哈希地址总能找到,并将记录存入。
- 开放定址法包括线性探测再散列、平方探测再散列、伪随机探测再散列等方法。
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的存储索引计算方式
- 计算key的哈希值:使用 hashCode() 方法计算 key 的哈希值。
- 处理哈希值的高位冲突(JDK1.8):为了增加哈希值的随机性并减少哈希冲突,它使用了一种“扰动函数”的方法,将哈希值的高16位与低16位进行异或操作(^)。
- 计算索引(取模):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方法流程
- 初始化或扩容:
- 如果当前哈希表为空,或当前哈希表的大小大于或等于阈值(capacity * loadFactor),则进行扩容操作。
- 计算哈希值和索引:
- 使用 hashCode() 方法计算 key 的哈希值。
- 使用
(n - 1) & hash
计算哈希值的索引, n 是哈希表的长度。
- 处理哈希冲突:
- 如果发生了哈希冲突,则遍历该位置处的链表或红黑树。
- 如果链表中存在相同哈希值和相等键(通过 equals(Object obj) 方法判断),则更新该元素的值(即替换旧值)。
- 否则,将新元素添加到链表或红黑树的末尾。
- 如果链表长度超过了树化阈值(默认为 8),并且哈希表的大小超过 64,则将链表转换为红黑树。
- 插入新元素:
- 如果没有哈希冲突,则创建一个新节点,并将新元素插入。
- 更新元素数量:
- 更新哈希表中元素的数量 size。
- 返回旧值(如果存在):
- 如果在插入新元素之前,已经存在相同键的元素,则返回该元素的旧值;否则返回 null。
一般使用什么类型作为Key
HashMap 的 key 通常使用不可变对象,如 Integer、String、枚举类型(enum)或者自定义的实现了正确 hashCode() 和 equals() 方法的不可变类。
因为 String 是不可变的,所以在创建的时候 hashcode 就被缓存了,不需要重新计算。
HashMap为什么线程不安全
- 无同步机制:HashMap 的内部没有使用任何同步机制(如 synchronized)来保证多线程环境下操作的原子性。
- 扩容非原子:当 HashMap 的容量不足时,会进行扩容操作,这是一个非原子的过程。在扩容期间,如果其他线程尝试访问或修改 HashMap,可能会导致数据不一致或异常。
- 哈希冲突解决:HashMap 使用链表或红黑树(JDK 1.8)来解决哈希冲突。在并发环境下,如果多个线程同时修改同一个哈希桶(bucket)中的元素,可能会导致链表或红黑树的结构被破坏。
- 可见性问题:由于 Java 内存模型(JMM)的原因,在没有同步的情况下,一个线程对 HashMap 的修改可能对其他线程不可见。可能导致线程之间看到的数据状态不一致。
HashMap如何扩容
- 检查是否需要扩容:检查当前 HashMap 的实际元素数量(size)是否超过了阈值 threshold = capacity * loadFactor 。
- 确定新的容量:新容量通常是当前容量的两倍。
- 创建新的哈希表:根据新容量,创建一个新的哈希表数组。
- 重新哈希和迁移元素:遍历旧哈希表中的每个元素,重新计算其在新哈希表中的索引位置,并将其插入到新的哈希表中。这个过程被称为 ReHashing。对于每个元素,根据其 key 的哈希值和新哈希表的大小,通过
(n - 1) & hash
( n 是新哈希表的大小)计算它在新哈希表中的位置。 - 更新引用:当所有的元素都被插入到新的哈希表中后,将原哈希表的引用更新为新的哈希表。原哈希表就被垃圾回收器回收了。
HashMap和Hashtable的区别
- 线程是否安全:HashMap 非线程安全,而 HashTable 线程安全。HashTable 内部基本都使用了 synchronized 修饰(现在推荐使用 ConcurrentHashMap)。
- 效率: 由于线程安全问题,HashMap 效率比 HashTable 高。HashTable 基本被淘汰了,不推荐使用。
- 空值:HashMap 允许 null 作为键(key)和值(value),而 Hashtable 不允许。
- 内部实现:在计算 hash 值时,HashMap 会重新计算,而 Hashtable 直接使用对象的hashCode。在扩容方式上,HashMap 默认容量为16(JKD1.8),扩容时容量会变为2n。Hashtable 默认容量为11,并且扩容时将容量变为原来的 2n+1。
- 底层数据结构:HashMap 使用数组+链表+红黑树(JDK1.8),HashTable 则没有。