Java面试题专集--HashMap

liuian 2025-05-27 15:53 34 浏览

HashMap的容量为什么是2的幂次

HashMap寻找Index位置是通过位运算计算出来的，但是原理是对length取余数，只有是2的次幂的时候h & (length - 1) == h % length (参数里的h就是key的hashCode，length就是容量capacity)

答：是因为效率，如果length为2的N次方，取模运算可以变成位与运算，效率显著提高！

HashMap原理、红黑树

https://blog.csdn.net/weixin_45093436/article/details/104273595

JDK1.7:哈希表是由数组+链表组成的，因为hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。因为HashMap使用LinkedList存储对象，这个Entry会存储在LinkedList中

在jdk1.8引入了红黑树的设计，当冲突的链表长度超过8个时，链表结构就会转为红黑树结构，这样做的好处是避免在极端条件的情况下冲突链表过长而导致查询效率非常慢。

红黑树查询:其访问性能近似于折半查找

红黑树的简单概念：红黑树是一种近似平衡的二叉查找树，其主要的优点就是平衡，即左右子树高度几乎一致，以此来防止树退化为链表，通过这种方式来保障查找的时间复杂度为log(n);

红黑树的调整方式： https://blog.csdn.net/weixin_45093436/article/details/104273595

HashMap size()方法怎么实现

https://www.jianshu.com/p/88881fdfcf4c

JDK 8 推荐使用mappingCount 方法，因为这个方法的返回值是 long 类型，不会因为 size 方法是 int 类型限制最大值（size 方法是接口定义的，不能修改）。

size 方法调用 sumCount 方法实现，

当 counterCells 是 null，就返返回baseCount ， put 结束后会对这个变量做 CAS 加法

当 counterCells 不是 null，就遍历元素，并和 baseCount 累加。

HashMap扩容

我们知道在HashMap的初始化默认容量是16。默认的负载因子大小为0.75

当一个map填满了75%的bucket时候，将会创建原来HashMap大小的两倍的bucket数组，

扩容需要遍历原数组，并且为其中的每个enrty进行hash计算。加入到新数组中，时间复杂度为O(n)。

扩容的成本并不低，最好是创建HashMap指定合适的大小

为啥扩容因子是0.75

选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折衷选择， 0.75的话碰撞最小

HashMap线程不安全

因为多线程环境下，使用Hashmap进行put操作可能会引起死循环，导致CPU利用率接近100%，所以在并发情况下不能使用HashMap

cas是什么？（ConcurrentHashMap）

cas是compareandswap的简称，从字面上理解就是比较并更新，简单来说：从某一内存上取值V，和预期值A进行比较，如果内存值V和预期值A的结果相等，那么我们就把新值B更新到内存，如果不相等，那么就重复上述操作直到成功为止。

它可以解决多线程并发安全的问题，

ConcurrentHashMap

https://www.jianshu.com/p/865c813f2726

在JDK1.7版本中，ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成， 16个段，Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁，也就是上面的提到的锁分离技术，而每一个Segment元素存储的是HashEntry数组+链表，这个和HashMap的数据存储结构一样

JDK1.8的实现已经抛弃了Segment分段锁机制，利用CAS+Synchronized来保证并发更新的安全。数据结构采用：数组+链表+红黑树。

Java锁的分类

可重入锁：Synchronized和ReentrantLook都是可重入锁，锁的可重入性标明了锁是针对线程分配方式而不是针对方法。例如调用Synchronized方法A中可以调用Synchronized方法B，而不需要重新申请锁。
读写锁：按照数据库事务隔离特性的类比读写锁，在访问统一个资源（一个文件）的时候，使用读锁来保证多线程可以同步读取资源。ReadWriteLock是一个读写锁，通过readLock()获取读锁，通过writeLock()获取写锁。
可中断锁：可中断是指锁是可以被中断的，Synchronized内置锁是不可中断锁，ReentrantLock可以通过lockInterruptibly方法中断显性锁。例如线程B在等待等待线程A释放锁，但是线程B由于等待时间太久，可以主动中断等待锁。
公平锁：公平锁是指尽量以线程的等待时间先后顺序获取锁，等待时间最久的线程优先获取锁。synchronized隐性锁是非公平锁，它无法保证等待的线程获取锁的顺序，ReentrantLook可以自己控制是否公平锁。

lock和synchronized

https://www.jianshu.com/p/b343a9637f95

Synchronized和Lock比较

Synchronized是关键字，内置语言实现，Lock是接口。
Synchronized在线程发生异常时会自动释放锁，因此不会发生异常死锁。Lock异常时不会自动释放锁，所以需要在finally中实现释放锁。
Lock是可以中断锁，Synchronized是非中断锁，必须等待线程执行完成释放锁。
Lock可以使用读锁提高多线程读效率。

常用的RuntimeException

NullPointerException - 空指针引用异常
ClassCastException - 类型强制转换异常。
IllegalArgumentException - 传递非法参数异常。
ArithmeticException - 算术运算异常
IndexOutOfBoundsException - 下标越界异常
NumberFormatException - 数字格式异常
UnsupportedOperationException - 不支持的操作异常