Map-Set-List

读源码有助于对程序的深入理解，原来一直横向拓宽技术栈，现在开始每天读一点源码。
这个Map很早就已经读完了，今天偷得浮生半日闲，来分享下。

首先Map、Set、List的区别

public static void main(String[] args) {
        /**
         * 线程安全 -- 性能依次提高
         */
        //同一时间只能有一个线程访问该容器，效率低
        Hashtable<String,String> hashTable = new Hashtable<>();
        //Hashtable的替代版本，同一时间只能有一个线程访问该容器的方法(方法锁)
        Map<String,String> synchronizedMap = Collections.synchronizedMap(new HashMap<>());
        //高性能版本，分段锁，线程安全
        ConcurrentMap<String,String> concurrentHashMap = new ConcurrentHashMap<>();

        /**
         * 非线程安全
         */
        //实现SortMap接口，默认是按键值的升序排序
        Map<String,String> treeMap = new TreeMap<>();
        //LinkedHashMap保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的。也可以在构造时带参数，按照应用次数排序。
        Map<String,String> linkedHashMap = new LinkedHashMap<>();
        //HashMap 是一个最常用的Map，它根据键的HashCode 值存储数据，根据键可以直接获取它的值，具有很快的访问速度。遍历时，取得数据的顺序是完全随机的。
        //HashMap最多只允许一条记录的键为Null；允许多条记录的值为 Null。
        //HashMap不支持线程的同步（即任一时刻可以有多个线程同时写HashMap），可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。
        //HashTable与 HashMap类似，它继承自Dictionary类。不同的是：它不允许记录的键或者值为空；它支持线程的同步（即任一时刻只有一个线程能写HashTable），因此也导致了 HashTable在写入时会比较慢。
        Map<String,String> hashMap = new HashMap<>();


        /**
         * List与Set
         * 简要说明
         * set --其中的值不允许重复，无序的数据结构。Set具有与Collection完全一样的接口，Set中的值必须唯一
         * list --其中的值允许重复，因为其为有序的数据结构
         * list和set是实现了collection接口的。
         */
        //为快速查找设计的Set。存入HashSet的对象必须定义hashCode()。
        Set<String> hashSet = new HashSet<>();
        //保存次序的Set, 底层为树结构。使用它可以从Set中提取有序的序列。
        Set<String> treeSet = new TreeSet<>();
        //LinkedHashSet : 具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)。
        //于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。
        Set<String> linkedHashSet = new LinkedHashSet<>();

        //由数组实现的List。允许对元素进行快速随机访问，但是向List中间插入与移除元素的速度很慢
        List<String> arrayList = new ArrayList<>();
        //对顺序访问进行了优化，向List中间插入与删除的开销并不大。随机访问则相对较慢。
        List<String> linkedList = new LinkedList<>();
    }

那么光这么简单了解一下，肯定是没有深度的，透过现象看本质。这些东西的本质到底是什么
List其实是一个Object[],
Set其实是包装了Map，HashSet => HashMap、TreeSet => TreeMap……
Map其实是相当于一个结构体，学过C语言的朋友肯定熟悉这个结构

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        //....
}

那我们都开始读源码了，肯定不能就了解这么一点就完事了。
继续读：

从这里开始就要分两个大概念（读者可以不跟着我的概念走，并不一定适合任何人，仅供参考）
两个概念是线程安全和非线程安全。

提到线程安全，那大家肯定记得有个通用的线程安全的方法
Collections.synchronizedxxx();
没错，这个方法隶属于java.util包下的方法。功能是返回一个线程安全的容器。
具体的实现方案是（以Collections.synchronizedMap为例）：

implements Map<K,V>, Serializable {
        private static final long serialVersionUID = 1978198479659022715L;

        private final Map<K,V> m;     // Backing Map
        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;
        }

        public int size() {
            synchronized (mutex) {return m.size();}
        }
        public boolean isEmpty() {
            synchronized (mutex) {return m.isEmpty();}
        }
        public boolean containsKey(Object key) {
            synchronized (mutex) {return m.containsKey(key);}
        }
        public boolean containsValue(Object value) {
            synchronized (mutex) {return m.containsValue(value);}
        }
        public V get(Object key) {
            synchronized (mutex) {return m.get(key);}
        }

        //....省略更多
}

可以看到这个方法，返回都在synchronized块里，提供了方法锁。这样的方法肯定要比table类锁要高效一点。那接下来我们细说非线程安全这一块。
继承Collection接口的只介绍一下ArrayList，其他的大同小异。
Set内部也是Map，所以我们快速的把目光放到Map上

public static void main(String[] args){
        List<String> list = new ArrayList<>();
        //添加数据
        for (int i =0; i < 10; i++){
            list.add("数据:" + i);
        }
        boolean isAddSuccess = list.add("0");
        String pos = list.get(0);
        int size = list.size();
        int position = list.indexOf("");
        boolean empty = list.isEmpty();
        boolean isRemoveSuccess = list.remove("");
        String remove = list.remove(0);

        //不建议使用，如频繁使用，则选择LinkedList
        list.add(10,"添加数据");

        //是否包含某条数据
        boolean contains = list.contains("0");

        //迭代器
        Iterator<String> iterator = list.iterator();
        //for循环其实是一个封装了迭代的语法块,所以我们遍历采用迭代器
        while (iterator.hasNext()){
            String str = iterator.next();
            System.out.println(str);
        }

        //带有操作功能的迭代器，add(),set(),remove...
        ListIterator<String> listIterator = list.listIterator();
        listIterator.previousIndex();


        //Spliterator是一个可分割迭代器(splitable iterator)
        Spliterator<String> spliterator1 = list.spliterator();

        //将要迭代的元素数量
        System.out.println("将要迭代的元素的数量" + spliterator1.estimateSize());

        //尝试分割一个List，返回靠前的数据段的迭代器，原迭代器从中间位置到最后位置。
        Spliterator<String> spliterator2 = spliterator1.trySplit();

        // 使用action消费下一个元素，指针向后移动一位
        spliterator1.tryAdvance(s -> System.out.println(s));

        System.out.println("切分迭代器遍历数据1");
        System.out.println("获取ExactSizeIfKnown" + spliterator1.getExactSizeIfKnown());
        spliterator1.forEachRemaining(str -> System.out.println(str));
        System.out.println("切分迭代器遍历数据2");
        System.out.println("获取ExactSizeIfKnown" + spliterator1.getExactSizeIfKnown());
        spliterator2.forEachRemaining(str -> System.out.println(str));


        //显示的调用这个函数，如果参数大于底层数组长度的1.5倍
        //那么这个数组的容量就会被扩容到这个参数值，如果参数小于低层数组长度的1.5倍
        //那么这个容量就会被扩容到低层数组长度的1.5倍（至少底层数组的1.5倍)
        ((ArrayList<String>) list).ensureCapacity(10);

        list.clear();
    }

那么本文的重头戏来了，我需要给这个重头戏加个粗

Map

没错，就是Map。
那么为什么说Map是重头戏呢，因为从实际生产中来看，Map确实用的很多，从源码角度看，Map有太多值得我们学习的地方。

前文已经简单介绍过Map了，我们先来回顾一下

//HashMap 是一个最常用的Map，它根据键的HashCode 值存储数据，根据键可以直接获取它的值，具有很快的访问速度。遍历时，取得数据的顺序是完全随机的。
//HashMap最多只允许一条记录的键为Null；允许多条记录的值为 Null。
//HashMap不支持线程的同步（即任一时刻可以有多个线程同时写HashMap），可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。
//HashTable与 HashMap类似，它继承自Dictionary类。不同的是：它不允许记录的键或者值为空；它支持线程的同步（即任一时刻只有一个线程能写HashTable），因此也导致了 HashTable在写入时会比较慢。

HashMap的底层采用类似C语言结构体一样的结构，定义了一个Node。而一个HashMap里包含很多个Node数组，我们称之为桶，那么HashMap既然是Hash，肯定会有Hash冲突的情况，我们看下HashMap怎么解决的冲突问题

/**
     * HashMap 内部有
     *  final int hash;     V value;
     *  final K key;        Node<K,V> next;
     *
     *  可以看到 HashMap 内部存储使用了一个 Node 数组(默认大小是16)，相当于一个链表
     *  所有根据hash值计算的 bucket 一样的key会存储到同一个链表里（冲突）
     *  当数据庞大时会影响效率，所以HashMap有自动扩容机制
     *  计算方法为（默认情况下数组大小为16，loadFactor为0.75）
     *  当size > 16 * 0.75 时，size = 16 * 2
     *  扩容会重新计算元素的位置，目的是让每个node链表降低深度，以达到高效
     *
     */

那么我上面说过分为线程安全与线程不安全，为什么说Map线程不安全呢？

/**
     *  原因有二：
     *  - 假设两个线程同时put的key发生碰撞，那么根据HashMap实现，两个key会被添加到同一位置，其中一个线程的数据会被覆盖
     *  - 多线程同时监测到需要扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组会赋给 table
     *  也就是说其他线程的都会丢失，并且各自线程 put 的数据也丢失。
     *
     *  《Java并发编程艺术》中说
     *  > HashMap 在并发执行 put 操作时会引起死循环，导致 CPU 利用率接近100%。因为多线程会导致 HashMap 的 Node 链表形成环形数据结构，
     *  > 一旦形成环形数据结构，Node 的 next 节点永远不为空，就会在获取 Node 时产生死循环。
     *  put并不会导致以上问题，死循环发生在扩容阶段
     */

线程安全的部分：
List没什么好说的，两个方案，一个是使用synchronized关键字，另一个是Collections.synchronizedList()。

那么set底层同样采用Map来实现，我们知道ConcurrentHashMap是线程安全中最快的方案（后续详解），但那需要我们重写一个ConcurrentHashSet类，比较麻烦。
通过百度一下，知道Google家的Guava已经帮我们实现了一个ConcurrentHashSet
使用方法大概是这样的：Set<String> s = Sets.newConcurrentHashSet();

Map的线程安全方案有三种，Hashtable,Collections.synchronizedMap,ConcurrentHashMap。

可以说很丰富了，但究竟我们该用哪个？
首先Hashtable可以说是完全可以不用看。速度很慢
Collections.synchronizedMap可以接受所有种类的Map，还有Collections.synchronizedMap是方法锁，ConcurrentHashMap分段锁机制，Java6吧提供这个类，而java8目前使用CAS算法更高效了。
从效率上讲，肯定是ConcurrentHashMap要更高效，但如果你对Map有特殊要求，比如TreeMap，那就要使用Collections.synchronizedMap了。

什么？不信？？
好吧，我这边有个测试类，运行一下看看～

/**
 * Test started for: class java.util.Hashtable
 * 2500K entried added/retrieved in 1632 ms
 * 2500K entried added/retrieved in 1722 ms
 * 2500K entried added/retrieved in 2129 ms
 * 2500K entried added/retrieved in 2061 ms
 * 2500K entried added/retrieved in 2058 ms
 * For class java.util.Hashtable the average time is 1920 ms
 *
 * Test started for: class java.util.Collections$SynchronizedMap
 * 2500K entried added/retrieved in 2677 ms
 * 2500K entried added/retrieved in 1944 ms
 * 2500K entried added/retrieved in 2019 ms
 * 2500K entried added/retrieved in 1964 ms
 * 2500K entried added/retrieved in 1972 ms
 * For class java.util.Collections$SynchronizedMap the average time is 2115 ms
 *
 * Test started for: class java.util.concurrent.ConcurrentHashMap
 * 2500K entried added/retrieved in 752 ms
 * 2500K entried added/retrieved in 454 ms
 * 2500K entried added/retrieved in 1190 ms
 * 2500K entried added/retrieved in 484 ms
 * 2500K entried added/retrieved in 473 ms
 * For class java.util.concurrent.ConcurrentHashMap the average time is 670 ms
 */

可以看到的确是ConcurrentHashMap的平均时间仅为670，另外两个结果都远超ConcurrentHashMap不只一倍。大家可以自己运行下看看，结果根据电脑配置上下有波动，但ConcurrentHashMap肯定是最快的（测试案例在本文结尾的GitHub链接里有）。

简单来看目前大概就是这么多了，水平有限，更深层次的东西我怕说不明白。

GitHub

Map-Set-List

Map

Eddie Lee