前言
很快乐遇见你~
在 深刻分析HashMap 文章中我从散列表的角度解析了HashMap，在 深刻解析ConcurrentHashMap：感触并发编程智慧 解析了ConcurrentHashMap的底层实现原理。本文是HashMap系列文章的第三篇，次要内容是解说与HashMap相干的汇合类。
HashMap自身性能曾经绝对欠缺，但在某些非凡的情景下，他就显得无能为力，如高并发、须要记住key插入程序、给key排序等。实现这些性能往往须要付出肯定的代价，在没有必然的需要情景下，削减这些性能是没必要的。因此，为了进步性能，Java并没有把这些个性间接集成到HashMap中，拓展了领有这些个性的其余汇合类作为补充：
- 线程平安的ConcurrentHashMap、Hashtable、SynchronizeMap
- 记住插入程序的LinkedHashMap
- 记录key程序的TreeMap
这样，咱们就能够在特定的需要情景下，抉择最适宜咱们的汇合框架，从而来进步性能。那么明天这篇文章，次要就是剖析这些其余的汇合类的个性、付出的性能代价、与HashMap的区别。
那么，咱们开始吧~
Hashtable
Hashtable是属于JDK1.1的第一批汇合框架其中之一，其余的还有Vector、Stack等。这些汇合框架因为设计上的缺点，导致了性能的瓶颈，在jdk1.2之后就被新的一套汇合框架取代，也就是HashMap、ArrayList这些。HashMap在jdk1.8之后进行了全面的优化，而Hashtable仍旧放弃着旧版本的设计，在很多方面都落后于HashMap。上面次要剖析Hashtable在：接口继承、哈希函数、哈希抵触、扩容计划、线程平安等方面解析他们的不同。
接口继承
Hashtable继承自Dictionary类而不是AbstractMap，类图如下（jdk1.8）
Hashtable诞生的工夫是比Map早，但为了兼容新的汇合在jdk1.2之后也继承了Map接口。Dictionary在目前曾经齐全被Map取代了，所以更加倡议应用继承自AbstractMap的HashMap。为了兼容新版本接口还有Hashtable的迭代器：Enumerator。他的接口继承构造如下：
他不仅实现了旧版的Enumeration接口，同时也实现了Iteractor接口，兼容了新的api与应用习惯。这里对于Hashtable还有一个问题：Hashtable是fast-fail的吗 ？
fast-fail指的是在应用迭代器遍历汇合过程中，如果汇合产生了结构性扭转，如增加数据、扩容、删除数据等，迭代器会抛出异样。Enumerator自身的实现是没有fast-fail设计的，但他继承了Iteractor接口之后，就有了fast-fail。看一下源码：
public T next() { // 这里在Enumerator的根底上，减少了fast-fail if (Hashtable.this.modCount != expectedModCount) throw new ConcurrentModificationException(); // nextElement()是Enumeration的接口办法 return nextElement();}private void addEntry(int hash, K key, V value, int index) { ... // 在增加数据之后，会扭转modCount的值 modCount++;}所以，Hashtable自身的设计是有fastfail的，但如果应用的Enumerator，则享受不到这个设计了。
哈希算法
Hashtable的哈希算法非常简单粗犷，如下代码
hash = key.hashCode();index = (hash & 0x7FFFFFFF) % tab.length;获取key的hashcode，通过间接对数组长度求余来获取下标。这里还有一步是hash & 0x7FFFFFFF，目标是把最高位变成0，把hashcode变成一个非正数。为了使得hash能够散布更加平均，Hashtable默认管制数组的长度为一个素数：初始值为11，每次扩容为原来的两倍+1 。
抵触解决
Hashtable应用的是链表法，也称为拉链法。发生冲突之后会转换为链表。HashMap在jdk1.8之后减少了红黑树，所以在激烈抵触的状况下，Hashtable的性能降落会比HashMap显著十分多。
Hashtable的装载因子与HashMap统一，默认都是0.75，且倡议非非凡状况不要进行批改。
扩容计划
Hashtable的扩容计划也非常简单粗犷，新建一个长度为原来的两倍+1长度的数组，遍历所有的旧数组的数据，从新hash插入新的数组。他的源码非常简单，有趣味能够看一下：
protected void rehash() { int oldCapacity = table.length; Entry<?,?>[] oldMap = table; // 设置数组长度为原来的2倍+1 int newCapacity = (oldCapacity << 1) + 1; if (newCapacity - MAX_ARRAY_SIZE > 0) { if (oldCapacity == MAX_ARRAY_SIZE) // 如果长度达到最大值，则间接返回 return; // 超过最大值设置长度为最大 newCapacity = MAX_ARRAY_SIZE; } // 新建数组 Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; // modcount++，示意产生结构性扭转 modCount++; // 初始化装载因子，扭转table援用 threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); table = newMap; // 遍历所有的数据，从新hash后插入新的数组，这里应用的是头插法 for (int i = oldCapacity ; i-- > 0 ;) { for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) { Entry<K,V> e = old; old = old.next; int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = (Entry<K,V>)newMap[index]; newMap[index] = e; } }}线程平安
Hashtable和HashMap最大的不同就是线程平安了。jdk1.1的第一批汇合框架都被设计为线程平安，但伎俩都十分粗犷：间接给所有办法上锁 。但咱们晓得，锁是一个十分重量级的操作，会重大影响性能。Hashtable间接对整个对象上锁的毛病有：
- 同一时间只能有一个线程在读或者写，并发效率极低
- 频繁上锁进行零碎调用，重大影响性能
所以尽管Hashtable实现了肯定水平上的线程平安，然而却付出了十分大的性能代价。这也是为什么在jdk1.2他们马上就被淘汰了。
不容许空键值
容许空键值这个设计无利也有弊，在ConcurrentHashMap中也禁止插入空键值，但HashMap是容许的。容许value空值会导致get办法返回null时有两种状况：
- 找不到对应的key
- 找到了然而value为null；
当get办法返回null时无奈判断是哪种状况，在并发环境下containsKey办法已不再牢靠，须要返回null来示意查问不到数据。容许key空值须要额定的逻辑解决，占用了数组空间，且并没有多大的实用价值。HashMap反对键和值为null，但基于以上起因，ConcurrentHashMap是不反对空键值。
小结
总体来说，Hashtable属于旧版本的汇合框架，他的设计曾经落后了，官网更加举荐应用HashMap；而Hashtable线程平安的个性的同时，也带来了极大的性能代价，更加举荐应用ConcurrentHashMap来代替Hashtable。
SynchronizeMap
SynchronizeMap这个汇合类可能并不太熟悉，他是Collections.synchronizeMap()办法返回的对象，如下：
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) { return new SynchronizedMap<>(m);}SynchronizeMap的作用是保障了线程平安，然而他的办法和Hashtable统一，也是简略粗犷，间接加锁，如下图：
这里的mutex是什么呢？间接看到结构器：
final Object mutex; // Object on which to synchronizeSynchronizedMap(Map<K,V> m) { this.m = Objects.requireNonNull(m); // 默认为本对象 mutex = this;}SynchronizedMap(Map<K,V> m, Object mutex) { this.m = m; this.mutex = mutex;}能够看到默认锁的就是对象自身，成果和Hashtable其实是一样的。所以，个别状况下也是不举荐应用这个办法来保障线程平安。
ConcurrentHashMap
后面讲到的两个线程平安的Map汇合框架，因为性能低下而不被举荐应用。ConcurrentHashMap就是来解决这个问题的。对于ConcurrentHashMap的具体内容，在深刻解析ConcurrentHashMap：感触并发编程智慧 一文中曾经有了具体的介绍，这里简略介绍一下ConcurrentHashMap的思路。
ConcurrentHashMap并不是和Hashtable一样采纳间接对整个数组进行上锁，而是对数组上的一个节点上锁，这样如果并发拜访的不是同个节点，那么就无需期待开释锁。如下图：
不同线程之间的拜访不同的节点不相互烦扰，进步了并发拜访的性能。ConcurrentHashMap读取内容是不须要加锁的，所以实现了能够边写边读，多线程共读，进步了性能。
这是jdk1.8优化之后的设计构造，jdk1.7之前是分为多个小数组，锁的粒度比Hashtable稍小了一些。如下：
锁的是Segment，每个Segment对应一个数组。而jdk1.8之后锁的粒度进一步升高，性能也进一步提高了。
LinkedHashMap
HashMap是无奈记住插入程序的，在一些须要记住插入程序的场景下，HashMap就显得无能为力，所以LinkHashMap就应运而生。LinkedHashMap外部新建一个外部节点类LinkedHashMapEntry继承自HashMap的Node，减少了前后指针。每个插入的节点，都会应用前后指针分割起来，造成一个链表，这样就能够记住插入的程序，如下图：
图中的红色线示意双向链表的援用。遍历时从head登程能够依照插入程序遍历所有节点。
LinkedHashMap继承于HashMap，齐全是基于HashMap进行革新的，在HashMap中就能看到LinkedMap的身影，如下：
HashMap.java// Callbacks to allow LinkedHashMap post-actionsvoid afterNodeAccess(Node<K,V> p) { }void afterNodeInsertion(boolean evict) { }void afterNodeRemoval(Node<K,V> p) { }HashMap自身曾经预留了接口给LinkedHashMap重写。LinkedHashMap自身的put、remove、get等等办法都是间接应用HashMap的办法。
LinkedHashMap的益处就是记住Node的插入程序，当应用Iteractor遍历LinkedHashMap时，会依照Node的插入程序遍历，HashMap则是依照数组的前后程序进行遍历。
TreeMap
有没有发现后面两个汇合框架的命名都是 xxHashMap，而TreeMap并不是，起因就在于TreeMap并不是散列表，只是实现了散列表的性能。
HashMap的key排列是无序的，hash函数把每个key都随机散列到数组中，而如果想要放弃key有序，则能够应用TreeMap。TreeMap的继承构造如下：
他继承自Map体系，实现了Map的接口，同时还实现了NavigationMap接口，该接口拓展了十分多的不便查找key的接口，如最大的key、最小的key等。
TreeMap尽管领有映射表的性能，然而他底层并不是一个映射表，而是一个红黑树。他能够将key进行排序，但同时也失去了HashMap在常数工夫复杂度下找到数据的长处，均匀工夫复杂度是O(logN）。所以若不是有排序的需要，惯例状况下还是应用HashMap。
须要留神的是，TreeMap中的元素必须实现Comparable接口或者在TreeMap的构造函数中传入一个Comparator对象，他们之间才能够进行比拟大小。
TreeMap自身的应用和个性是比较简单的，外围的重点在于他的底层数据结构：红黑树。这是一个比较复杂的数据结构，限于篇幅，笔者会在另外的文章中详解红黑树。
最初
文章详解了Hashtable这个旧版的汇合框架，同时简略介绍了SynchronizeMap、ConcurrentHashMap、LinkedHashMap、TreeMap。这个类都在HashMap的根底性能上，拓展了一些新的个性，同时也带来一些性能上的代价。HashMap并没有称为性能的集大成者，而是把具体的个性散发到其余的Map实现类中，这样做得益处是，咱们不须要在单线程的环境下却要付出线程平安的代价。所以理解这些相干Map实现类的个性以及付出的性能代价，则是咱们学习的重点。
心愿文章对你有帮忙~
全文到此，原创不易，感觉有帮忙能够点赞珍藏评论关注转发。
笔者满腹经纶，有任何想法欢送评论区交换斧正。
如需转载请评论区或私信交换。另外欢迎光临笔者的集体博客：传送门