在Java面试中很多公司都会面试到的一点是HashMap和ConcurrentHashMap的区别以及JDK7和JDK8中HashMap的区别。
那么，今天我们一起来从源码中看看他们到底有什么不同呢？
首先，我们需要知道的一点是HashMap是线程不安全的，而ConcurrentHashMap是线程安全的。
其次，Map类型的数据结构最主要的两个方法是get(K)和put(K,V)。
在JDK7中，
HashMap其内部结构是数组+链表的形式存放元素的
数组默认初始化大小为16，最大的数组长度是1<<30,加载因子是0.75
初始化一个HashMap 可以不指定其初始数组大小（默认16），也可以指定数组长度以及加载因子
其最终调用其构造方法为
public HashMap(int initialCapacity,float loadFactor){
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//以上都是一些验证
// Find a power of 2 >= initialCapacity
//找到一个大于初始容量大小的2的次方的数，很关键
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
//计算需要扩容的阈值
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}
在HashMap构造方法中，只有一个找到一个大于指定初始化容量的2的次方的数这步比较关键，对于下面put操作有影响。
请注意HashMap数组的容量必须是2的次方
接下来，重点看map.put(K,V)操作，put操作如果在相同key上有一个旧值，新值会覆盖旧值，并返回旧值，这个应该说是HashMap中是最重要的一个方法了，相对来说也比较复杂。在多线程中，hashmap的put操作可能会引起死循环，所以在并发情况下不能使用HashMap。
先看下put方法的源码
public V put(K key, V value) {
//1.如果table为空，需要创建并初始化指定大小的数组
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//2.如果 key 为 null，循环遍历table[0]上的链表，最终会将这个 entry 放到 table[0] 中
if (key == null)
return putForNullKey(value);
//3.计算key的哈希值
int hash = hash(key);
//4、通过h & (length-1)即h%length求模找到键值对放在哪个位置。
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//循环对应位置的单向链表，逐个查找每个链表节点上是否有整个键了。
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//hash值为整数，比较性能比equals高；另外短路运算，哈希值系统了就没必要在比较equals。
V oldValue = e.value;//先将当前节点的键对应的值取出来。
e.value = value; //替换为新值。
e.recordAccess(this);
return oldValue;
}
}
modCount++; //容器修改次数加1
addEntry(hash, key, value, i); //在指定的位置上添加数据，若空间不够则动态扩充，当前容量乘以2，新建一个数组，长度为capacity*2；并将原来的数组拷贝过来，更新对应变量。
return null;
}
//数组初始化：
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize); //指定数组容量，默认为16
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity]; //改变数组的引用，指向新创建的数组
initHashSeedAsNeeded(capacity);
}
//计算键值对的位置：
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
//这个地方很重要 也就是解释了为什么一定数组容量一定要是2的次方
//读者可以自己去思考下，在JDK某个版本中取模操作速度很慢 JDK作者采用了此中底层操作方法加快速度
return h & (length-1); //等同于h%length
}
//添加节点到链表中
void addEntry(int hash, K key, V value, int bucketIndex) {
//假如map中的元素个数大于等于阈值并且在bucketIndex的位置已经有元素，那么需要进行动态扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容 一般是当前表大小的两倍
resize(2 * table.length);
//计算key的hash值
hash = (null != key) ? hash(key) : 0;
//计算在数组存储下标
bucketIndex = indexFor(hash, table.length);
}
//创建元素及链表节点
createEntry(hash, key, value, bucketIndex);
}
//新建一个Entry对象，插入链表表头，size++
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
//数组扩容
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//新建一个容量扩充2倍的数组
Entry[] newTable = new Entry[newCapacity];
//调用transfer方法将旧数组中的键值对拷贝过来
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//旧数组原来的堆空间设置为引用切断,指向新数组
table = newTable;
//重新计算阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//map中数据移动分配等于循环遍历map并做put操作
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
//是否重新计算key的哈希
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//重新计算元素位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
总结：put操作步骤
1)、计算key的哈希值；
2)、根据哈希值并计算数组元素的保存位置下标；
3)、根据需要进行数组扩容；
4)、将键值对插入到对应的链表头部或更新已有值；
map.put方法应该是HashMap中相对复杂的一个方法了。
再接着是get方法了
public V get(Object key) {
//如果key为空则直接在table[0]取值,所以直接调用getForNullKey方法遍历对应链表即可。
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
//在JDK7中table[0]的位置一般只会有一个值
//遍历table[0]位置的链表，返回对应key==null的值，若果返回null,则有两种情况，要么没有key==null的键值对，要么对应位置上的值为null。
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
//key值不为空，则调用返回对应的值：
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
get方法还是很简单的。
那么接来下接着看JDK7的ConcurrentHashMap：
一般的防止并发带来的问题，我们会给需要同步的方法加一个synchronized的关键字，在Java中就是变成了HashTable，但是效率会相对低下。
ConcurrentHashMap改进了效率低下的问题，使用了分段锁机制（Segment）。
图示结构
static class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
final float loadFactor;
Segment(float lf) { this.loadFactor = lf; }
}
一个Segment相当于一个小的HashMap并且每个Segment拥有一个可重入锁。
在初始化ConcurrentHashMap时，先生成一个Segment数组（但不先分配Segment对象）。
Segment个数可在初始化ConcurrentHashMap时指定，默认时16和table数组大小一致。
ConcurrentHashMap在定位一个元素的时候需要进行两次Hash操作，第一次定位元素所在的Segment，第二次相当于查找在Segment中定位元素的具体位置。
相较于HashMap，ConcurrentHashMap的好处在于在写操作时，只需要对元素所处的Segment加锁即可，不影响其他Segment的操作，这样，在最理想的情况下，ConcurrentHashMap可以最高同时支持Segment数量大小的写操作，但是hash的次数会多一次。
JDK1.8
HashMap的内部结构发生了变化
如果同一table[n]中的链表长度超过8，那么就将原来的链表转为红黑树。
HashMap的put方法实现
思路如下：
1.table[]是否为空
2.判断table[i]处是否插入过值
3.判断链表长度是否大于8，如果大于就转换为红黑二叉树，并插入树中
4.判断key是否和原有key相同，如果相同就覆盖原有key的value，并返回原有value
5.如果key不相同，就插入一个key，记录结构变化一次
HashMap的get方法实现
实现思路：
1.判断表或key是否是null，如果是直接返回null
2.判断索引处第一个key与传入key是否相等，如果相等直接返回
3.如果不相等，判断链表是否是红黑二叉树，如果是，直接从树中取值
4.如果不是树，就遍历链表查找
扩容机制
我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。
ConcurrentHashMap
JDK8中ConcurrentHashMap 借鉴了HashMap的数组+链表+红黑树的实现方式来设计，并且采用了CAS的乐观锁锁机制。
CAS（compare and swap）：CAS 操作含有三个操作数 ： 内存位置（V）、预期旧值（A）和新值(B)。如果内存里面的值和A值是一样的，那就将内存中的值更新成B值。CAS是通过无限循环来获取数据的，如果在第一轮循环中，a线程获取地址里面的值被b线程修改了，那么a线程需要自旋，到下次循环才有可能机会执行。
在JDK8中，ConcurrentHashMap不再采用Segment分段锁，而采用了Node。
Node：保存key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。
关于ConcurrentHashMap更详细的讲解可参考以下这篇文章：
https://blog.csdn.net/programerxiaoer/article/details/80040090