HashMap底层原理
在说HashMap底层原理之前，我们先来说一下HashMap与Hashtable和ConcurrentHashMap的区别。这篇文章主要去说JDK1.8版本的HashMap，其实他们的原理都差不多，都是数组加链表的存储形式。再讲之前我们先了解一下Map的继承体系：
HashMap与Hashtable的区别
相同点
- HashMap和Hashtable都是基于哈希表实现的，其内部每个元素都是key-value 键值对，
- HashMap和Hashtable都实现了Map、Cloneable、 Serializable 接口。
不同点
-
父类不同: HashMap继承了AbstractMap 类，而Hashtable继承了Dictionary 类
-
空值不同: HashMap 允许空的key和value值，HashTable 不允许空的key和value值。
HashMap会把Null key当做普通的key对待。不允许null key重复。
-
线程安全性: HashMap 不是线程安全的，如果多个外部操作同时修改HashMap的数据结构比如add或者是delete,必须进行同步操作，仅仅对key或者value的修改不是改变数据结构的操作。可以选择构造线程安全的Map比如Collections.synchronizedMap或者是ConcurrentHashMap。而Hashtable本身就是线程安全的容器。
-
性能方面:虽然HashMap和Hashtable都是基于单链表的，但是HashMap进行put或者get操作，可以达到常数时间的性能;而Hashtable的put和get操作都是加synchronized 锁的，所以效率很差。
-
初始容量不同: Hashtable 的初始长度是11，之后每次扩充容量变为之前的2n+1 (n为上一次的长度）而HashMap的初始长度为16，之后每次扩充变为原来的两倍。创建时，如果给定了容量初始值，那么Hashtable 会直接使用你给定的大小，而HashMap会将其扩充为2的幂次方大小。
HashMap和ConcurrentHashMap的区别
浅谈ConcurrentHashMap本质
我们为什么要使用ConcurrentHashMap
在并发编程中,jdk1.7的情况下使用 HashMap 可能造成死循环，而jdk1.8 中有可能会造成数据丢失
ConcurrentHashMap是在HashMap的基础上，将数据分为多个segment(段)，默认16个（concurrency level），然后每次操作对一个segment(段)加锁，避免多线程锁的几率，提高并发效率。
ConcurrentHashMap结构
jdk1.7中结构
jdk1.7中采用Segment+HashEntry的方式进行实现，采取分段锁来保证安全性。Segment 扮演锁的角色，HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，一个 Segment 里包含一个 HashEntry 数组，Segment 的结构和 HashMap 类似，是一个数组和链表结构。
jdk1.8中结构
JDK1.8 的实现已经摒弃了 Segment 的概念，而是直接用Node 数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized 和 CAS来操作，整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本。
区别总结
HashMap
- 底层数组+链表实现，可以存储null键和null值，线程不安全
- 初始size为16，扩容：newsize = oldsize*2，size一定为2的n次幂
- 扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
- 插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）
- 当Map中元素总数超过Entry数组的75%，触发扩容操作，为了减少链表长度，元素分配更均匀
- 计算index方法：index = hash & (tab.length – 1)
HashMap的初始值还要考虑加载因子:
- 哈希冲突：若干Key的哈希值按数组大小取模后，如果落在同一个数组下标上，将组成一条Entry链，对Key的查找需要遍历Entry链上的每个元素执行equals()比较。
- 加载因子：为了降低哈希冲突的概率，默认当HashMap中的键值对达到数组大小的75%时，即会触发扩容。因此，如果预估容量是100，即需要设定100/0.75＝134的数组大小。
- 空间换时间*：如果希望加快Key查找的时间，还可以进一步降低加载因子，加大初始大小，以降低哈希冲突的概率。*
ConcurrentHashMap
- 底层采用分段的数组+链表实现，线程安全
- 通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。)
- Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术
- 有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁
- 扩容：段内扩容（段内元素超过该段对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容），插入前检测需不需要扩容，有效避免无效扩容
ConcurrentHashMap是使用了锁分段技术来保证线程安全的。
锁分段技术：首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。
ConcurrentHashMap提供了与Hashtable和SynchronizedMap不同的锁机制。Hashtable中采用的锁机制是一次锁住整个hash表，从而在同一时刻只能由一个线程对其进行操作；而ConcurrentHashMap中则是一次锁住一个桶。
ConcurrentHashMap默认将hash表分为16个桶，诸如get、put、remove等常用操作只锁住当前需要用到的桶。这样，原来只能一个线程进入，现在却能同时有16个写线程执行，并发性能的提升是显而易见的。
HashMap存取元素详解
HashMap的存储方式是哈希表，那什么是哈希表呢，其实就是数组+链表。HashMap初始数组长度为16。数组的每个元素都保存着链表头的地址(或者为null)，在向HashMap中put（key，value）的时候，先使用hash算法计算哈希值，然后再和数组的长度减一做与运算。计算出此键值对应该保存到数组的那个位置上，如果此位置没有元素，意思就是链表的头结点为null，那么就新建一个node结点，把key，value以及next保存。Node类源码如下：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
....
......
........
}
保存键值对的node结点是一个实现了Map.Entry的内部类，里面的属性有hash值（就是通过hash算法计算出来的），key，value，以及next。
当执行put（key，value）的时候，如果计算出来的数组位置上有元素的话（说明计算出的hash值和此数组位置对应的单链表上的所有元素的hash值相同，即发生冲突。），就沿着此数组位置对应的单链表上的结点一个个比较，如果遇到相同的key，就用新的value替换掉旧的value，如果找不到相同的key，就新建一个node结点，保存hash值，key和value，然后插入到此单链表的尾部。
插入之后，这里程序会判断此单链表上的结点个数（这里注意，不是全部的元素结点个数，而是此单链表上的结点个数，和其他数组位置上的单链表无关）是否超过限制(HashMap默认是8)，如果超过限制，那么HashMap就会把此单链表转成红黑树，这样做的目的是为了提高get（key）的速度。时间复杂度会由原来的O(n)变成了O(logn) 。
一旦插入新的node，程序就会检查HashMap的元素个数（全部键值对的个数）是否超过阈值，这个阈值是计算出来的，就是装载因子乘上数组容量。
一旦装载量大于此阈值，程序就会执行resize()方法进行扩展容量，HashMap是直接扩容2倍，扩容之后，将原来链表数组的每一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置，这样就减少了每个链表的长度，增加查找效率，但是扩容是很耗费时间的。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始数组容量 16
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; //装载因子默认0.75
static final int TREEIFY_THRESHOLD = 8; //单链表结点个数超过8就转成红黑树
int threshold; //阈值，超过此数，就进行扩展容量
HashMap存储元素的大致情况
put操作源码解析
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
//1
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
HashMap.Node<K,V> e; K k;
//3
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//4
else if (p instanceof HashMap.TreeNode)
e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
//5
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//6
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//7
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//8
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
- 如果是第一次put元素，数组这个时候为null，那么程序会执行resize () 方法，此方法会初始化数组容里为16，即n=16
- 先计算要添加的键值对在数组中的位置i，如果此位置没有元素，就新建一个结点保存。
- 如果此位置的第一个结点的key和要添加的元素key相同，就执行步骤7,用新值替换旧值就行了
- 如果此数组位置上的第一个结点属于红黑树类型的,说明此数组位置上的单链表结点个数肯定大于等于8个,那么直接去红黑树上操作就可以了，如果有相同的key，e不为null，就执行步骤7，新值替换旧值
- 如果不是上述情况,说明此位置是个单链表，那么就在此单链表上查找有没有相同的key，没有就new个Node,然后检查此单链表的结点个数是否超过限制,超过就调用treeifyBin() 方法把单链表转换成红黑树。
- 如果在此链表中找到了相同的key，那么就和步骤3—样,继续执行步骤7。只不过3是在开头找到的,6是在中间找到的。都是继续执行7，新值替换旧值。
- 链表中找到了相同的key，将旧值替换为新值
- 如果容里超过了阀值，就会执行resize () 方法扩展容里
get操作的源码解析
final HashMap.Node<K,V> getNode(int hash, Object key) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
//1
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//2
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//3
if (first instanceof HashMap.TreeNode)
return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
//4
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
- 如果数组为null，或者此位置上的第一个结点为null，说明要获取的key-value不存在，直接return null
- 如果此位置第一个结点就是要查找的结点,那么直接return first
- 如果此数组位置第一个结点属于红黑树类型的，那么直接在红黑树上找就行了。
- 否则，就在单链表上一个个查找，找到就return此结点，找不到就return null
其实，HashMap的初始容量和装载因子都是可以通过HashMap的有参构造进行改的，如果使用无参的构造函数定义HashMap，那么这两个属性都是默认的。至此，HashMap的底层实现原理就介绍完了.
下面简单说下Hashtable和ConcurrentHashMap。它们两个都是线程安全的，都不可以存储值为null的key，但是它们在线程同步上有些区别。
Hashtable是在方法上使用synchronized关键字，其实这是对对象加锁，锁住的都是对象整体，当Hashtable的大小增加到一定的时候，性能会急剧下降，因为迭代时需要被锁定很长的时间。ConcurrentHashMap算是对上述问题的优化。
至此，HashMap的底层实现原理就介绍完了.
下面简单说下Hashtable和ConcurrentHashMap。它们两个都是线程安全的，都不可以存储值为null的key，但是它们在线程同步上有些区别。
Hashtable是在方法上使用synchronized关键字，其实这是对对象加锁，锁住的都是对象整体，当Hashtable的大小增加到一定的时候，性能会急剧下降，因为迭代时需要被锁定很长的时间。ConcurrentHashMap算是对上述问题的优化。
ConcurrentHashMap引入了分割(Segment)，可以理解为它把一个大的Map拆分成N个小的Hashtable，在put方法中，会根据哈希算法来先决定具体存放进哪个Segment，如果我们查看Segment的put操作源码，会发现内部使用的同步机制还是基于锁的，但是这样可以只对Map的一部分（Segment）进行上锁，影响的只是将要放入同一个Segment的元素的put操作，保证同步的时候，锁住的不是整个Map（而Hashtable是锁住全部的），相对于Hashtable的synchronized关键字锁的粒度更精细了一些，提高了多线程环境下的性能，所以Hashtable已被淘汰了。