java中的集合

====================================================================================

1.8中的HashMap

HashMap 数组+单向链表+红黑树

特点：无序，线程不安全

为什么是无序的，往hashmap中添加元素时，是将key hash之后能均匀的分布在hash表中

key和value都可以是null

capacity 默认是16 （哈希表的长度）

loadFactor 默认0.75 （负荷因子）

threshold ＝容量*负荷因子（临界值）

size 实际存放的元素个数（map存放的元素个数）

哈希表长度

当传入容量时，传入5 ，设置为8 。即会设置capacity为大于传入值的最小的2的幂次方

扩容

当 size > capacity * loadFactor 时候，会扩容，新的容量为旧的值的2倍

本例中，capacity为4，loadFactor为0.75，threshold为3，当添加第4个元素时，会扩容。

链表转成红黑树，当桶的长度(桶可以理解为哈希表的某一行)大于8并且哈希表的长度大于64时候，会把该桶中节点转为红黑树

===============================================================================================

1.8中的ConcurrentHashMap

数组+单向链表+红黑树

特点：无序，线程安全

无序：和HashMap是同样的原因

以put元素为例子，根据put的元素的key计算出（两次，防止hash冲突）hash值，如果计算出来的要插入的哈希表的行的首节点不存在，则采用CAS无锁的方式添加。如果不是首节点，则采用synchronized对行首节点加锁synchronized后，再进行put操作。

get元素时不加锁，因为val属性用volatile修饰了，一个线程修改对另外的线程是可见的。

key和value都不能为null

1.8与1.7的变化是，1.8中删除了segments，加锁的粒度更细。加入了红黑树这种数据结构。效率更高。

================================================================================================

1.7中的ConcurrentHashMap

数组+单向链表

ConcurrentHashMap采用了分段锁的机制，默认的并发级别是16，即segments数组大小是16。对segments数组的操作是采用Unsafe类的，可以保证线程安全。由于Segment是继承了reentrantLock的，对Segment中的HashEntry进行操作时加的是重入锁可以保证线程安全。

================================================================================================

Hashtable 数组+单向链表

特点：无序，线程安全

无序：和HashMap是同样的原因

线程安全：对每个方法进行同步，synchronized

capacity 默认是11 （哈希表的长度）

loadFactor 默认0.75 （负荷因子）

threshold (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1)

count 存放的元素个数

key和value都不能为null

*********************************************************************************************************************************************

ConcurrentHashMap 和 Hashtable key和value都不能为null

value不能为null的原因

The main reason that nulls aren’t allowed in ConcurrentMaps
(ConcurrentHashMaps, ConcurrentSkipListMaps) is that
ambiguities that may be just barely tolerable in non-concurrent
maps can’t be accommodated. The main one is that if
map.get(key) returns null, you can’t detect whether the
key explicitly maps to null vs the key isn’t mapped.
In a non-concurrent map, you can check this via map.contains(key),
but in a concurrent one, the map might have changed between calls

无法分辨是key没找到的null还是有key值为null，这在多线程里面是模糊不清的，主要是在调用get方法时，这个值有可能被其他线程修改了。所以压根就不允许val值为null。key值也不能为null. 在put方法时，会先算出key的hash值，null就抛出异常。而hashmap就不存在上面的情况，并且假如key为null时，会将null的hash值设置为默认的0。

***************************************************************************************************************************************************

HashMap 的遍历， hashmap提供了迭代器三种遍历方式，遍历的方式是外层是哈表表的行，内层是哈希表的每一行中链表或者红黑树

=================================================================================================

LinkedHashMap 数组+双向链表+红黑树

特点：有序，线程不安全

LinkedHashMap 是HashMap的子类，继承HashMap，重写了父类的节点类型，每个节点持有当前节点的上一个节点的引用和下一个节点的引用。并增加了head和tail属性。

LinkedHashMap 与HashMap不同的地方是他要维持entry之间的顺序关系。

key和value都可以是null

有序：按照访问顺序或者按照元素插入的顺序，根据构造方法acccessOrder值来确定，默认是元素的插入顺序

插入顺序指的是：遍历顺序和放入的顺序是一样的

访问顺序指的是：最后访问的元素总是最后遍历出来

注意利用head和tail节点，可以实现LRU（最近最少使用淘汰）算法。LRU的核心思想是如果数据最近被访问过，那么将来被访问的几率也很高。

采用迭代器遍历时候用到了head头节点

==================================================================================================

TreeMap 红黑树

特点：有序，线程不安全

有序：一种情况是根据字典顺序排序（即key的compareTo方法，Integer,String都实现了Comparable接口），一种情况是根据传入的比较器进行排序

当向TreeMap中添加entry时，是根据插入entry的key 来比较排序的，根据比较的大小来决定将entry插入到哪个位置。

下面的例子中是按照key的字典顺序排序的，所以遍历时候，是从小到大的顺序

key不可以是null，要用到key的compare方法比较大小

==================================================================================================

ArrayList 动态数组实现

线程不安全

插入删除效率低，随机访问效率高

默认的长度为10

数组扩容的比例为1.5，即扩容后新数组长度是旧数组长度的1.5倍

=================================================================================================

LinkedList 双向链表实现

线程不安全

插入删除效率高，随机访问效率低

与ArrayList不同的是，他实现了queue接口，可以当成队列使用

采用双向链表比用单向链表的好处是：查找时，我们可以借用二分法的思路，这样双链表的效率可以提高一倍

缺点是：从存储结构来看，每个双链表的节点要比单链表的节点多一个指针，浪费空间了

=================================================================================================

CopyOnWriteArrayList 动态数组+重入锁

线程安全是由于是哟和了重去锁

与ArrayList的比较

    //线程不安全
    static List list= new  ArrayList<Integer>();
    public static void main(String[] args) throws InterruptedException {
        Runnable runnable = () -> {
            for (int i = 0; i < 10000; i++) {
                list.add(i);
            }    
        };
        Thread one = new Thread(runnable);
        Thread two = new Thread(runnable);
        one.start();
        two.start();
        one.join();
        two.join();
        System.out.println(list.size());
    }

//线程安全
    // static CopyOnWriteArrayList<Integer> list= new CopyOnWriteArrayList<Integer>();
     static List<Integer> list = Collections.synchronizedList(new  ArrayList<Integer>());
    //线程不安全
    //static List list= new  ArrayList<Integer>();
    public static void main(String[] args) throws InterruptedException {
        Runnable runnable = () -> {
            for (int i = 0; i < 10000; i++) {
                list.add(i);
            }    
        };
        Thread one = new Thread(runnable);
        Thread two = new Thread(runnable);
        one.start();
        two.start();
        one.join();
        two.join();
        System.out.println(list.size());
    }

================================================================================================

HashSet 对HashMap的封装

元素不能重复

线程不安全

无序

=================================================================================================

LinkedHashSet 继承了HashSet，对LinkedHashMap的封装

元素不能重复

线程不安全

有序（只能按照插入顺序遍历）

=================================================================================================