Java集合总结

总结图片

一：List

1. Java ArrayList源码学习
2. Java LinkedList源码学习
3. Java Vector源码学习

二：Queue

1. Java ArrayDeque源码学习
2. Java PriorityQueue源码学习

三：Set

基于相应的Map实现 Set<E> = Map<E,Object>, final Object PRESENT = new Object();

四：Map

1. HashMap：它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
   Java HashMap源码学习

2. Hashtable：Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

3. LinkedHashMap：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。
   默认构造函数是只记录插入顺序

    LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
    map.put("one", 1);
    map.put("two", 2);
    map.put("three", 3);
    map.put("two", 3);
    //[one=1, two=3, three=3]
   
    记录访问顺序，每次访问node都会将其添加到链表的尾部；
    遍历时从头部开始遍历；
    LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, (float) 0.75, true);
    map.put("one", 1);
    map.put("two", 2);
    map.put("three", 3);
    map.get("two");
    // [one=1, three=3, two=2]
   

4. TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

5. ConcurrentHashMap

   • JDK1.7
     Segment + HashEntry；每个Segment继承了ReentrantLock，自带锁功能；
     size实现：因为ConcurrentHashMap是可以并发插入数据的，所以在准确计算元素时存在一定的难度，一般的思路是统计每个Segment对象中的元素个数，然后进行累加，但是这种方式计算出来的结果并不一样的准确的，因为在计算后面几个Segment的元素个数时，已经计算过的Segment同时可能有数据的插入或则删除。
     

   • JDK1.8
     1.8中放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现； 每个Node结点为空时CAS式添加，链表/红黑树添加节点需要Synchronized内置锁；
     size实现：1.8中使用一个volatile类型的变量baseCount记录元素的个数，当插入新数据或则删除数据时，会通过addCount()方法更新baseCount；
     

   参考：谈谈ConcurrentHashMap1.7和1.8的不同实现

@梦工厂2018.3.26