Java集合框架————Map集合（2）Hashtable子类；ConcurrentHashMap子类

1.Hashtable子类

JDK1.0提供有三大主要类：Vector、Enumeration、Hashtable。Hashtable是最早实现这种二元偶对象数据结构，后期的设计也让其与Vector一样多实现了Map接口而已。

范例：观察Hashtable

public class HashtableDemo {

    public static class TestDemo {
        public static void main(String[] args) {
            Map<Integer,String> map = new Hashtable<>() ;
            map.put(1,"hello") ;
// key重复
            map.put(1,"Hello") ;
            map.put(3,"Bad") ;
            map.put(2,"man") ;
            System.out.println(map);
        }
    }
}

以后使用的时候多考虑HashMap。

2. ConcurrentHashMap子类

为什么需要 ConcurrentHashMap？

Hashtable 本身比较低效，因为它的实现基本就是将 put、get、size 等各种方法加上“synchronized”。简单来说，这就导致了所有并发操作都要竞争同一把锁，一个线程在进行同步操作时，其他线程只能等待，大大降低了并发操
作的效率。

那么能不能利用 Collections 提供的同步包装器来解决问题呢？
看看下面的代码片段，我们发现同步包装器只是利用输入 Map 构造了另一个同步版本，所有操作虽然不再声明成为 synchronized 方法，但是还是利用了“this”作为互斥的 mutex，没有真正意义上的改进!

ConcurrentHashMap 分析

ConcurrentHashMap 的设计实现其实一直在演化，比如在 Java 8 中就发生了非常大的变化（Java 7 其实也有不少更新），所以，这里将比较分析结构、实现机制等方面，对比不同版本的主要区别。

早期 ConcurrentHashMap，其实现是基于：

• 分离锁，也就是将内部进行分段（Segment），里面则是HashEntry 的数组，和 HashMap类似，哈希相同的条目也是以链表形式存放。
• HashEntry 内部使用 volatile 的 value 字段来保证可见性，也利用了不可变对象的机制以改进利用Unsafe 提供的底层能力，比如 volatile access，去直接完成部分操作，以最优化性能，毕竟 Unsafe 中的很多操作都是 JVM intrinsic 优化过的。

可以参考下面这个早期 ConcurrentHashMap 内部结构的示意图，其核心是利用分段设计，在进行并发操作的时候，只需要锁定相应段，这样就有效避免了类似 Hashtable 整体同步的问题，大大提高了性能。

在构造的时候，Segment 的数量由所谓的 concurrency Level 决定，默认是 16，也可以在相应构造函数直接指定。注意，Java 需要它是 2 的幂数值，如果输入是类似 15 这种非幂值，会被自动调整到 16 之类 2 的幂数值。

• ConcurrentHashMap 会获取再入锁，以保证数据一致性，Segment 本身就是基于ReentrantLock 的扩展实现，所以，在并发修改期间，相应 Segment 是被锁定的。
• 在最初阶段，进行重复性的扫描，以确定相应 key 值是否已经在数组里面，进而决定是更新还是放置操作。重复扫描、检测冲突是ConcurrentHashMap 的常见技巧。
• 在 ConcurrentHashMap中扩容同样存在。不过有一个明显区别，就是它进行的不是整体的扩容，而是单独对 Segment 进行扩容。

另外一个 Map 的 size 方法同样需要关注，它的实现涉及分离锁的一个副作用。
试想，如果不进行同步，简单的计算所有 Segment 的总值，可能会因为并发 put，导致结果不准确，但是直接锁定所有 Segment 进行计算，就会变得非常昂贵。其实，分离锁也限制了 Map的初始化等操作。
所以，ConcurrentHashMap 的实现是通过重试机制（RETRIES_BEFORE_LOCK，指定重试次数 2），来试图获得可靠值。如果没有监控到发生变化（通过对比 Segment.modCount），就直接返回，否则获取锁进行操作。

下面来对比一下，在 Java 8 和之后的版本中，ConcurrentHashMap 发生了哪些变化呢？

• 总体结构上，它的内部存储变得和HashMap 结构非常相似，同样是大的桶（bucket）数组，然后内部也是一个个所谓的链表结构（bin），同步的粒度要更细致一些。
• 其内部仍然有 Segment 定义，但仅仅是为了保证序列化时的兼容性而已，不再有任何结构上的用处。
• 因为不再使用 Segment，初始化操作大大简化，修改为 lazy-load 形式，这样可以有效避免初始开销，解决了老版本很多人抱怨的这一点。
• 数据存储利用 volatile 来保证可见性。
• 使用 CAS 等操作，在特定场景进行无锁并发操作。
• 使用 Unsafe、LongAdder 之类底层手段，进行极端情况的优化。