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 接口，后文再分析它们的实现原理。

JDK源码一文详解——HashMap(1)，Lock&Condition

HashMap(1)

Lock&Condition

相关推荐

取消回复欢迎你发表评论:

Google 黑客常用搜索语句一览原力计划

npx简介（npxvip是哪国的）

在 Android 模拟器上运行 ARM 应用（android模拟器原理）

GB28181,B接口协议之SIPRTSPRTPRTMP协议从入门到精通

手机实时提取SIM卡打电话的信令和声音-辅助外设与商用通话方案

轻松转换!AppleNumbers到Excel的快捷教程

电脑端腾讯文档如何导出excel

简单而准确，在 Python 中计算日期时间的时差

Python自动化办公——后台截图（python 自动截图）

网络流媒体经典开源软件宝典webRTC, FFMpeg, SIP_流媒体开发教程

JDK源码一文详解——HashMap(1)，Lock&amp;Condition

HashMap(1)

Lock&Condition

相关推荐

取消回复欢迎 你 发表评论:

Google 黑客常用搜索语句一览 原力计划

npx简介（npxvip是哪国的）

在 Android 模拟器上运行 ARM 应用（android模拟器原理）

GB28181,B接口协议之SIPRTSPRTPRTMP协议从入门到精通

手机实时提取SIM卡打电话的信令和声音-辅助外设与商用通话方案

轻松转换!AppleNumbers到Excel的快捷教程

电脑端腾讯文档如何导出excel

简单而准确，在 Python 中计算日期时间的时差

Python自动化办公——后台截图（python 自动截图）

网络流媒体经典开源软件宝典webRTC, FFMpeg, SIP_流媒体开发教程

JDK源码一文详解——HashMap(1)，Lock&Condition

取消回复欢迎你发表评论:

Google 黑客常用搜索语句一览原力计划