关于java:HashMap相关类HashtableLinkHashMapTreeMap

前言

很快乐遇见你~

在 深刻分析 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 时有两种状况：

1. 找不到对应的 key
2. 找到了然而 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 synchronize
SynchronizedMap(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-actions
void 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 实现类的个性以及付出的性能代价，则是咱们学习的重点。

心愿文章对你有帮忙~

全文到此，原创不易，感觉有帮忙能够点赞珍藏评论关注转发。
笔者满腹经纶，有任何想法欢送评论区交换斧正。
如需转载请评论区或私信交换。

另外欢迎光临笔者的集体博客：传送门