java容器精讲（Java容器基本说全了），带源码讲解，集合，同步类容器，并发容器，队列

2022-08-02 10:32:53

集合 & 容器

容器：在内存中存储数据的结构，例如数组、集合，就是采用各种数据结构存储数据的内存结构

集合：和数组不同，数组存储同一种类型数据，有长度限制。大部分集合没有长度限制，比如LinkedList，链表数据结构理论上没有长度限制，除非人为限制或者占满内存。

集合特点：只能存放引用数据类型数据，不能存放基本数据类型，如果我们存放基本数据类型，会自动装箱对应包装类。

存在意义：不同的业务场景下，对数据的存储有不同要求，为了应付各种场景，所以提供很多种类的容器

源码（码云）：`https://gitee.com/yin_zhipeng/to_study_the_collection.git`

看一下最基本的集合

完整的类图：文件位置simple_collection/uml/collection.puml

可以发现重复继承了，比如ArrayList extends AbstractList implements List，AbstractList implement List。ArrayList extends AbstractList就不用实现List了，因为AbstractList已经实现

JDK源码写Collection的人也自己承认了这个失误，但是在后来的版本，并没有改，因为他们觉得没必要，也确实没必要

简易的：文件位置simple_collection/uml/collection-simple.puml

`声明`：看源码时经常看见这个变量modCount，就是标记容器被操作的次数的，在这里统一说一下，否则遇见一次说一次，想一头撞死

文章目录

一、Collection接口
二、List接口
三、LinkedList实现类
四、Set接口
五、Map接口
六、同步类容器
- 1. Collections工具类转换
- 2. Collections源码(JDK1.8)
七、并发类容器
八、队列

一、`Collection接口`

Collectiono 是*接口，我们对其常用Api进行介绍

接口不能new对象，所以我们需要使用其子类，ArrayList，LinkedList，HashSet，TreeSet，

选个简单的，我们使用ArrayList

1. `常用Api解析`

描述	API
添加单个元素	`add(E e)`
添加一个集合	`addAll(Collection<? extends E> c)`
清除集合	`clear()`
移除指定元素	`remove(Object o)`
迭代器	`iterator()`
集合元素个数	`size()`
判断指定元素是否在集合中	`contains(Object o)`
比较两个集合的元素是否相等	`equals(Object o)`
集合是否为空	`isEmpty()`

测试API：simple_collection/CollectionAPITest.java

import java.util.*;

public class CollectionAPITest {

    public static void main(String[] args) {
        //Collection是接口，使用需要实现类
        Collection col = new ArrayList();
        //add()添加一个元素，添加基本数据类型，会自动装箱，int--->Integer
        col.add(1);
        col.add(2);
        System.out.println("使用add方法添加1和2："+col);
        //addALl()添加一个集合的所有元素
        List<Integer> integers = Arrays.asList(new Integer[]{3, 4, 5, 6, 7, 8});
        col.addAll(integers);
        System.out.println("使用addAll方法添加{3, 4, 5, 6, 7, 8}:"+col);
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        //remove()方法移除指定元素
        System.out.println("使用remove()方法移除元素1："+col.remove(1)+"(true成功/false失败)移除后集合"+col);
        System.out.println("再次使用remove()方法移除元素1："+col.remove(1)+"(true成功/false失败)移除后集合"+col);
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        //clear()方法清除集合
        col.clear();
        System.out.println("使用clear方法清除集合"+col);
        //isEmpty()方法查看集合是否为空
        System.out.println("使用isEmpty方法查看集合是否为空"+col.isEmpty());
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        //equals()方法比较两个集合是否相等
        ArrayList<Object> objects = new ArrayList<>();
        System.out.println("集合一："+col+"集合二："+objects+"使用equals()比较两个集合元素是否相等"+col.equals(objects));
        objects.add(1);
        System.out.println("集合一："+col+"集合二："+objects+"使用equals()比较两个集合元素是否相等"+col.equals(objects));
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        //contains()方法判断集合是否包含指定元素
        System.out.println("集合："+objects+"使用contains()方法判断集合是否包含1这个元素"+objects.contains(1));
        System.out.println("集合："+objects+"使用contains()方法判断集合是否包含2这个元素"+objects.contains(2));
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        //size()方法获取集合长度
        System.out.println("集合："+col+"使用size()方法获取集合长度"+col.size());
        System.out.println("集合："+objects+"使用size()方法获取集合长度"+objects.size());
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        //使用iterator()迭代器遍历集合
        col.addAll( Arrays.asList(new Integer[]{3, 4, 5, 6, 7, 8}));
        System.out.println("使用iterator()遍历集合"+col);

        Iterator iterator = col.iterator();//获取Iterator对象
        int i = 1;
        while(iterator.hasNext()){//Iterator.hasNext()方法，判断是否有个下一个可迭代对象
            Object next = iterator.next();//返回当前元素，并指针后移，指针指向下一个元素，若没有，下一次hasNext方法会做处理
            System.out.println("第"+i+"个元素："+next);
            i++;
        }

    }
}

2. `Iterator接口`

首先Collection extends Iterable，而Iterable接口中定义了Iterator iterator();，返回Iterator接口对象,我们操作迭代的方法，都在Iterator接口

接口是不可用的，如果想用需要实现类，我们从ArrayList源码中，可以看到，实现类就是Itr类,Itr类是内部类

3. `ArrayList的iterator()方法源码(JDK1.8)`

ArrayList的iterator迭代器解析

iterator()：我们发现iterator()方法只是new了一个自己的内部类Itr，Itr中有当前元素指针cursor，当前元素的上一个元素指针lastRet

hasNext()方法:只是判断当前指针，是否!=size，如果不等于，说明还有元素可以遍历，返回true

next()方法: 返回当前元素，并指针后移，指针指向下一个元素。源码中变量i记录当前元素指针，如果i>=size,表示下标越界（抛异常），否则数据集合，然后再次判断，i是否在数据集合的下标范围内，如果不在，报异常。都没问题，cursor后移，lastRet = i（记录当前元素，当前元素是下一次迭代元素的上一个），然后返回lastRet（i）指向的元素

4. `集合之间如何比较`

1. Comparable 和 Comparator

Comparabel接口（内部比较器），java.lang包下，有个一个compareTo(Obj)方法来排序，比较Obj和this（内部的自己）谁大

Comparator接口(外部比较器)，java.util包下，有一个compare(Obj1,Obj2)方法来排序，比较Obj1和Obj2谁大

一般对集合自定义排序，需要重写compareTo或compare方法，当我们需要对集合实现两种排序方式，比如一个song对象中歌名和歌手名分别采用一种排序方式的话，我们可以重写compareTo方法和使用自制的Comparator方法，或者两个Comparator来实现歌名排序和歌星名排序，第二种代表我们只能使用两个参数版的Collections.sort()

假设num1 = 10;num2=20;如何比较他俩谁大呢？num1-num2>0,表示num1>num2。如果=0，表示他俩一样大，如果<0表示num2比num1大

那么上面两个数比较当然好比较，但是换成对象呢？该如何比较两个对象谁大谁小呢？这就需要你用这两个接口为对象定制比较规则（同样，返回值>0,表示num1>num2…）

下面分别介绍Comparable和Comparator的用法，以及如何对集合正确排序

Comparable需要让对象实现Comparable接口，集合排序时Collections.sort(list);会自动调用对象重写的compareTo()

Comparator直接用匿名内部类实现即可，将两个需要排序的对象给它，集合排序，Collections.sort(list,new Comparator())即可

Comparabel接口（内部比较器），实现更简单， Comparator接口(外部比较器)更灵活

import java.util.*;

public class Test implements Comparable<Test>{
    private Integer age;

    public Test(Integer age) {
        this.age = age;
    }

    /**
     * 返回一个int值，正数表示自己（this）比o大,0表示this=o2，负数表示this小于o2
     */
    @Override
    public int compareTo(Test o) {
        //根据年龄决定谁大
        return this.age-o.age;
    }

    @Override
    public String toString() {
        return "Test{" +
                "age=" + age +
                '}';
    }

    public static void main(String[] args) {
        Test test = new Test(1);
        Test test1 = new Test(2);
        ArrayList<Test> tests = new ArrayList<>();
        tests.add(test1);
        tests.add(test);
        System.out.println("list集合排序前"+Arrays.toString(tests.toArray())+"\n\n");
        System.out.println("==========Comparable排序===========");

        int i = test.compareTo(test1);
        System.out.println("Comparable：test和test1谁大（正数表示test大，0表示相等，负数表示test1大）"+i);
        Collections.sort(tests);
        System.out.println("list集合排序后"+Arrays.toString(tests.toArray())+"\n\n");


        System.out.println("==========Comparator排序===========");
        Comparator<Test> comparator = new Comparator<Test>() {

            /**
             * 返回一个int值，正数表示o2>o1,0表示o1=o2，负数表示o2小于o1
             */
            @Override
            public int compare(Test o1, Test o2) {
                //根据年龄决定谁大
                return o2.age-o1.age;
            }
        };
        int compare = comparator.compare(test, test1);
        System.out.println("Comparator：test和test1谁大（正数表示test1大，0表示相等，负数表示test大）"+compare);
        Collections.sort(tests, new Comparator<Test>() {
            /**
             * 返回一个int值，正数表示o2>o1,0表示o1=o2，负数表示o2小于o1
             */
            @Override
            public int compare(Test o1, Test o2) {
                return o2.age-o1.age;
            }
        });
        System.out.println("list集合排序后"+Arrays.toString(tests.toArray()));
    }
}

二、`List接口`

List也是一个接口，继承于Collection，Collection有的他都有，所以我们介绍它特有的常用Api进行介绍

接口不能new对象，所以我们需要使用其子类，ArrayList，LinkedList

选个简单的，我们使用ArrayList

1. `常用Api解析`

listIterator()和listInterator(int index)等方法，放在后面统一介绍，放在这里有的突兀

描述	API
`添加`单个元素到指定下标	`add(int index,E e)`
`设置(替换)`单个元素到指定下标	`set(int index,E e)`
获取指定下标元素	`get(int index)`
移除指定下标元素	`remove(int index)`

测试API：simple_collection/ListApiTest.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ListApiTest {
    public static void main(String[] args) {
        //List是接口，使用需要子类
        List list = new ArrayList();
        list.addAll(Arrays.asList(new Integer[]{4,7,8,-1}));
        System.out.println("List init ====>>> "+list);
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        //add(int index,E e)添加单个元素到指定下标
        list.add(1,5);
        System.out.println("List add(1,5):在下标为1的位置添加元素5"+list);
        //set(int index,E e)设置单个元素到指定下标
        list.set(1, 6);
        System.out.println("List set(1,6):在下标为1的位置设置元素6"+list);
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        //get(int index)获取指定下标元素
        System.out.println("List get(1):获取下标为1的元素："+list.get(1));
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        //remove(int index)移除指定下标元素
        list.remove(1);
        System.out.println("List remove(1):移除下标为1的元素："+list);
    }
}

2. `ArrayList源码(JDK1.8)`

ArrayList优缺点

底层基于数组，查询，修改效率高。删除，增加效率低

数据可重复，因为底层数组是Object类型，可以存储任意类型数据

简单说一下JDK1.7版本的细节，具体源码看JDK1.8的

ArrayList维护的是一个Object类型数组elementData，和size变量

初始大小10（默认）

add方法中，没有System.arraycopy(elementData, index, elementData, index + 1,size - index);这行代码

JDK1.8 ArrayList源码

和1.7一样，维护Object类型数组elementData，和size变量

默认大小依然是10，但是不是初始直接赋值，而是先指向一个空数组{}，elementData默认指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA

add()方法，会进行扩容数组（因为初始化数组长度为0（size = 0），所以必定会进行扩容操作）

判断是否需要扩容，如果是默认创建ArrayList，就确保扩容数值大于等于DEFAULT_CAPACITY（10）,不是直接判断是否需要扩容，如果数组没满，不需要扩容

扩容操作（每次原数组1.5倍）

默认大小为10

3. `Vector源码(JDK1.8)`

一个被淘汰的容器，但是面试常问

ArrayList 底层扩容长度为原数组1.5倍，线程不安全效率高

Vector 底层扩容长度为原数组2倍，线程安全效率低

底层维护Object类型数组elementData和int变量elementCount表示元素个数

默认长度为10

add()方法，加锁，方法内扩容

扩容方法（每次扩容为原数组2倍）

4. `iterator()方法的Itr迭代器并发修改异常`

ArrayList是线程不安全的，使用迭代器的时候，不可以同时对集合进行其它操作，比如用迭代器添加数据,一个指针迭代，另一个指针操作集合，就会报错

那么我们可以让一个人做这件事，解决并发修改异常，使用ListIterator接口

5. `ListIterator接口，ArrayList的ListItr实现类`

ListIterator接口继承于Iterator接口，同时ArrayList也使用内部类ListItr实现了此接口,ListItr内部类还继承了Itr内部类

遍历和添加，都使用ListIterator对象，不报并发修改异常

遍历时还可以判断上一个元素，以完成逆向遍历，前提是，当前ListIterator指针已经在靠后的位置（不等于0）

源码如下

三、`LinkedList实现类`

1. `常用Api解析`

描述	API
插入指定元素到列表开头	`addFirst(E e)`
插入指定元素到列表结尾	`addLast(E e)`
获取但不移除此列表的头	`E element()`
获取但不移除此列表的头	`E peek()`
获取但不移除此列表的第一个元素，列表为空，返回null	`E peekFirst()`
获取但不移除此列表的最后一个元素，列表为空，返回null	`E peekLast()`
返回此列表第一个元素	`getFirst()`
返回此列表最后一个元素	`getLast()`
返回此列表首次出现的指定元素的索引，无元素返回-1	`indexOf(Object o)`
返回此列表最后出现的指定元素的索引，无元素返回-1	`lastIndexOf(Object o)`
获取并移除此列表的头	`poll()`
获取并移除此列表的第一个元素，列表为空，返回null	`pollFirst()`
获取并移除此列表的最后一个元素，列表为空，返回null	`pollLast()`
从此列表所表示的堆栈处弹出一个元素	`pop()`
将元素推入此列表所表示的堆栈	`push(E e)`
将指定元素添加到此列表的末尾	`offer(E e)`
将指定元素插入到此列表的开头	`offerFirst(E e)`
将指定元素插入到此列表的末尾	`offerLast(E e)`
移除并返回此列表的第一个元素,列表为空，报错	`E removeFirst()`
移除并返回此列表的最后一个元素	`E removeLast()`

上面很多API看似功能一样，重复，其实细节是不一样的，为了适应各种场景

比如pollFirst()和removeFirst(),一个列表为空时，继续移除元素，会返回空列表，一个会直接报错。removeFirst从JDK1.0就有，直接抛异常，系统没有健壮性，pollFirst在JDK1.6加入，提高系统健壮性，不随便抛异常

测试API：simple_collection/LinkedListApiTest.java

import java.util.LinkedList;

public class LinkedListApiTest {
    public static void main(String[] args) {
        //创建LinkedList
        LinkedList linkedList = new LinkedList();
        //特有的添加方法
        System.out.println("addFirst()插入指定元素到列表开头");linkedList.addFirst("addFirst()");
        System.out.println("addLast()插入指定元素到列表结尾");linkedList.addLast("addLast()");
        System.out.println("push()入栈");linkedList.push("push()");
        System.out.println("offer()元素添加到末尾");linkedList.offer("offer()");
        System.out.println("offerFirst()元素插入到列表开头");linkedList.offerFirst("offerFirst()");
        System.out.println("offerLast()元素插入到列表末尾");linkedList.offerLast("offerLast()");
        linkedList.push("push()");//多添加一个用于测试lastIndexOf()
        System.out.println("添加元素完成："+linkedList);
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        //特有获取元素方法
        System.out.println("element():获取但不移除列表头"+linkedList.element());
        System.out.println("peek():获取但不移除列表头"+linkedList.peek());
        System.out.println("peekFirst():获取但不移除列表头,列表空，返回null："+linkedList.peekFirst());
        System.out.println("peekLast():获取但不移除列表尾,列表空，返回null："+linkedList.peekLast());
        System.out.println("getFirst():列表第一个元素"+linkedList.getFirst());
        System.out.println("getLast():列表最后一个元素"+linkedList.getLast());
        System.out.println("linkedList.indexOf(push()):获取列表第一个'push()'的下标"+linkedList.indexOf("push()"));
        System.out.println("lastIndexOf(push()):获取列表最后一个'push()'的下标"+linkedList.lastIndexOf("push()"));
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        //特有移除元素方法
        System.out.println("pop()，出栈弹出一个元素=="+linkedList.pop()+"==移除后列表："+linkedList);
        System.out.println("poll(),获取并移除此列表的头=="+linkedList.poll()+"==移除后列表："+linkedList);
        System.out.println("pollFirst(),获取并移除列表首元素，列表空，返回null：=="+linkedList.pollFirst()+"==移除后列表："+linkedList);
        System.out.println("pollLast(),获取并移除列表尾元素，列表空，返回null：=="+linkedList.pollLast()+"==移除后列表："+linkedList);
        System.out.println("removeFirst(),移除并返回此列表第一个元素=="+linkedList.removeFirst()+"==移除后列表："+linkedList);
        System.out.println("removeLast(),移除并返回此列表最后一个元素=="+linkedList.removeLast()+"==移除后列表："+linkedList);
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        //遍历
        System.out.println("遍历======");
        for(Iterator iterator =linkedList.iterator();iterator.hasNext();){
            System.out.println(iterator.next());
        }
    }
}

2. `两种迭代器使用方法比较`

//不推荐，iterator 用完，不会立即被回收
Iterator iterator = col.iterator();
while(iterator.hasNext()){
    System.out.println(iterator.next());
}
//更优，iterator 为局部变量，for循环结束，迭代器直接回收
for(Iterator iterator =linkedList.iterator();iterator.hasNext();){
    System.out.println(iterator.next());
}

3. `LinkedList源码(JDK1.8)`

LinkedList底层由双向链表实现，维护内部类Node< E >,代表链表单个节点，first，last分别代表首尾节点

添加首尾节点，底层全部都调用linkFirst和linkLast两个方法

linkFirst和linkLast，就是平常双链表数据结构插入结点代码，first或last先保存，然后指向要插入结点，刚保存的first或last，再成为新插入结点的后继或前驱，然后判断是否是首次插入结点，如果是首次，first和last指向同一个结点，如果不是，让刚保存的first或last成为新结点的后继或前驱（具体是成为前驱还是后继，看是插入到末尾还是首部）

根据索引查找

get(index)方法，首先考虑了程序健壮性，检查了索引，然后调用node(index)方法返回指定结点

node(int index)方法：size >>1 表示size缩小为原来的2倍，10就变5，首先判断用户要检索的index是在列表前半段，还是后半段，如果是前半段，就从first开始遍历查找，后半段就从last开始遍历查找

四、`Set接口`

Set接口继承于Collection接口，Collection有的他都有，特性如下

除去特殊的Set（后边会介绍），其它Set全都：元素唯一（不重复），无序（按照一定哈希算法选择元素放置位置,内存地址不挨着），存储元素位置固定但又不固定，我们获取元素时，和插入元素顺序会不一致（按照一定hash算法确定元素存储位置，存储元素）

底层使用Map实现（Hash表），HashSet底层维护HashMap，TreeSet底层维护TreeMap

TreeHashSet基本上可以实现自动帮你排序的效果，但这不重要，主要是调用Comparable 和 Comparator

`Set接口的API和List接口大致相同，但是少了和索引相关的API，Set中没有索引`，所以我们不介绍特有API

Set底层都是用Map实现，所以我们研究源码时，只看怎么用的Map，具体原理请看后面Map的源码

1. `HashSet实现类和源码(JDK1.8)`

基本特性测试:simple_collection/HashSetApiTest.java

import java.util.HashSet;
import java.util.Set;

public class SetApiTest {
    public static void main(String[] args) {
        Set set = new HashSet();
        //去重，根据Set特性，数据唯一
        set.add(1);set.add(1);set.add(1);set.add(1);set.add(1);set.add(1);
        System.out.println("向set集合中添加6个元素1，根据数据唯一特性，集合中将只有1个1："+set);
        //无序测试
        set.add("a");set.add("b");set.add(2);set.add(3);set.add(4);
        set.add(5);set.add(6);set.add(7);set.add("asdfsdf");set.add("asdasdffsdf");set.add("asdfasdfasdfsdf");
        System.out.println("Set集合无序测试，查看是否和插入顺序一至：" +set);
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        //add方法，添加元素成功，返回true，添加失败，返回false，表示重复了，集合中有了
        System.out.println("测试添加集合中没有的值，添加元素10："+set.add(10));
        System.out.println("测试添加集合中已经有值，添加元素1："+set.add(1));
    }
}

源码解析：看不懂就先往下看或者先看Map

HashSet,底层维护HashMap

添加方法add(),将要添加元素作为key，put到map中，value是PRESENT，指向一个空的Object对象（map中value可重复，所以可以一直添加同一个对象）

2. `LinkedHashSet实现类和源码(JDK1.8)`

LinkedHashSet 和 HashSet的区别

底层实现加了链表，数据存储有序了，按照输入顺序输出

虽然底层Map依然通过hash算法确定元素位置，但是LinkedHashSet中多出一个链表，专门按顺序记录这些元素在hash表的位置

底层依然使用Map，用的是LinkedHashMap

测试，发现有序了：simple_collection/LinkedHashSetTest.java

import java.util.LinkedHashSet;

public class LinkedHashSetTest {
    public static void main(String[] args) {
        LinkedHashSet set = new LinkedHashSet();
        //去重，根据Set特性，数据唯一
        set.add(1);set.add(1);set.add(1);set.add(1);set.add(1);set.add(1);
        System.out.println("向set集合中添加6个元素1，根据数据唯一特性，集合中将只有1个1："+set);
        //无序测试
        set.add("a");set.add("b");set.add(2);set.add(3);set.add(4);
        set.add(5);set.add(6);set.add(7);set.add("asdfsdf");set.add("asdasdffsdf");set.add("asdfasdfasdfsdf");
        System.out.println("Set集合无序测试，查看是否和插入顺序一至：" +set);
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        //add方法，添加元素成功，返回true，添加失败，返回false，表示重复了，集合中有了
        System.out.println("测试添加集合中没有的值，添加元素10："+set.add(10));
        System.out.println("测试添加集合中已经有值，添加元素1："+set.add(1));
    }
}

源码分析:看不懂先去看map

LinkedHashSet 继承 HashSet，创建对象调用的就是HashSet的构造方法

HashSet关于链表的构造方法，发现是创建了LinkedHashMap

也就是调用的方法都是调用LinkedHashMap中的，我们后面说

3. `TreeSet实现类和源码(JDK1.8)`

和HashSet基本一样，只是底层是用二叉树实现的（遍历方式为中序遍历），一样的不按插入顺序排序，一样的不允许重复，`但是会排序`:simple_collection/TreeSetTest.java

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet<Integer> set = new TreeSet();//使用默认比较器
        //去重，根据Set特性，数据唯一
        set.add(1);set.add(1);set.add(1);set.add(1);set.add(1);set.add(1);
        System.out.println("向set集合中添加6个元素1，根据数据唯一特性，集合中将只有1个1："+set);
        //无序测试
        set.add(9);set.add(13);set.add(7);set.add(16);set.add(17);set.add(15);

        System.out.println("TreeSet集合使用：内部比较器排序：" +set);
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        //add方法，添加元素成功，返回true，添加失败，返回false，表示重复了，集合中有了
        System.out.println("测试添加集合中没有的值，添加元素10："+set.add(10));
        System.out.println("测试添加集合中已经有值，添加元素1："+set.add(1));
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        
        TreeSet<Integer> integers = new TreeSet<>(new Comparator<Integer>() {//使用外部比较器
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        integers.add(9);integers.add(13);integers.add(7);integers.add(16);integers.add(17);integers.add(15);

        System.out.println("TreeSet集合使用：外部比较器排序：" +integers);
    }
}

源码：主要理解为什么可以排序

TreeSet底层维护TreeMap，可以自定义比较器

add()方法看看为什么可以自动排序：调用TreeMap的put方法

TreeMap的put()方法：可见，调用了compare()方法比较

compare方法：如果传入比较器，就用我们传入的，没传就用默认的内部比较器

HashMap是没有比较的

五、`Map接口`

Map是一个*接口，主要规定采用键值对的形式存储数据，多采用Hash表和二叉树两种数据结构实现，接口不能new对象，我们用HashMap介绍Map的Api

键(K:key)：数据映射的唯一标识，不可重复，相当于人的身份证号码，一人就一个

值(V:Value): 具体的数据，可以重复，就相当于人名，世界上有很多名字一样的人，比如"张伟"

1. `常用Api解析`

描述	API
从此映射中移除所有隐射关系	`clear()`
如果此映射包含指定键的映射关系，返回true	`boolean containsKey(Object key)`
如果此映射将一个或多个键映射到指定值，返回true	`boolean containsValue(Object value)`
返回此映射中包含的映射关系的Set视图	`Set<Map.Entry<K,V>> entrySet()`
比较指定的对象与此映射是否相等	`boolean equals(Object o)`
返回指定键所映射的值；如果此映射不包含该键的映射关系，返回null	`V get(Object key)`
返回此映射的哈希码值	`int hashCode()`
如果此映射未包含键-值映射关系，返回true	`boolean isEmpty()`
返回此映射包含的键的Set视图	`Set< K > keySet()`
将指定的值与此映射中的指定键关联（可选操作）	`V put(K key,V value)`
从指定映射中将所有映射关系复制到此映射中（可选操作）	`void putAll(Map<? extends K,? extends V> m)`
如果存在一个键的映射关系，则将其从此映射中移除（可选操作）	`V remove(Object key)`
返回此映射中的键-值映射关系数	`int size()`
返回此映射中包含的值的Collection视图	`Collection< V > values()`

测试API：simple_collection/MapApiTest.java

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class MapApiTest {
    public static void main(String[] args) {
        Map<String,Integer> map = new HashMap<>();
        System.out.println("测试一下对同一个key赋值，put()方法的返回值");
        System.out.println("put(\"one\", 3)返回值："+map.put("one", 3));
        System.out.println("put(\"one\", 2)返回值："+map.put("one", 2));
        System.out.println("put(\"one\", 1)返回值："+map.put("one", 1));
        System.out.println("对同一个key，one设置3个值，只会保留最后一个，一个键映射一个值，重复赋值会替换："+map);
        map.put("two",2);
        map.put("three",3);
        map.put("four",4);
        System.out.println("map集合初始化完成（会按照key的hash排序）："+map);
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        System.out.println("通过get('one')获取one对应的值："+map.get("one"));
        System.out.println("当前map的大小："+map.size());
        System.out.println("keySet()获取所有key，Set<K>对象："+map.keySet());
        System.out.println("values()获取所有映射值Collection对象："+map.values());
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        System.out.println("map1.equals(map2):判断两个map的映射关系，是否一致："+map.equals(map));
        System.out.println("isEmpty()判断集合是否为空："+map.isEmpty());
        System.out.println("map.containsKey(\"one\"):判断集合中是否包含key值one的映射："+map.containsKey("one"));
        System.out.println("map.containsValue(1):判断1这个值，是否和map中某个或某些key映射："+map.containsValue(1));
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));
        System.out.println("remove(\"one\")：删除指定key，one，返回它映射的值（key丢失，1这个值没有引用指向，也会被GC回收）："+map.remove("one"));
        System.out.println("remove(\"two\", 3):删除指定key-value对，不满足映射关系，不删除："+map.remove("two", 3));
        System.out.println("删除后map："+map);
        map.clear();
        System.out.println("map.clear()清空map："+map);
        System.out.println(Integer.toBinaryString(2)+" "+Integer.toBinaryString(-2)+" "+Integer.toHexString(-2>>>2)+" "+Integer.toBinaryString(-2>>>2));

        map.put("one", 1);map.put("two",2);map.put("three",3);map.put("four",4);



        System.out.print("配合keySet()方法遍历key值:===>>[");
        Set<String> keySet = map.keySet();
        for(String s:keySet){
            System.out.print(s+", ");
        }
        System.out.println("]");

        System.out.print("配合keySet()和get()方法遍历key和value:===>>{");
        for(String s:keySet){
            System.out.print(s+"="+map.get(s)+", ");
        }
        System.out.println("}");

        System.out.print("配合values()方法遍历value值:===>>[");
        Collection<Integer> values = map.values();
        for(Integer i : values){
            System.out.print(i+", ");
        }
        System.out.println("]");

        System.out.print("配合entrySet()方法，同时遍历key和vlaue值:===>>{");
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        for (Map.Entry<String, Integer> entry : entries) {
            System.out.print(entry.getKey()+"="+entry.getValue()+", ");
        }
        System.out.println("}");
    }
}

2. `HashMap源码(JDK1.8)`

HashMap底层是由哈希表数据结构实现（数组+链表+红黑树JDK1.8）

根据键值对（key-value）直接进行访问的数据结构，通过key映射value，让我们可以快速的通过key拿到对应value值。这个映射函数叫做散列函数，存放记录的数组叫做散列表

数组是散列表代表key，每个数组元素是一个链表代表value，所以一个key只能有一个，但是一个key可以映射多个value(因为value存在链表中)

散列表的大小必须是2的幂，为了让哈希后的结果更加均匀，如果不是2的幂次方，很可能会得到一些很极端的值，比如0或1，这让0或1这个位置的元素非常多，链表非常长（红黑树很大），2的幂，可以让元素hash的（存放）根分布平均

hash怎么算,一定要搞懂，否则后面源码看不懂

java提供hashCode()方法提供hash值，java中hash值都是int类型，4个字节表示，共32位

但为了减少碰撞，降低hash冲突的几率。右移16位异或可以同时保留高16位于低16位的特征.使得高十六位的特征与低十六位的特征进行了混合得到的新的数值中就高位与低位的信息都被保留了

异或运算能更好的保留各部分的特征.直接做&运算高十六位所代表的部分特征就可能被丢失,如果采用&运算计算出来的值会向1靠拢，采用|运算计算出来的值会向0靠拢

可以将hashcode高位和低位的值进行混合做异或运算，而且混合后，低位的信息中加入了高位的信息，这样高位的信息被变相的保留了下来

等于说计算下标时把hash的高16位也参与进来了，掺杂的元素多了，那么生成的hash值的随机性会增大，减少了hash碰撞。

hash不一样，但是下标算成一样的怎么办（哈希碰撞），一定要搞懂，否则后面源码看不懂

如果是key相同的，直接替换值

如果是key不同的，就添加在链表（7上8下，JDK1.7添加在链表前，JDK1.8添加到链表后面）

代码测试

        //获取key的hashCode值h，然后保存h无符号右位移16位的二进制i，将h ^ i 得到我们需要的hashCode码
        //11010111001100110 ^ 异或表示 值一样取0，值相异为1
        //00000000000000001
        //11010111001100111
        int h;
        String key = "one";
        h = key.hashCode();//获取hashCode值
        System.out.println("key通过hashCode()方法获取的hashcode值"+Integer.toBinaryString(h));
        int i = h >>> 16;//右位移16位，
        System.out.println("将hashcode值，右位移16位，用来减少碰撞"+Integer.toBinaryString(i));
        int hashCode = (h) ^ (i);//异或
        System.out.println("右位移16位异或减少碰撞，还能保留高位和低位的特性："+hashCode);
        System.out.println("hashCode的二进制"+Integer.toBinaryString(hashCode));


        //计算下标，n - 1 n是散列表长度，让高位参与运算，
        int n = 16;
        int i1 = 16 - 1;
        System.out.println(Integer.toBinaryString(i1));
        System.out.println("最终下标位置："+(i1&hashCode));

分析源码1：算hash

如何算hash,hash(),hashCode码，右移十六位异或，高位参与运算，减少碰撞

源码分析2：如何在用户指定大小时（用户可能指定偶数也可能指定负数，不可以指定就不用这么麻烦了，每次都<<1就可以了），依旧保证大小为2的幂次方,tableSizeFor 表示生成一个大于等于 cap 且为 2 的 N 次方的最小整数

下面的源码中，返回给定目标容量的，大于它并最接近它的2次幂，如果这个值大于设定的最大容量 MAXIMUM_CAPACITY（1<<30），则返回最大容量

我们测试一下上面这段代码的值（假设cap为8，我们看看cap-1和不减1的最终结果），发现虽然我们想要空间是8，但是不减一居然会得到16，有大量空间浪费（基数没啥大影响，所以不做讲解，主要是偶数有问题）

        System.out.println("=======================测试当我们向要将散列表长度扩充为8，我们如何确保长度为2的幂次方的基础上，还能不浪费空间呢===============================");
        int n = 8;//
        int n2 = n-1;//-1可以解决空间浪费
        System.out.println(n+"==================="+n2);
        System.out.println(Integer.toBinaryString(n)+"=============="+Integer.toBinaryString(n2));
//        n = n - 1;//7
        System.out.println(Integer.toBinaryString(n |= n >>> 1)+"=============="+Integer.toBinaryString(n2|= n2 >>> 1));
        System.out.println(Integer.toBinaryString(n |= n >>> 2)+"=============="+Integer.toBinaryString(n2|= n2 >>> 2));
        System.out.println(Integer.toBinaryString(n |= n >>> 4)+"=============="+Integer.toBinaryString(n2|= n2 >>> 4));
        System.out.println(Integer.toBinaryString(n |= n >>> 8)+"=============="+Integer.toBinaryString(n2|= n2 >>> 8));
        System.out.println(Integer.toBinaryString(n |= n >>> 16)+"=============="+Integer.toBinaryString(n2|= n2 >>> 16));

        System.out.println((n + 1)+"=============="+(n2+1));

为什么呢？首先我们n先减1，然后无符号右移，然后将右移结果位或 “|” n 。作用就是将最高位1后面填满1（从上图中就可以看出来）

为什么只位移到16呢，而且每次都是偶数？首先n是int型，最大4字节32位，1+2+4+8+16 = 31，正好满足要求，我们用HashMap指定的最大值来测试

我们发现上面不减1，居然还会得到负数。1000-1，正好111，加1,又变成1000

填满1是为什么呢？假设8这个数1000，-1后为111.一直位移，给它最高位后面全填上1(因为它本来就全是1，所以没啥效果),最后+1,1000，正好进位成一个最小的2的幂次方数

分析源码3：重要属性

常量，数组默认大小16，最大1<<30（2^30）,默认加载因子0.75f,

数组和大小，以及专门用来处理加载因子的变量threshold，还有threshold,代表要调整大小的下一个大小值(容量*负载系数)

链表结点

红黑树结点

重要属性JDK1.8特有，如果链表长度超过此值，需要将链表转换为红黑树

源码解析4：创建散列表

默认构造器直接让加载因子，搞成0.75，同时初始容量肯定也是16，这不过逻辑不在这里

指定初始大小的构造器，需要保证大小为2的幂次方，加载因子还是默认的0.75f

源码分析5：添加

put() 添加元素，调用putVal方法，并调用hash(key)方法计算了hash值，传入

putVal()方法，如果哈希表为空，初始化哈希表，然后直接插入结点到hash算法算出来的位置下标中，如果哈希表不为空，判断hash确定位置是否正确，如果正确，判断key是否一致，一致就是替换值。否则判断结点是不是红黑树节点，不是就说明是依然是链表结点，只不过不是当前下标数组的链表的头结点，需要往链表后面插。如果链表长度已经大于8了，需要变换为红黑树。不大于8，还需要判断链表每一个结点，key是否一样，一样就是替换，不是插入新结点。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //声明了一个局部变量 tab,局部变量 Node 类型的数据 p,int 类型 n,i
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //首先将当前 hashmap 中的 table(哈希表)赋值给当前的局部变量 tab,然后判断tab 是不是空或者长度是不是 0,实际上就是判断当前 hashmap 中的哈希表是不是空或者长度等于 0
        if ((tab = table) == null || (n = tab.length) == 0)
        //如果是空的或者长度等于0,代表现在还没哈希表,所以需要创建新的哈希表,默认就是创建了一个长度为 16 的哈希表
            n = (tab = resize()).length;
        //将当前哈希表中与要插入的数据位置对应的数据取出来,(n - 1) & hash])就是找当前要插入的数据应该在哈希表中的位置,如果没找到,代表哈希表中当前的位置是空的,否则就代表找到数据了, 并赋值给变量 p
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);//创建一个新的数据,这个数据没有下一条,并将数据放到当前这个位置
        else {//代表要插入的数据所在的位置是有内容的
        //声明了一个节点 e, 一个 key k
            Node<K,V> e; K k;
            if (p.hash == hash && //如果当前位置上的那个数据的 hash 和我们要插入的 hash 是一样,代表没有放错位置
            //如果当前这个数据的 key 和我们要放的 key 是一样的,实际操作应该是就替换值
                ((k = p.key) == key || (key != null && key.equals(k))))
                //将当前的节点赋值给局部变量 e
                e = p;
            else if (p instanceof TreeNode)//如果当前节点的 key 和要插入的 key 不一样,然后要判断当前节点是不是一个红黑色类型的节点
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//如果是就创建一个新的树节点,并把数据放进去
            else {
                //如果不是树节点,代表当前是一个链表,那么就遍历链表
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {//如果当前节点的下一个是空的,就代表没有后面的数据了
                        p.next = newNode(hash, key, value, null);//创建一个新的节点数据并放到当前遍历的节点的后面
                        if (binCount >= TREEIFY_THRESHOLD - 1) // 重新计算当前链表的长度是不是超出了限制
                            treeifyBin(tab, hash);//超出了之后就将当前链表转换为树,注意转换树的时候,如果当前数组的长度小于MIN_TREEIFY_CAPACITY(默认 64),会触发扩容,我个人感觉可能是因为觉得一个节点下面的数据都超过8 了,说明 hash寻址重复的厉害(比如数组长度为 16 ,hash 值刚好是 0或者 16 的倍数,导致都去同一个位置),需要重新扩容重新 hash
                        break;
                    }
                    //如果当前遍历到的数据和要插入的数据的 key 是一样,和上面之前的一样,赋值给变量 e,下面替换内容
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { //如果当前的节点不等于空,
                V oldValue = e.value;//将当前节点的值赋值给 oldvalue
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value; //将当前要插入的 value 替换当前的节点里面值
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;//增加长度
        if (++size > threshold)
            resize();//如果当前的 hash表的长度已经超过了当前 hash 需要扩容的长度, 重新扩容,条件是 haspmap 中存放的数据超过了临界值(经过测试),而不是数组中被使用的下标
        afterNodeInsertion(evict);
        return null;
    }

源码分析6：底层数组扩容

添加时，如何判断是否该扩容？散列表是空的时候，当前数组元素个数+1的值大于数组长度(散列表当前大小)

括容调用resize()方法,如果table == null, 则为HashMap的初始化, 生成空table返回即可,如果table不为空, 需要重新计算table的长度, newLength = oldLength << 1（原oldLength已经到了上限, 则newLength = oldLength），遍历oldTable首节点为空, 本次循环结束，无后续节点, 重新计算hash位, 本次循环结束，当前是红黑树, 走红黑树的重定位，当前是链表, JAVA7时还需要重新计算hash位, 但是JAVA8做了优化, 通过(e.hash & oldCap) = = 0来判断是否需要移位; 如果为真则在原位不动, 否则则需要移动到当前hash槽位 + oldCap的位置

为什么加载因子是0.75f（为什么长度到数组0.75倍的时候，就扩容）

如果填装因子（加载因子）为1，空间利用率得到很大满足，很容易碰撞，产生链表–查询效率低

如果是0.5，碰撞概率低，常常还没等碰撞，就扩容了，产生链表几率低，查询效率高，空间利用率低，

所以取中间值0.75

官方注释的，关于统计学的解释（根据统计学的结果, hash冲突是符合泊松分布的, 而冲突概率最小的是在7-8之间, 都小于百万分之一了; 所以HashMap.loadFactor选取只要在7-8之间的任意值即可，7.1、7.2、7.3…但偏偏用了7.5，原因是HashMap的扩容机制，有专门的文章解释，这里就不提了）

3. `TreeMap源码(JDK1.8)`

TreeMap底层就是一棵二叉排序树，学会二叉排序树就行了，没啥好讲的，就走一遍源码流程得了

底层维护二叉排序树，结点为内部类Entry<K,V>类型,保存key-value，左子结点，右子结点，父节点

put()方法，简单的二叉排序树插入逻辑，先拿根结点准备遍历，调用比较器比较（比较key），将元素插入（或替换）到合适的位置

六、`同步类容器`

1. `Collections工具类转换`

首先，集合有一个工具类，Collections，提供一些api，方便我们操作集合，但是不常用。然而我们可以用它将线程不安全的容器，转换成线程安全的。

ArrayList<Integer> arrayList = new ArrayList<>();
List<Integer> synchronizedList = Collections.synchronizedList(arrayList);//变成线程安全

线程不安全的ArrayList

将ArrayList变成线程安全

import java.util.*;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class CollectionsTest {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        HashMap<String, Integer> hashMap = new HashMap<>();

        List<Integer> synchronizedList = Collections.synchronizedList(arrayList);
        Map<String, Integer> synchronizedMap = Collections.synchronizedMap(hashMap);

        //搞个线程池测试
        ExecutorService es = Executors.newFixedThreadPool(100);

        //向集合中插入10000个值
        for(Integer i = 0;i<10000;i++){
            Integer finalI = i;
            es.execute(new Runnable() {
                @Override
                public void run() {
                    //arrayList.add(1);//线程不安全，直接报错Exception in thread "main" java.util.ConcurrentModificationException
                    synchronizedList.add(finalI);
                }
            });
        }
        //System.out.println(arrayList);
        System.out.println(synchronizedList);
        //关闭线程池
        es.shutdown();
        //监控线程是否执行完毕
        while(true){
            System.out.println("正在监控线程是否都执行完毕");
            //线程都执行完后返回true
            if(es.isTerminated()){
                System.out.println("所有子线程都执行完毕了！");
                //输出集合
                System.out.println(synchronizedList);
                //执行完毕后看一下集合中元素数量
                System.out.println(synchronizedList.size());
                if(synchronizedList.size() == 10000){
                    System.out.println("线程安全！");
                }else{
                    System.out.println("线程不安全！！！");
                }
                break;
            }
        }
    }
}

2. `Collections源码(JDK1.8)`

synchronizedList()方法：判断list是不是RandomAccess对象（List接口继承RandomAccess），如果是返回SynchronizedRandomAccessList对象，否则返回SynchronizedList

SynchronizedRandomAccessList：是Collections的内部类，构造方法调用父类SynchronizedList的构造

SynchronizedList的构造：SynchronizedList也是Collections的内部类，调用父类SynchronizedCollection构造后，让类中list等于构造好的list

SynchronizedCollection构造，如果传过来的Collection为空，直接报错，否则让进行同步的对象指向它

add()方法：全部对mutex(要进行同步的容器)加了锁

可以发现，他对整个集合加了锁，这是很影响性能的

七、`并发类容器`

JDK1.5之后，提供多种并发类容器，可以代替同步类容器，提升性能、吞吐量

ConcurrentMap：接口，有两个实现类

ConcurrentHashMap实现类，替代加锁版HashMap和HashTable（本身就线程安全）

ConcurrentSkipListMap实现类，替代TreeMap

1. `ConcurrentMap`

HashTable为什么被淘汰？为什么效率低

这玩意加锁直接把整个容器加锁

当一个线程存数据的时候，其它线程没法访问

如果存和取不在同一个位置，应该是不冲突的

就像你去网吧上网，网吧一共100台机子，一个人去开了一台机子，其它人居然得等他上完机，下一个人才能进去再开一台，尽管两个机子，不是同一台

ConcurrentMap为什么效率高

它将集合分成多个片区（16个），分别加锁，降低锁的粒度

当一个线程去第一个片区，第一个片区加锁，其它片区不受影响

测试一下,ConcurrentMap最快，HashTable慢了4倍，synchronizedMap最慢:simple_collection/ConcurrentMapApiTest.java

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class ConcurrentMapApiTest {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> cHMap = new ConcurrentHashMap<>();
        //线程池
        ExecutorService es = Executors.newFixedThreadPool(10);

        for (int i = 0;i<10;i++){
            es.execute(new Runnable() {
                @Override
                public void run() {
                    long startTime = System.currentTimeMillis();
                    for (int j = 0;j<1000000;j++){
                        cHMap.put("test"+j,j);
                    }
                    long endTime = System.currentTimeMillis();
                    System.out.println(Thread.currentThread()+"==ConcurrentHashMap==>"+"执行完成共需要"+(endTime - startTime));

                }
            });
        }
        es.shutdown();
        System.out.println("========================HashTable=============================");
        //线程池
        ExecutorService es2 = Executors.newFixedThreadPool(10);
        Hashtable<String, Integer> hashtable = new Hashtable<>();
        for (int i = 0;i<10;i++){
            es2.execute(new Runnable() {
                @Override
                public void run() {
                    long startTime = System.currentTimeMillis();
                    for (int j = 0;j<1000000;j++){
                        hashtable.put("test"+j,j);
                    }
                    long endTime = System.currentTimeMillis();
                    System.out.println(Thread.currentThread()+"==HashTable==>"+"执行完成共需要"+(endTime - startTime));

                }
            });
        }
        es2.shutdown();
        System.out.println("========================synchronizedMap=============================");
        //线程池
        ExecutorService es3 = Executors.newFixedThreadPool(10);
        Map<String, Integer> synchronizedMap = Collections.synchronizedMap(new HashMap<>());

        for (int i = 0;i<10;i++){
            es3.execute(new Runnable() {
                @Override
                public void run() {
                    long startTime = System.currentTimeMillis();
                    for (int j = 0;j<1000000;j++){//太慢了，我给他剪了个0
                        synchronizedMap.put("test"+j,j);
                    }
                    long endTime = System.currentTimeMillis();
                    System.out.println(Thread.currentThread()+"==synchronizedMap==>"+"执行完成共需要"+(endTime - startTime));
                }
            });
        }
        es3.shutdown();

    }
}

2. `COW(Copy On Write)并发容器,写时复制容器`

原理

向容器中添加元素时，先将容器copy一份搞个新容器，将元素添加到新容器中，再将原容器引用指向形容器。

并发读的时候不需要锁定容器，因为原容器不会发生变化。读写分离的思想

但只能保证最终一致性，不能保证数据实时一致性

如果希望写入数据后，马上就能读到，请不要使用CopyOnWrite容器

适用于读多写少（高并发读的场景下），每次写操作，都会复制容器，一旦写进程过多，JVM必定内存消耗高，甚至内存溢出。

两种COW容器

CopyWriteArrayList : 替代ArrayList

CopyOnWriteArraySet ：替代Set

1. `CopyOnWriteArrayList实现类`

简单使用：simple_collection/COWApiTest.java

import java.util.concurrent.CopyOnWriteArrayList;

public class COWApiTest {
    public static void main(String[] args) {
        CopyOnWriteArrayList<Integer> cOWList = new CopyOnWriteArrayList<>();
        //添加元素，可添加重复元素
        cOWList.add(1);
        cOWList.add(1);
        cOWList.add(1);
        System.out.println("使用add添加，元素可以重复："+cOWList);
        cOWList.addIfAbsent(1);
        System.out.println("使用addIfAbsent添加，如果集合中已有相同的，不可以添加："+cOWList);
    }
}

2. `CopyOnWriteArrayList源码(JDK1.8)`

可重入锁
就是一个线程执行一个加锁的代码，此时这个线程，执行另一个加锁的代码，两个锁发现是同一个线程，就让线程可以进入，这就是可重入锁

源码中，声明了可重入锁，所有的操作，都使用这个lock加锁，这样，拿到锁的线程，就可以一趟线完成自己的操作

基本源码

构造方法：创建了一个空列表，底层维护一个volatile修饰的Object型数组

add()方法：首先拿到了可重入锁lock，锁住try代码块，里面复制了一份当前数组，长度+1，将要插入元素，添加到数组末尾，然后更新数组

addIfAbsent()方法：先拿到数组对象，引用保存到一个变量里面，然后判断元素是否存在，如果存在返回false，否则执行添加；

addIfAbsent()方法细节：先拿可重入锁，对try加锁，再次获取数组current（高并发，我们刚判断元素是否存在，可以又有其它线程操作了数组），如果当前保存数组和再次获取的数组current不一样，则进行优化。否则，不进行优化，和add()方法逻辑相同

优化：先获取，当前数组长度和我们获取到的数组长度，小的内个值，然后根据这个值遍历，我们拿到的和现在实际的数组，每个元素进行比较，如果数组某个元素不一致，或者当前要插入元素和数组中某元素相同（eq()方法，处理了null值），直接return false

上面没退出，判断当前要插入元素是否存在，存在返回false

addIfAbsent()方法效率会比add()低很多，因为每次都需要比较

3. `CopyOnWriteArraySet源码(JDK1.8)`

使用和普通set没有区别，不做api介绍，直接上源码分析，其实就是用CopyOnWriteArrayList实现而已，感觉完全没必要看

构造方法：底层维护CopyOnWriteArrayList

add()方法：调用CopyOnWriteArrayList的addIfAbsent()方法

八、`队列`

简单类图（烦的不行，东西怎么越写越多？）：simple_collection/uml/Queue.puml

Queue也是Collection容器的一种，额外规定了队列的特性

BlockingQueue，阻塞队列，因为队列这种数据结构本身就用于多线程场景，所以都是阻塞的

阻塞队列有很多，我们只介绍上面的几种

为什么不用非阻塞队列

假设队列容量为10，现在队列已满

当第11个哥们，要入队列，会直接丢失

而阻塞队列，会让这哥们先等着，等有人办完事出队列了，你再进去

当从队列取数据时，队列为空

非阻塞队列，会获得一个null值

阻塞队列，队列为空，会让这哥们先等着，等队列有东西了，你再去取

1. `BlockingQueue接口常用API解析`

BlockingQueue是个接口，需要具体实现类，给出APi，不做测试了

描述（关于我们 \| 联系我们 \| 留言反馈专注分享技术，共同学习，共同进步。侵权联系[admin#icode9.com] Copyright (C)ICode9.com, All Rights Reserved. ICode9版权所有

码农公寓

文章目录

一、Collection接口

1. 常用Api解析

2. Iterator接口

3. ArrayList的iterator()方法源码(JDK1.8)

4. 集合之间如何比较

二、List接口

1. 常用Api解析

2. ArrayList源码(JDK1.8)

3. Vector源码(JDK1.8)

4. iterator()方法的Itr迭代器并发修改异常

5. ListIterator接口，ArrayList的ListItr实现类

三、LinkedList实现类

1. 常用Api解析

2. 两种迭代器使用方法比较

3. LinkedList源码(JDK1.8)

四、Set接口

1. HashSet实现类和源码(JDK1.8)

2. LinkedHashSet实现类和源码(JDK1.8)

3. TreeSet实现类和源码(JDK1.8)

五、Map接口

1. 常用Api解析

2. HashMap源码(JDK1.8)

3. TreeMap源码(JDK1.8)

六、同步类容器

1. Collections工具类转换

2. Collections源码(JDK1.8)

七、并发类容器

1. ConcurrentMap

2. COW(Copy On Write)并发容器,写时复制容器

1. CopyOnWriteArrayList实现类

2. CopyOnWriteArrayList源码(JDK1.8)

3. CopyOnWriteArraySet源码(JDK1.8)

八、队列

1. BlockingQueue接口常用API解析

相关文章

一、`Collection接口`

1. `常用Api解析`

2. `Iterator接口`

3. `ArrayList的iterator()方法源码(JDK1.8)`

4. `集合之间如何比较`

二、`List接口`

1. `常用Api解析`

2. `ArrayList源码(JDK1.8)`

3. `Vector源码(JDK1.8)`

4. `iterator()方法的Itr迭代器并发修改异常`

5. `ListIterator接口，ArrayList的ListItr实现类`

三、`LinkedList实现类`

1. `常用Api解析`

2. `两种迭代器使用方法比较`

3. `LinkedList源码(JDK1.8)`

四、`Set接口`

1. `HashSet实现类和源码(JDK1.8)`

2. `LinkedHashSet实现类和源码(JDK1.8)`

3. `TreeSet实现类和源码(JDK1.8)`

五、`Map接口`

1. `常用Api解析`

2. `HashMap源码(JDK1.8)`

3. `TreeMap源码(JDK1.8)`

六、`同步类容器`

1. `Collections工具类转换`

2. `Collections源码(JDK1.8)`

七、`并发类容器`

1. `ConcurrentMap`

2. `COW(Copy On Write)并发容器,写时复制容器`

1. `CopyOnWriteArrayList实现类`

2. `CopyOnWriteArrayList源码(JDK1.8)`

3. `CopyOnWriteArraySet源码(JDK1.8)`

八、`队列`

1. `BlockingQueue接口常用API解析`