如果没有内存限制，如何快速、安全地将 1000 亿条数据插入到 HashMap 中？

回答重点

前置知识，需要先了解 HashMap 的原理

我们分析一下题目的关键点，HashMap、1000 亿条数据、无限制内存、快速、安全地插入。

首先无限制内存就不需要考虑机器或者 JVM 的内存溢出问题，在这个条件下 1000 亿还是 10000 亿都不影响，反正知道数据量很大就对了。

其次 HashMap + 插入，需要考虑影响性能的点：

哈希冲突，如果数据哈希冲突很大，都命中一个槽，如果是 JDK 8 之前版本，只用链表法解决冲突，那么将会非常耗时，JDK8 及之后引入红黑树，红黑树的插入时间复杂度是 O(log n)，虽然比链表法好了很多，但终究没O(1) 快。
扩容，HashMap 的插入过程，会先判定 HashMap 的空间是否足够，如果不够的话则会扩容，每次扩容都又需要将元素迁移，很浪费时间 HashMap 默认初始容量是为 16 ，如果插入到 1000 亿那得扩容多少次？

再者就是快速和安全，基于这两点大家应该能联想到多线程与并发安全，多线程插入肯定可以提高效率，但是 HashMap 又是一个非线程安全容器，因此使用多线程后就不安全了。

综上：

1）避免动态扩容，在 HashMap 创建的时候指定初始容量稍微超过 1000 亿，且负载因子配置为 1 （默认负载因子为 0.75）

负载因子的作用：假设当前 HashMap 容量设置为 16，负载因子是 0.75，则 16 * 0.75 = 12，当 HashMap 存储的数据达到了 12 的时，就会执行扩容操作。

2）采用多线程的方式，因为 HashMap 线程不安全的特性，其多线程插入的时候大概率会出现数据覆盖的情况，即线程不安全的情况。针对这种情况，我们可以使用 ConcurrentHashMap 解决并发安全问题，ConcurrentHashMap 也是 HashMap。

如果面试官非要用 HashMap 来做，那么我们可以把 ConcurrentHashMap 的线程安全机制搬运到外部来实现。

ConcurrentHashMap 对于冲突节点插入操作用的是 CAS + synchronized 来保证线程安全。

参考 ConcurrentHashMap，我们可以有以下思路：

1）将 1000 亿条数据分成多份，再对应起多个线程。

2）同时创建一个数组（可以大小为 1000 亿，反正不考虑内存。），存放锁对象。

2）多线程并发将对应批次的数据插入到 HashMap。

3）但是每个数据插入之前需要抢锁，针对 HashMap 的槽都建立一把对应的锁（仿照 ConcurrentHashMap 的设计）。

4）每个数据先按照 HashMap 的哈希算法定位哈希槽的下标，根据下标从锁对象数组找到对应的锁对象，如果当前下标锁对象数组没数据，则创建一个锁对象，并通过 CAS 插入到锁对象数组中。

5）当前线程利用 synchronized（得到的锁对象）加锁，抢到锁之后再执行插入，这样就能避免多线程插入数据覆盖等问题了。

上述的本质就是 ConcurrentHashMap 的实现原理，无非就是搬运到外部来实现。

这里再提一下，线程数的控制可以自定义，和锁对象数组的大小没关系。（一千门对应有 1000 把锁，但不是非得叫 1000 个人去开锁）