HashMap(1)
前文「JDK源码一文详解-HashMap」分析了 HashMap 的内部结构和主要方法的实现原理。但是,面试中通常还会问到很多其他的问题,本文简要分析下常见的一些问题。
这里再贴一下 HashMap 内部的结构图(JDK 1.8):
FAQ:
Q1: HashMap 是否线程安全?为什么?
首先 HashMap 是线程不安全的。这一点很多人应该都了解,HashMap 源码中也有说明。但是为什么说不安全?体现在哪里呢?下面通过两个例子简要进行分析(可能不够全面,仅做参考)。
case 1:
线程 T1 执行 put / remove 等结构性修改(structural modification)的操作;线程 T2 执行遍历操作,这种情况下会抛出 ConcurrentModificationException.
示例代码(以 put 为例):
private static void test() {
Map<Integer, Integer> map = new HashMap<>();
Thread t1 = new Thread(() -> {
for (int i = 0; i < 5000; i++) {
map.put(i, i);
}
});
Thread t2 = new Thread(() -> {
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
System.out.println(entry);
}
});
t1.start();
t2.start();
}
// 执行结果:
// 抛出 java.util.ConcurrentModificationException
原因在这里:
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
HashMap 的迭代器和集合视图中,都会对该值进行比较。目的是判断是否有其他线程正在对该 HashMap 进行结构性修改,若有则抛会出异常。
PS: 细心阅读 HashMap 源码的话可以发现,结构性修改的方法中都会有如下一行代码:
++modCount;
该值就是用来记录结构性修改的次数。
case 2:
线程 T1 和 T2 同时执行 put / remove 等结构性修改(structural modification)的操作。以 put 方法为例分析,会发生元素覆盖。
示例代码:
private static void test() throws InterruptedException {
Map<Integer, Integer> map = new HashMap<>();
Thread t1 = new Thread(() -> {
for (int i = 0; i < 5000; i++) {
map.put(i, i);
}
});
Thread t2 = new Thread(() -> {
for (int i = 5000; i < 10000; i++) {
map.put(i, i);
}
});
t1.start();
t2.start();
TimeUnit.SECONDS.sleep(20);
System.out.println(map);
System.out.println("size: " + map.size());
}
// 输出结果:
// {8192=8192, 8193=8193, 8194=8194, 8195=8195, ...
// size: 9666
// PS: 这是某一次的结果,多次测试的具体结果可能不同,但基本都没有 size=10000 的情况。
这里问题出在 put 方法上,通过前文分析 HashMap 中 put 方法的内部实现原理可以找出原因,这里不再赘述。
这里再说一句,HashMap 的设计就是为了单线程下的高效率,了解线程不安全是为了加深对它的理解,知道在哪些情况不适合使用,若有线程安全的需求,可以考虑使用 ConcurrentHashMap。
Q2: 链表和红黑树的转换阈值为什么是 8 和 6 ?
首先分析下为什么会有链表和红黑树。理想情况下,HashMap 中每个 bin 所在位置只有一个节点,这样查询效率最高,为 O(1)。而拉出一个链表、或者把链表再转为红黑树,是在散列冲突比较严重时的一种应对措施,目的是为了让 HashMap 在极端情况下仍然能够保持较高的效率。
至于为什么是 8,HashMap 的部分 Implementation notes 如下:
/* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
*/
由于 TreeNode 的大小是普通节点(Node)的两倍,因此只有当 bin 中包含足够多(即树化的阈值 TREEIFY_THRESHOLD)的节点时才会转为 TreeNode;而当 bin 中节点减少时(删除节点或扩容),又会把红黑树再转为链表。
hashCode 均匀分布时,TreeNode 用到的机会很小。理想情况下,在随机分布的 hashCode 下,bin 中节点的分布遵循泊松分布,并列出了几个数据,可以看到一个 bin 中链表长度达到 8 的概率(0.00000006)不足千万分之一,因此将转换的阈值设为 8.
两个转换阈值及其说明如下:
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
至于将红黑树转为链表的阈值为 6,网上有说法是为了避免频繁转换。比如,若红黑树转为链表的阈值也是 8,如果一个 HashMap 不停地进行插入和删除元素,链表的个数一直在 8 左右,这种情况会频繁地进行树和链表的相互转换,效率很低。
这样解释似乎也有些道理,各位可以去探索。
Q3: 为什么负载因子是 0.75?
JDK 1.7 中的相关描述:
/* As a general rule, the default load factor (.75) offers a good tradeoff
* between time and space costs. Higher values decrease the space overhead
* but increase the lookup cost (reflected in most of the operations of the
* <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>).
*/
下面文章也对此做了分析:
HashMap的loadFactor为什么是0.75?
https://www.jianshu.com/p/64f6de3ffcc1
也许这个问题没必要那么深究,简单来讲,其实就是时间和空间的 tradeoff.
Q4: 为什么容量是 2 的次幂?
位运算 n & (length - 1) 和取余运算 n % length 效果是一样的。但是在计算机中,位运算的效率却远高于取余运算。因此,这样做是为了提高运算效率。
Q5: 一般用什么类型的元素作为 Key?为什么?
一般用 String、Integer 等,它们是不可变的(Immutable),作为不可变类天生是线程安全的。而且重写了 hashCode 方法和 equals 方法。
Q6: 衡量 hash 算法的好坏?String 类的 hashCode 实现?
hash 方法的设计可以有很多。虽然散列值越均匀越好,但 HashMap 首要目的是追求快,因此 hash 算法的设计要尽可能地快。String 类的 hashCode 方法如下:
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
PS: 上述问题是本人从网上搜索后整理和思考的结果,仅做参考,并不一定完全准确(要持有怀疑态度)。有关 HashMap 的问题可能还有很多,这里不再一一列举。
Lock&Condition
涉及多线程问题,往往绕不开「锁」。在 JDK 1.5 之前,Java 通过 synchronized 关键字来实现锁的功能,该方式是语法层面的,由 JVM 实现。JDK 1.5 增加了锁在 API 层面的实现,也就是 java.util.concurrent.locks.Lock 接口及其相关的实现类,它不仅具备 synchronized 的功能,而且还增加了更加丰富的功能。通常与其配合使用的还有 Condition 接口。
本文先简要分析下接口定义,后文再分析相关实现类的原理。
接口分析
Lock 接口的定义如下:
public interface Lock {
// 阻塞式获取锁,该方法与synchronized功能类似
void lock();
// 获取锁,可响应中断
void lockInterruptibly() throws InterruptedException;
// 尝试获取锁,若成功返回true;否则返回false
boolean tryLock();
// 尝试获取锁(在给定的时间内),若成功返回true;否则返回false
boolean tryLock(long time, TimeUnit unit) throws InterruptedException;
// 释放锁
void unlock();
// 创建一个与该锁绑定的Condition
Condition newCondition();
}
Condition 接口定义如下:
public interface Condition {
// 使当前线程等待,直到被signal唤醒或被中断
void await() throws InterruptedException;
// 使当前线程等待,直到被signal唤醒(不响应中断)
void awaitUninterruptibly();
// 使当前线程等待,直到被signal唤醒、或被中断、或到达等待时间
long awaitNanos(long nanosTimeout) throws InterruptedException;
// 使当前线程等待,直到被signal唤醒、或被中断、或到达等待时间(与上面方法类似)
boolean await(long time, TimeUnit unit) throws InterruptedException;
// // 使当前线程等待,直到被signal唤醒、或被中断、或到达给定的截止时间
boolean awaitUntil(Date deadline) throws InterruptedException;
// 唤醒一个等待的线程
void signal();
// 唤醒所有等待的线程
void signalAll();
}
Condition 的方法虽然不少,但其实就两类:
1. await* 方法,让当前线程处于等待状态;
2. signal* 方法,唤醒处于等待的线程。
此外,还有一个 ReadWriteLock 接口:
public interface ReadWriteLock {
// 读锁
Lock readLock();
// 写锁
Lock writeLock();
}
定义了读锁和写锁,其中读锁是共享的,写锁是互斥的。
代码示例
以典型的“生产者-消费者”模型为例,下面分别使用 synchronized 和 Lock 方式来实现并比较其用法。
使用 synchronized 和 wait/notify 实现,示例代码:
public class ProdConsumerTest {
private static final Object monitor = new Object();
private Random random = new Random();
private static final int SIZE = 10;
private Queue<Integer> queue = new LinkedList<>();
private void produce() throws InterruptedException {
for (; ; ) {
synchronized (monitor) {
if (queue.size() >= SIZE) {
monitor.wait();
}
int nextInt = random.nextInt(1000);
queue.offer(nextInt);
sleep(400);
System.out.println("size=" + queue.size() + ", 生产-->" + nextInt);
monitor.notify();
}
}
}
private void consume() throws InterruptedException {
for (; ; ) {
synchronized (monitor) {
if (queue.size() <= 0) {
monitor.wait();
}
Integer poll = queue.poll();
sleep(300);
System.out.println("size=" + queue.size() + ", 消费成功-->" + poll);
monitor.notify();
}
}
}
private void sleep(int timeout) {
try {
TimeUnit.MILLISECONDS.sleep(timeout);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
public static void main(String[] args) {
ProdConsumerTest test = new ProdConsumerTest();
Thread t1 = new Thread(() -> {
try {
test.produce();
} catch (InterruptedException e) {
e.printStackTrace();
}
});
Thread t2 = new Thread(() -> {
try {
test.consume();
} catch (InterruptedException e) {
e.printStackTrace();
}
});
t1.start();
t2.start();
}
}
使用 Lock/Condition 实现,示例代码:
public class ProdConsumerTest {
private static final int SIZE = 10;
private Random random = new Random();
private Queue<Integer> queue = new LinkedList<>();
// ReentrantLock 是 JDK 提供的 Lock 接口实现类,后文分析其原理
private Lock lock = new ReentrantLock();
private Condition notFull = lock.newCondition();
private Condition notEmpty = lock.newCondition();
private void produce() throws InterruptedException {
for (; ; ) {
lock.lock();
try {
if (queue.size() >= SIZE) {
notFull.await();
}
int nextInt = random.nextInt(1000);
queue.offer(nextInt);
sleep(400);
System.out.println("size=" + queue.size() + ", 生产-->" + nextInt);
notEmpty.signal();
} finally {
lock.unlock();
}
}
}
private void consume() throws InterruptedException {
for (; ; ) {
lock.lock();
try {
if (queue.size() <= 0) {
notEmpty.await();
}
Integer poll = queue.poll();
sleep(300);
System.out.println("size=" + queue.size() + ", 消费成功-->" + poll);
notFull.signal();
} finally {
lock.unlock();
}
}
}
private void sleep(int timeout) {
try {
TimeUnit.MILLISECONDS.sleep(timeout);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
public static void main(String[] args) {
ProdConsumerTest test = new ProdConsumerTest();
Thread t1 = new Thread(() -> {
try {
test.produce();
} catch (InterruptedException e) {
e.printStackTrace();
}
});
Thread t2 = new Thread(() -> {
try {
test.consume();
} catch (InterruptedException e) {
e.printStackTrace();
}
});
t1.start();
t2.start();
}
}
通过对比发现,Lock/Condition 可以实现和 synchronized 一样的功能,而 Condition 的 await/signal 则相当于 Object 的 wait/notify。
本文简要分析了 Lock 和 Condition 接口,后文再分析它们的实现原理。