1 大致对比
| 名称 | 线程是否安全 | 实现接口 | 父类 | 能否使用Null作为键值对 |
| HashMap | 不安全 | Map、Cloneable、Serializable | AbstractMap | 可以使用一个null作为键值对 |
| HashTable | 安全 | Map、Cloneable、Serializable | Dictionary | 不可以使用null作为键值对 |
| ConcurrentHashMap | 安全 | ConcurrentMap、Serializable | AbstractMap | 不可以使用null作为键值对 |
2 HashMap
HashMap的类继承关系：
2.1 jdk7中HashMap的底层实现
JDK7 中，HashMap 采用数组+链表的实现，即使用链表来处理冲突，产生Hash碰撞时，同一 hash 值的链表都存储在一个数组元素中。但是当位于一个数组元素的链表中的元素较多，即 hash 值相等的元素较多时，通过 key 值依次查找的效率较低。数据结构如下:
HashMap 底层数据结构就是一个 Entry 数组，Entry 是 HashMap 的基本组成单元，每个 Entry 中包含一个 key-value 键值对。
2.2 jdk8中HashMap的底层实现
JDK8中，HashMap进行了大量的源码修改，底层的数据结构变为了数组+链表+红黑树，如果发生碰撞的时候当数组的每个链表的长度大于8时，HashMap通过链表将产生碰撞冲突的元素组织起来。会将链表自动转化为红黑树，从而提高速度。
Node节点（链表）
/** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */ 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; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } } 复制代码
Entry接口
Enrty主要提供的方法就是计算节点长度，get和push操作，全部方法如下：
TreeNode（红黑树）
- 和一般的二叉搜索树类似，红-黑树的查找、插入和删除的时间复杂度为O(logzN)。在红-黑树中的查找时间和在普通二叉搜索树中的查找时间应该几乎完全一样，因为
在查找的过程中并没有应用红-黑树的特征。额外的开销只是每一个节点的存储空间都稍微增加了一点，来存储红-黑的颜色(一-个boolean变量)。
更为特别的，根据Sedgwick的说法(参见附录B)，实际上在红-黑树中的查找大约需要log；N次比较，并且也说明了查找不可能需要超过2*log2N次比较. - 插入和删除的时间要增加一个常数因子，因为不得不在下行的路径上和插入点执行颜色变换和旋转。平均起来，一次插入大约需要一次旋转。因此，插入的时间复杂度还是O(log;N)，但是比在普通的二叉搜索树中要慢。
因为在大多数应用中，查找的数次比插入和删除的次数多，所以应用红-黑树取代普通的二叉搜索树总体上不会增加太多的时间开销.当然，红-黑树的优点是对有序数据的操作不会慢到O(N)的时间复杂度.
网络异常，图片无法展示|
2.3 put的过程
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 如果table 为null 或者没有为 table 分配内存，就resize一次 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 指定hash值节点为空则直接插入，这个(n - 1) & hash才是表中真正的哈希 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 如果不为空 else { Node<K,V> e; K k; // 计算表中的这个真正的哈希值与要插入的key.hash相比 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 若不同的话，并且当前节点已经在 TreeNode 上了 else if (p instanceof TreeNode) // 采用红黑树存储方式 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // key.hash 不同并且也不再 TreeNode 上，在链表上找到 p.next==null else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { // 在表尾插入 p.next = newNode(hash, key, value, null); // 新增节点后如果节点个数到达阈值，则进入 treeifyBin() 进行再次判断 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果找到了同 hash、key 的节点，那么直接退出循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; // 更新 p 指向下一节点 p = e; } } // map中含有旧值，返回旧值 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } // map调整次数 + 1 ++modCount; // 键值对的数量达到阈值，需要扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 复制代码
2.4 扩容机制
- 数组的初始容量为16，而容量是以2的次方扩充的，一是为了提高性能使用足够大的数组，二是为了能使用位运算代替取模预算(据说提升了5~8倍)。
- 数组是否需要扩充是通过负载因子判断的，如果当前元素个数为数组容量的0.75时，就会扩充数组。这个0.75就是默认的负载因子，可由构造器传入。我们也可以设置大于1的负载因子，这样数组就不会扩充，牺牲性能，节省内存。
- 为了解决碰撞，数组中的元素是单向链表类型。当链表长度到达一个阈值时（7或8），会将链表转换成红黑树提高性能。而当链表长度缩小到另一个阈值时（6），又会将红黑树转换回单向链表提高性能。
- 对于第三点补充说明，检查链表长度转换成红黑树之前，还会先检测当前数组数组是否到达一个阈值（64），如果没有到达这个容量，会放弃转换，先去扩充数组。所以上面也说了链表长度的阈值是7或8，因为会有一次放弃转换的操作。
2.5 get过程
首先会检查 table 中的元素是否为空，然后根据 hash 算出指定 key 的位置。然后检查链表的第一个元素是否为空，如果不为空，是否匹配，如果匹配，直接返回这条记录；如果匹配，再判断下一个元素的值是否为 null，为空直接返回，如果不为空，再判断是否是 TreeNode 实例，如果是 TreeNode 实例，则直接使用 TreeNode.getTreeNode 取出元素，否则执行循环，直到下一个元素为 null 位置。
2.6 HashMap如何实现线程安全
- 直接使用Hashtable类；
- 直接使用ConcurrentHashMap；
- 使用Collections将HashMap包装成线程安全的Map。
HashMap是非线程安全的，这意味着不应该在多线程中对这些Map进行修改操作，否则会产生数据不一致的问题，甚至还会因为并发插入元素而导致链表成环，这样在查找时就会发生死循环，影响到整个应用程序。
Collections工具类可以将一个Map转换成线程安全的实现，其实也就是通过一个包装类，然后把所有功能都委托给传入的Map，而包装类是基于synchronized关键字来保证线程安全的（Hashtable也是基于synchronized关键字），底层使用的是互斥锁，性能与吞吐量比较低。
ConcurrentHashMap的实现细节远没有这么简单，因此性能也要高上许多。它没有使用一个全局锁来锁住自己，而是采用了减少锁粒度的方法，尽量减少因为竞争锁而导致的阻塞与冲突，而且ConcurrentHashMap的检索操作是不需要锁的。
3 HashTable
3.1 底层实现
HashTable的主要方法实现逻辑和数据结构，与HashMap中非常相似，有一点重大区别就是所有的操作都是通过synchronized锁保护的。只有获得了对应的锁，才能进行后续的读写等操作。
另外HashTable不允许将null作为键和值。
3.2 put过程
//将方法加锁 public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)tab[index]; for(; entry != null ; entry = entry.next) { if ((entry.hash == hash) && entry.key.equals(key)) { V old = entry.value; entry.value = value; return old; } } addEntry(hash, key, value, index); return null; } 复制代码
3.3 扩容机制
Hashtable的扩容机制通过rehash()来实现，如果Hashtable中元素的个数大于临界值时，会调用rehash()来实现扩容。临界值的大小等于Hashtable数组的大小与负载因子相乘，默认的负载因子大小为0.75。
3.4 get过程
public synchronized V get(Object key) { Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { return (V)e.value; } } return null; } 复制代码
HashTable的get过程还是比较简单的，先取到key的哈希值，然后再遍历Entry数组进行查找，找到相等则返回，否则返回空。
4 ConcurrentHashMap
3.1 底层实现
3.1.1 jdk1.7
在 jdk 1.7 中，ConcurrentHashMap 是由 Segment 数据结构和 HashEntry 数组结构构成，采取分段锁来保证安全性。Segment 是 ReentrantLock 重入锁，在 ConcurrentHashMap 中扮演锁的角色，HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，一个 Segment 里包含一个 HashEntry 数组，Segment 的结构和 HashMap 类似，是一个数组和链表结构。
3.1.2 jdk1.8
JDK1.8 的实现已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 Synchronized 和 CAS 来操作，整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本。
3.2 put过程
public V put(K key, V value) { return putVal(key, value, false); } /** Implementation for put and putIfAbsent */ final V putVal(K key, V value, boolean onlyIfAbsent) { //键和值都不能为空 if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; //判断Node[]数组是否初始化，没有则进行初始化操作 if (tab == null || (n = tab.length) == 0) tab = initTable(); //通过hash定位数组的索引坐标，是否有Node节点，如果没有则使用CAS进行添加 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } //检查到内部正在扩容，就帮助它一块扩容。 else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { V oldVal = null; //对Node加锁 synchronized (f) { //如果f！=null，则使用synchronized锁住f元素（链表/红黑树的头元素）。如果是Node（链表结构）则执行链表的添加操作；如果是TreeNode（树型结构）则执行树添加操作。 if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; //通过hash定位数组的索引坐标，是否有Node节点，如果没有则使用CAS进行添加（链表的头节点），添加失败则进入下次循环。 if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } if (binCount != 0) { //判断链表长度已经达到临界值8（默认值），当节点超过这个值就需要把链表转换为树结构 if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } //如果添加成功就调用addCount（）方法统计size，并且检查是否需要扩容 addCount(1L, binCount); return null; } 复制代码
3.3 扩容机制
什么情况下扩容？
1、如果新增节点之后，所在链表的元素个数达到了阈值 8，则会调用treeifyBin方法把链表转换成红黑树，不过在结构转换之前，会对数组长度进行判断，实现如下：
- 如果数组长度n小于阈值MIN_TREEIFY_CAPACITY，默认是64，则会调用tryPresize方法把数组长度扩大到原来的两倍，并触发transfer方法，重新调整节点的位置。
2、新增节点之后，会调用addCount方法记录元素个数，并检查是否需要进行扩容，当数组元素个数达到阈值时，会触发transfer方法，重新调整节点的位置。
3、当前线程发现此时map正在扩容，则协助扩容。
如何扩容？
1、扩容线程A 以CAS的方式修改transferindex=31-16=16 ,然后按照降序迁移table[31]至table[16]这个区间的hash桶
2、迁移hash桶时，会将桶内的链表或者红黑树，按照一定算法，拆分成2份，将其插入nextTable[i]和nextTable[i+n]。 迁移完毕的hash桶,会被设置成ForwardingNode节点，以此告知访问此桶的其他线程，此节点已经迁移完毕。
3、此时线程2访问到了ForwardingNode节点，如果线程2执行的put或remove等写操作，那么就会先帮其扩容。如果线程2执行的是get等读方法，则会调用ForwardingNode的find方法，去nextTable里面查找相关元素
3.4 get过程
Segment的get操作实现非常简单和高效，先经过一次再散列，然后使用这个散列值通过散列运算定位到Segment，再通过散列算法定位到元素。get操作的高效之处在于整个get过程都不需要加锁，除非读到空的值才会加锁重读。原因就是将使用的共享变量定义成volatile类型
5 总结
总的来讲，Map就是一个能够很好实现KV存储的数据结构，在平时的项目开发中一定会很常用，Java的优越和强大就在于此，将Map分成很多种，每一种都有自己的优势和作用，比如单线程下使用HashMap可以不用考虑线程安全，而且效率要高于HashTable，多线程下推荐使用JUC提供的ConcurrentHashMap来替代HashMap，其内部很好的实现机制可以让程序在高并发下能够应对。总之，三种数据结构都非常值得我们研究。
