浅谈java中容器的发展史之collection接口

java中容器的发展史

collection接口
- collection的API
List接口
- Vector及其子类Stack
- - Vector
  - Stack类
- ArrayList和linkedList
- - ArrayList
  - linkedList
- linkedeList和ArrayList的区别
- - CopyOnWriteArrayList
Set接口
- HashSet 及其子类linkedHashSet
- - HashSet
  - - 小结HashSet:
    - - 为什么默认加载因子为0.75呢?
  - linkedHashSet
  - EnumSet---抽象类
  - SortedSet 接口
  - - SortedSet 接口实现类----TreeSet
    - - CopyOnWriteArraySet
    - ConcurrentSkipListSet
Queue 接口
- Queue的子接口---->>>Deque
- - ArrayDeque
  - ConcurrentlinkedDeque
- Deque子接口----BlockingDeque接口
- linkedBlockingDeque
- - linkedBlockingDeque与ArrayDeque对比
- Queue 接口
- - ConcurrentlinkedQueue
- Queue 的子接口---->BlockingQueue
- - ArrayBlockingQueue
  - linkedBlockingQueue;
  - PriorityBlockingQueue

在jdk 1.*版本的时候,主要的容器有 Vector(实现List接口)和HashTable(实现Map接口),随着jdk版本的衍变,同时为了处理高并发环境下的事务,jdk后来又添加了一些适合于高并发情况下的容器;现在我们循着历史的脚步一起探究一下java中的容器,以及了解为什么有些容器的实现已淡出我们的视野;

collection接口 collection的API

继承实现关系---->>>
public interface Collection extends Iterable
接口中的方法----->>>

该接口下有很多实现类,

按照存储的特点来分:
存储一个 List,Set和Queue,
存储键值对的 map
按照继承实现关系来分:
List
Set
Queue
Map

不着急,一个一个来:先看容器的根接口----->>>Collection接口

该接口的描述---->
集合层次结构中的根接口。一个集合代表一组对象，称为它的元素。一些集合允许重复元素，而另一些则不允许。有些是有序的，有些是无序的。 JDK 不提供此接口的任何直接实现：它提供了更具体的子接口（如 Set 和 List）的实现。此接口通常用于传递集合并在需要最大通用性的地方操作它们。

Collection接口中的默认方法------>>

关于默认方法,子类可以选择去实现也可以选择不实现;

List接口

list接口的实现类----->>>
从最早的Vector, Stack到ArrayList,linkedList.CopyOnWriteList
List中的静态方法----->>>

import java.util.List;
public class ListDemo {
    public static void main(String[] args) {
        List he = List.of("你好");
        he.add("hello");
        he.forEach(s -> {
            System.out.println(s);
        });
    }
}

可以看到of方法返回的是一个不可修改的List集合;

Exception in thread "main" java.lang.UnsupportedOperationException

Vector及其子类Stack Vector

import java.util.Collection;
import java.util.Iterator;
import java.util.Vector;
import java.util.stream.Stream;

class Person{
    String name;

    public Person(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + ''' +
                '}';
    }
}
public class Vector_1Demo {
    public static void main(String[] args) {
      
        Collectionc=new Vector<>(100,12);
        c.add(new Person("张三"));
        c.add(new Person("李四"));
        System.out.println(c.size());
      
        for (Person per:
           c  ) {
            System.out.println(per);
        }
        Iterator iterator = c.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
        //流式操做 stream,感兴趣可以查一下API
        Stream personStream1 = c.parallelStream();
        personStream1.forEach(person -> System.out.println(person));
       
        Stream personStream = c.parallelStream();
        personStream.forEach(person -> System.out.println(person));
    }
}

来看API---->>
Vector的继承实现关系
public class Vector extends AbstractList
implements List, RandomAccess, Cloneable, Serializable

描述:Vector类实现了一个可增长的数组对象。像数组一样，它包含的组件可以是使用整数索引访问。然而，一个大小 Vector可以根据需要增长或缩小以适应添加和删除项目之后

类中的方法不必多说,重点关注一下两点----
构造方法---->>

类的构造----

截取部分方法----->
Vector的底层构造----->>

Vector维护了三个变量------
Object[] elementData--------数组
int elementCount------>>元素数量
int capacityIncrement---->>>容量扩充

Vector的扩容机制----->>>
1,如果有通过构造方法指定初始容量和容量扩充,那么当容量不够时,Vector会扩充为旧的长度+扩容长度
2,如果没有指定扩容量,则扩容时容量变为扩容时的两倍

Vector类中的大部分方法都是加了锁的,因此在高并发情况下添加或者移除元素的效率不如ArrayList,但是线程安全
以卖票为例子

import java.util.Vector;
public class TicketSeller02 {
    static Vectorvector= new Vector<>();
    static {
        for (int i = 1; i <11; i++) {
            vector.add("第--"+i+"张票");
        }
    }
    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            new Thread(()->{while (vector.size()>0){
            //原子方法----size()
//如果在这之间有一些其他操做也是需要加锁的,因为原子操做与原子操做之间是不确保线程安全的;
//原子方法---remove();
                System.out.println(vector.remove(0));}
            }).start();
        }
    }
}

Stack类

public class Stack extends Vector

描述---->>
这 Stack类代表后进先出 (LIFO) 对象堆栈。

首次创建堆栈时，它不包含任何项目。

Deque接口及其实现提供了一套更完整、更一致的 LIFO 堆栈操作，应优先于此类使用。例如：
Deque stack = new ArrayDeque();

import java.util.Stack;
public class StackDemo {
    public static void main(String[] args) {
        Stackstack= new Stack<>();
        stack.add(10);
        stack.add(88);
        stack.add(99);
        stack.add(111);
        stack.add(88);
        Integer peek = stack.peek();//查看栈顶元素,而不将其移除栈;
        System.out.println("A-栈顶元素"+peek);//111
        System.out.println("B-栈顶元素"+stack.push(4444));//将4444压入栈顶
        Integer pop = stack.pop();
        System.out.println("移除栈顶元素"+pop);
        System.out.println("检查此时的栈顶元素--"+stack.peek());
        System.out.println("88所在栈的位置--"+stack.search(88));//返回对象在此堆栈上的从 1 开始的位置。 

    }
}

小结---->>>>

由于历史原因,你会发现有些容器多次实现了同一个接口比如Vector继承AbstractList,而AbstractList实现了List,但Vector也实现了List接口;

ArrayList和linkedList ArrayList

public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, Serializable

描述:可调整大小的数组实现 List界面。也是列表操作，并允许所有元素，包括 null. 除了实施 List界面，此类提供操作数组大小的方法在内部用于存储列表。（这个类大致相当于 Vector，除了它是不同步的。）

ArrayList的插入效率是比较高的,add()方法的时间复杂度O(N)

如果多个线程同时访问一个 ArrayList实例，并且至少有一个线程在结构上修改了列表，它必须在外部同步。（结构修改是添加或删除一个或多个元素的任何操作，或显式调整后备数组的大小；仅仅设置元素的值不是结构修改。）这通常是通过同步一些自然封装列表的对象。如果不存在这样的对象，则应使用 Collections.synchronizedList方法。

List list = Collections.synchronizedList(new ArrayList(…));

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ArrayListDemo {
    public static void main(String[] args) {
        ArrayListlist= new ArrayList<>();
//        使得这个list变为线程安全的集合
        List synList = Collections.synchronizedList(list);
//        非同步的添加
        list.add(0);
//        同步的添加
      synList.add(1);
        list.forEach(i->{
            System.out.println(i);
        });

        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
        //返回元素的位置----如果有多个,则返回第一个
        System.out.println(synList.indexOf(0));
        //返回这个list的浅拷贝---即只是元素的拷贝,地址是不一样的
        Object clone = list.clone();
        System.out.println(clone);
        ArrayList list1=list;//这个是深拷贝,元素和地址都拷贝
        
    }
}

以售票为例子

public class TicketSeller {
    static List list= new ArrayList<>();
    static{
        for (int i = 1; i < 11; i++) {
            list.add("第--"+i+"张票");
        }
    }
    public static void main(String[] args) {
        List list1 = Collections.synchronizedList(list);
        for (int i = 0; i < 10; i++) {
            new Thread(()->{
                while(list1.size()>0){
                    System.out.println(list1.remove(0));
                }
            }).start();
        }

    }
}

ArrayList的底层原理---->>> 数组

在ArrayList的底层维护了两个变量----

transient Object[] elementData;
private int size;

ArrayList的扩容原理---->>
说到扩容原理先看构造方法----->>
不指定初始容量即 new ArrayList()这是默认容量为10
扩容原理---->>

当我们用无参构造创建集合时;
虽然说默认容量是10,但它是在添加第一个元素时才生效的;

小结—>>>

1,ArrayList中扩容机制----扩容为原来的1.5倍,节省空间
2,ArrayList中的方法为非同步,但是也可以通过Collections工具类使其变为同步的List

linkedList

继承实现关系:
public class linkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, Serializable

描述:----双向链表的实现了 List和 Deque接口。允许所有元素（包括 null).

如果多个线程同时访问一个链表，并且至少其中一个线程在结构上修改了列表，它必须是外部同步。（结构修改是任何操作添加或删除一个或多个元素；仅设置值元素不是结构修改。）这通常是通过同步一些自然而然的对象来完成封装列表。如果不存在这样的对象，则应使用 Collections.synchronizedList方法。这最好在创建时完成，以防止意外对列表的非同步访问：

List list = Collections.synchronizedList(new linkedList(…));

构造方法

import java.util.Collections;
import java.util.linkedList;
import java.util.List;
public class linkedListDemo {
    public static void main(String[] args) {
        linkedListlinkedList= new linkedList<>();
        List lks = Collections.synchronizedList(linkedList);//同步链表
        linkedList.add(0);
        lks.add(100);
        linkedList.add(0,12);
        System.out.println(lks);
        System.out.println(linkedList.peek());//返回第一个元素
        System.out.println(linkedList.peekFirst());
        System.out.println(linkedList.peekFirst());//返回第一个元素
        System.out.println(linkedList.peekLast());//返回最后一个元素
        System.out.println(linkedList.element());//返回第一个元素
        System.out.println(linkedList.offer(88));//链表尾部插入一个元素
        System.out.println(linkedList.offerFirst(99));//链表头部插入一个元素
        System.out.println(linkedList.offerLast(100));//链表尾部插入一个元素
        System.out.println(linkedList);
        System.out.println(linkedList.poll());//检索并删除第一个元素,返回这个元素
        System.out.println(linkedList.pollFirst());//检索并删除第一个元素,返回这个元素
        System.out.println(linkedList.pollLast());//检索并删除最后一个元素,返回这个元素
        System.out.println(linkedList);
        linkedList.removeFirst();//移除第一个
        linkedList.removeLast();//移除第二个
    }
}

链表在查询数据时效率低,因为要遍历整个集合,但是在插入数据时效率较高!

linkedList的底层实现----->
底层维护了一个节点以及大小

linkedeList和ArrayList的区别

1、底层存储的数据结构不同,ArrayList是Object(动态数组)的数据结构，linkedList是Node(链表)的数据结构。
2,ArrayList由于时数组,可以通过下标快速查询数据而linkedlist是通过指针进行移动来查询数据的,
3,linkedList在增加和删除数据时效率较高,
在API中没有发现linkedList关于容量的一些信息------即linkedlist不用考虑初始容量的问题,即用多少就是多少,不需要预留容量;

CopyonWriteArrayList

继承实现关系:

public class CopyonWriteArrayList extends Object implements List, RandomAccess, Cloneable, Serializable

描述信息:
线程安全的变体 ArrayList其中所有突变操作（ add, set，等等）由制作底层数组的新副本。

这通常成本太高，但可能更有效当遍历操作数量远远超过替代方案时突变，当你不能或不想时很有用同步遍历，但需要排除之间的干扰并发线程。

简单的说就是一个关于读写的线程安全的一个ArrayList
构造方法—>>

import java.util.ArrayList;
import java.util.concurrent.CopyOnWriteArrayList;
public class CopyOnWriteArraylistDemo {
    public static void main(String[] args) {
        //创建一个空列表
        CopyOnWriteArrayList copy = new CopyOnWriteArrayList<>();
        //线程安全的写操做
        //写互斥
        copy.add(0);
        copy.add(1);
//     读共享
        Integer integer = copy.get(0);
        System.out.println("_________________");
        ArrayList list = new ArrayList<>(10);
        list.add(0);
        list.add(1);
        list.add(2);
        list.add(3);
        CopyOnWriteArrayList CWASList=new CopyOnWriteArrayList(list);
        CWASList.add(100);

        System.out.println(CWASList);
        Object []objects= new Object[100];
        CopyOnWriteArrayList ca=new CopyOnWriteArrayList(objects);
        ca.add(999);
        System.out.println(ca);
    }
}

这个类的一个好处是,对于高并发环境下,同时读读是不需要加锁的,读写,写读,写写操做需要加锁,这类似于读写锁的实现;

先看一下写操做的add()方法---->>

在这个类中那个关于添加数据的都加了不同粒度的锁,关于读取数据的都没有加锁;

这个相比于ArrayList,能做到线程安全,但是如果数据量太多,那么对于服务器的开销会很大,因为是通过在拷贝上修改来实现线程安全的,通过这个拷贝来替换掉原来的;

以售票为例子

public class TicketSeller02 {
    static CopyOnWriteArrayList coa=new CopyOnWriteArrayList<>();
    static {
        for (int i = 1; i <11 ; i++) {
            coa.add("第--"+i+"张票");
        }
    }
    public static void main(String[] args) {     
        for (int i = 0; i < 10; i++) {
            new Thread(()->{while (coa.size()>0){
                System.out.println(coa.remove(0));}
            }).start();
        }

    }
}

小结:-----

1,本身线程安全(读与写)的容器-----vector ,stack 读写都加了锁;
2,读写不安全的 ArrayList和linkedlist,不过可以通过Collections工具类的 synchronizedList 来返回一个安全的容器读写都加了锁)
3,读安全(未加锁),写安全的(加锁)CopyOnWriteArrayList,原理时写的时候拷贝一份,在末尾把添加进的元素塞进去;

Set接口

继承实现关系—>

public interface Set extends Collection

描述:
不包含重复元素的集合。更正式地说，集合不包含一对元素 e1 和 e2，使得 e1.equals(e2)，并且最多包含一个空元素。
该接口的实现类中一些集合实现对它们可能包含的元素有限制。例如，有些实现禁止空元素，有些实现对其元素的类型有限制。

Set.of 和 Set.copyOf 静态工厂方法提供了一种创建不可修改集的便捷方法。这些方法创建的 Set 实例具有以下特点：

它们是不可修改的。不能添加或删除元素。调用 Set 上的任何 mutator 方法将始终导致抛出
UnsupportedOperationException。
如果包含的元素本身是可变的，这可能会导致 Set 的行为不一致或它的内容似乎发生了变化。
它们不允许空元素。尝试使用空元素创建它们会导致 NullPointerException。
如果所有元素都可序列化，则它们是可序列化的。
他们在创建时拒绝重复的元素。传递给静态工厂方法的重复元素会导致 IllegalArgumentException

接口中的方法----->

HashSet 及其子类linkedHashSet HashSet

继承实现关系------>>
public class HashSet extends AbstractSet
implements Set, Cloneable, Serializable

描述:
这个类实现了 Set接口，由哈希表支持（实际上是一个 HashMap实例）。它不保证集合的迭代顺序；特别是，它不保证随着时间的推移，订单将保持不变。这个类允许 null 元素。

此实现不是同步的。如果多个线程同时访问哈希集，并且至少有一个线程修改了集，则必须外部同步。这通常是通过在自然封装集的某个对象上同步来实现的。如果没有此类对象，则应使用集合"包装"。同步集法。最好在创建时间完成此工作，以防止意外的不同步访问集：

Set s = Collections.synchronizedSet(new HashSet(…));

构造方法:
HashSet的底层维护了一个HashMap,

import java.util.HashSet;
import java.util.Set;
public class HashSetDemo {
    public static void main(String[] args) {
        //无参构造---默认16,加载因子0.75
        Setset= new HashSet<>();
        set.add(1);
        set.add(6);
        set.add(1);
        set.add(null);
        set.add(2);
        System.out.println(set);//[null, 1, 2, 6]--说明后面重复的元素被自动过滤掉,按照升序排列
        //只指定初始容量,加载因子仍默认为0.75
        Setset1= new HashSet<>(8);
        //指定初始容量,同时指定加载因子
        Setset2= new HashSet<>(8,1);
    }
}

HashSet容量初始化分析—>>>>

hashSet怎么做到没有重复元素?

关于HashSet添加的顺序是无序的,即不是按照我们添加使得顺序显示的;

例如以下代码------>>>

public class HashSetDemo {
    public static void main(String[] args) {
        //无参构造---默认16,加载因子0.75
        Setset= new HashSet<>();
        set.add(9);
        set.add(6);
        set.add(5);
        set.add(7);
        set.add(8);
        set.add(7);
        System.out.println(set);
        //只指定初始容量,加载因子仍默认为0.75
        Setset1= new HashSet<>(8);
        //指定初始容量,同时指定加载因子
        Setset2= new HashSet<>(8,1);
    }
}

小结HashSet:

1,底层是通过hashmap实现的,只不过用了键值对中的key;
2,扩容机制是 (无参构造) 容量=阈值时开始扩容,每次扩容为原来的2倍;

为什么默认加载因子为0.75呢?

因为当加载因子太小时hash碰撞的概率会增加,这使得数据分布不均匀;当加载因子太大时,会产生空间上的浪费,所以去一个折中值0.75;

linkedHashSet

继承实现关系---->
public class linkedHashSet
extends HashSet implements Set, Cloneable, Serializable

描述:

哈希表和链表的实现 Set界面，具有可预测的迭代顺序。这个实现不同于 HashSet因为它维护一个双向链表贯穿它的所有条目。这个链表定义了迭代顺序，这是元素插入集合的顺序（插入顺序）。

请注意，插入顺序不影响如果一个元素被重新插入到集合中。（一个元素 e 重新插入到一个集合中 s如果 s.add(e)被调用时 s.contains(e)会回来 true紧接在之前调用。）

请注意，此实现不是同步的。如果多个线程同时访问一个链接的散列集，并且至少其中一个线程修改了集合，它必须是同步的外部。这通常是通过同步一些自然封装集合的对象。如果不存在这样的对象，则应使用 Collections.synchronizedSet方法。这最好在创建时完成，以防止意外对集合的非同步访问：

Set s = Collections.synchronizedSet(new linkedHashSet(…));

底层实现原理----->>>
哈希表和双向链表

构造函数----->跟HashSet形式是一样的;
除了双向链表,其他方面跟HashSet基本是一样的;

小结:
1,linkedHashSet中元素排序是有序的,因为可以通过双向链表的形式找到每一个元素;
2,底层依旧是hashMap,在HashSetde 基础上多维护了一个链表;用的是hash表和双向链表来实现的

EnumSet—抽象类

继承实现关系:

public abstract class EnumSet extends
AbstractSet implements Cloneable, Serializable

描述:
一个专门的 Set用于枚举类型的实现。所有的枚举集中的元素必须来自单个枚举类型，即在创建集合时显式或隐式指定。枚举集在内部表示为位向量。这种表示是非常紧凑和高效。这个时空表现类应该足够好以允许将其用作高质量的类型安全替代传统 int-基于“位标志”。甚至散装操作（例如 containsAll和 retainAll）应该如果他们的参数也是枚举集，则运行速度非常快。

像大多数集合实现一样， EnumSet不是同步。如果多个线程同时访问一个枚举集，并且在至少有一个线程修改了集合，它应该是同步的外部。这通常是通过同步一些自然封装枚举集的对象。如果不存在这样的对象，该集合应该使用 Collections.synchronizedSet(java.util.Set)方法。这最好在创建时完成，以防止意外非同步访问：

Set s = Collections.synchronizedSet(EnumSet.noneOf(MyEnum.class));

由于该类为抽象类,类中的方法都为静态方法,所以在创建枚举集合的时候可以通过类名调用静态方法;

简单地说,EnumSet是专门为枚举类集合设计的,因此在添加和取出枚举值时操做要比HashSet要快!!

import java.util.EnumSet;
public class EnumSetDemo {
    public static void main(String[] args) {
        //创建一个枚举集合,包含没居中所有元素
        EnumSet fruits = EnumSet.allOf(FRUIT.class);
        fruits.add(FRUIT.FRUIT1);
        System.out.println(fruits.size());
//拷贝一个fruits
        EnumSet fruits1 = EnumSet.copyOf(fruits);
//创建一个指定为枚举类型为FRUIT的空的集合,
        EnumSet fruits2 = EnumSet.noneOf(FRUIT.class);
        System.out.println(fruits2.size());
        EnumSet clone = fruits.clone();
    }

}

我很是好奇,于是做了个不成熟的实验------>>
有这样一个枚举 FRUIT,里面有十个枚举元素
分别往 HashSet 和EnumSet里面添加;
本实验为重复100000次(扩大时间以便于观察)

import gavin.CollectionDemo.Other.FRUIT;
import java.util.EnumSet;
import java.util.HashSet;
import java.util.Set;
public class EnumSetDemo {
    //准备好容器
    static EnumSet fruits2 = EnumSet.noneOf(FRUIT.class);
    static HashSet hashSet = new HashSet<>();
    //将枚举值一个个去除放到数组中
    static FRUIT fruits[] = FRUIT.values();
    public static void main(String[] args) throws InterruptedException {
        Thread thread = new Thread(() -> {
          long  start = System.currentTimeMillis();
            for (int i = 0; i < 100000; i++) {
                AddE(hashSet);
                RemoveE(hashSet);
            }
            long end = System.currentTimeMillis();
            System.out.println(end - start);
        });
        Thread thread1 = new Thread(() -> {
          long  start = System.currentTimeMillis();
            for (int i = 0; i < 100000; i++) {
                AddE(fruits2);
                RemoveE(fruits2);
            }
            long end = System.currentTimeMillis();
            System.out.println(end - start);
        });
        thread.start();
       //thread1.start();
       thread.join();
       // thread1.join();
//thread  ----44
//thread1-----14

    }

    //    拆开挨个添加   
    static void AddE(Set set) {
        for (FRUIT fruit :
                fruits) {
            set.add(fruit);
        }
    }//

    // 拆开挨个移除
    static void RemoveE(Set set) {
        for (FRUIT fruit :
                fruits) {
            set.remove(fruit);
        }
    }
}

SortedSet 接口

继承实现关系----->>

public interface SortedSet extends Set

描述:

种 Set这进一步提供了的排序其元素。元素使用它们的排列自然顺序，或由 Comparator通常在排序时提供设置创建时间。集合的迭代器将遍历集合元素升序。提供了几个额外的操作以利用排序。（这个界面是设置类似物 SortedMap.)

插入到有序集合中的所有元素都必须实现 Comparable接口（或被指定的比较器接受）。此外，所有这些元素必须相互比较： e1.compareTo(e2) （或者 comparator.compare(e1, e2)) 不得抛出 ClassCastException对于任何元素 e1和 e2在排序集。试图违反此限制将导致引发错误的方法或构造函数调用 ClassCastException.

请注意，排序集维护的排序（无论是否为提供了显式比较器）必须与 equals 一致，如果排序集是为了正确实现 Set集合。

所有通用排序集实施类应提供四个"标准"构造器：
1）空（无参数）构造器，该构造符创建根据其元素的自然顺序排序的空排序集。

2）具有单个类型参数的构造器，该构造器创建根据指定的比较器排序的空排序集。

3）具有单个类型参数的构造器，该构造器创建具有与其参数相同的元素的新排序集，根据元素的自然顺序进行排序。

4）具有单个类型参数的构造器，该构造器创建具有与输入排序集相同的元素和相同排序的新排序集。无法执行此建议，因为界面无法包含构造器。ComparatorCollectionSortedSet

import java.util.Objects;
import java.util.SortedSet;
import java.util.TreeSet;
class Student implements Comparable {
    int S_id;
    String S_name;
    int S_age;
    public Student() {
    }
    @Override
    public String toString() {
        return "Student{" +
                "S_id=" + S_id +
                ", S_name='" + S_name + ''' +
                ", S_age=" + S_age +
                '}';
    }

    public Student(int s_id, String s_name, int s_age) {
        S_id = s_id;
        S_name = s_name;
        S_age = s_age;
    }
    @Override
    public int compareTo(Object o) {
        //这里要检查o的类型的,省略了
       Student s= (Student)o;
        return this.S_id-s.S_id;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return S_id == student.S_id &&
                S_age == student.S_age &&
                S_name.equals(student.S_name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(S_id, S_name, S_age);
    }
}

public class SortedSetDemo {
    public static void main(String[] args) {
        SortedSetsortedSet=new TreeSet<>();
        sortedSet.add(new Student(1001,"扎根三",20));
        sortedSet.add(new Student(1008,"李四",20));
        sortedSet.add(new Student(1004,"王五",20));
        sortedSet.add(new Student(1007,"赵六",20));
        sortedSet.add(new Student(1009,"乾七",20));
        sortedSet.add(new Student(1012,"六八",20));
        for (Student s :
                sortedSet) {
            System.out.println(s);
        }

    }
}

SortedSet 接口实现类----TreeSet

继承实现关系----->
public class TreeSet extends AbstractSet
implements NavigableSet, Cloneable, Serializable

怎么没看到实现了SortedSet?,别急看这个
public interface NavigableSet extends SortedSet

TreeSet描述:
一种 NavigableSet实现基于 TreeMap. 元素使用它们的排列自然订购，或由 Comparator在集合创建时提供时间，取决于使用的构造函数。

此实现为基本的 log(n) 时间成本提供了保证操作（ add, remove和 contains).

请注意，此实现不是同步的。如果多个线程同时访问一个树集，并且至少有一个的线程修改集合，它必须是同步的外部。这通常是通过同步一些自然封装集合的对象。如果不存在这样的对象，则应使用 Collections.synchronizedSortedSet方法。这最好在创建时完成，以防止意外对集合的非同步访问：

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(…));

构造函数总结
TreeSet()
构造一个新的空树集，根据其元素的自然排序。

TreeSet(Collection c)
构造一个包含指定元素的新树集收集，根据排序自然排序的其元素。

TreeSet(Comparator comparator)
构造一个新的空树集，按照指定的排序比较器。

TreeSet(SortedSet s)
构造一个包含相同元素的新树集使用与指定排序集相同的顺序。

import java.util.Comparator;
import java.util.TreeSet;
class Animal implements Comparator {
    int A_id;
    String name;
    public Animal(int a_id, String name) {
        A_id = a_id;
        this.name = name;
    }
    @Override
    public String toString() {
        return "Animal{" +
                "A_id=" + A_id +
                ", name='" + name + ''' +
                '}';
    }
    @Override
    public int compare(Object o1, Object o2) {
        int result = ((Animal) o1).A_id - ((Animal) o2).A_id;
        return result;
    }
}
public class TreeSetDemo {
    public static void main(String[] args) {
//        一个空的构造
        TreeSet treeSet = new TreeSet<>();
        //构建包含指定集合中元素的新树集，根据其元素的自然顺序进行排序。
        TreeSet treeSet1 = new TreeSet<>(treeSet);
        Animal [] animal= new Animal[10];
        //实现Comparator接口

        TreeSet treeSet2 = new TreeSet<>((o1, o2) -> o1.A_id-o2.A_id);
        TreeSet treeSet3 = new TreeSet<>(Comparator.comparingInt(o -> o.A_id));
        for (int i = 0; i < animal.length; i++) {
            animal[i]=new Animal(i,"狗");
            treeSet3.add(animal[i]);
        }
        for (Animal a :
                treeSet3) {
            System.out.println(a);
        }
    }
}

注意:往set集合中放自定义数据时要注意实现compareable或者comparator接口,同事要实现hash和equals方法,在实际应用中有可能还需要实现序列化;

CopyonWriteArraySet

public class CopyOnWriteArraySet
extends AbstractSet implements Serializable

用于所有操作的内部副本执行列表的集。因此，它具有相同的基本属性：
它最适合设置大小通常保持小，仅读操作大大超过突变操作的应用程序，并且您需要防止在横穿过程中线程之间的干扰。
它是线程安全。
add set remove 操作（等）开销很大，因为它们通常需要复制整个底层阵列。
这个也是读读共享和CopyOnWriteArrayList基本一样;
还是看以下add 方法

重点在下面这个类----->>

ConcurrentSkipListSet

继承实现关系
public class ConcurrentSkipListSet
extends AbstractSet
implements NavigableSet, Cloneable, Serializable

描述:
可扩展的并发 NavigableSet实施基于一种 ConcurrentSkipListMap. 集合的元素被保留根据它们的自然顺序排序，或由 Comparator在设置创建时间提供，取决于在哪个构造函数上使用。

此实现提供预期的平均 log(n) 时间成本 contains, add，和 remove操作及其变体** 插入、移除和访问操作由多个线程安全地并发执行。**

与大多数集合不同， size方法不是恒定时间操作。由于这些集合的异步性质，确定当前数量 of elements 需要遍历元素，因此可能会报告如果在遍历期间修改此集合，则结果不准确。

底层是通过ConcurrentNavigableMap来实现的

private final ConcurrentNavigableMap m;

class PersonP implements Comparable {
    int P_ID;
    String name;
    int age;
    String gender;

    public PersonP() {
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        PersonP personP = (PersonP) o;
        return P_ID == personP.P_ID &&
                age == personP.age &&
                Objects.equals(name, personP.name) &&
                Objects.equals(gender, personP.gender);
    }

    @Override
    public int hashCode() {
        return Objects.hash(P_ID, name, age, gender);
    }

    public PersonP(int p_ID, String name, int age, String gender) {
        P_ID = p_ID;
        this.name = name;
        this.age = age;
        this.gender = gender;
    }

    @Override
    public int compareTo(Object o) {
        PersonP p = (PersonP) o;
        return this.P_ID - p.P_ID;
    }

    @Override
    public String toString() {
        return "PersonP{" +
                "P_ID=" + P_ID +
                ", name='" + name + ''' +
                ", age=" + age +
                ", gender='" + gender + ''' +
                '}';
    }
}

public class CurrentSkipListSetDemo {
    public static void main(String[] args) {
        //无参构造
        ConcurrentSkipListSet concurrentSkipListSet = new ConcurrentSkipListSet();
        concurrentSkipListSet.add(new PersonP(1001, "李四", 20, "男"));
        concurrentSkipListSet.add(new PersonP(1006, "王四", 22, "男"));
        concurrentSkipListSet.add(new PersonP(1004, "赵四", 21, "男"));
//取出数据
        for (PersonP p :
                concurrentSkipListSet) {
            System.out.println(p);
        }

        //        有参构造
        Set set = new HashSet<>();
        ConcurrentSkipListSet cSL = new ConcurrentSkipListSet(set);
        Comparator comparator = cSL.comparator();
        System.out.println("comparator = " + comparator);
        ConcurrentSkipListSet cSL2 = new ConcurrentSkipListSet((o1, o2) -> {
            if(o1 instanceof PersonP&&o2 instanceof PersonP){
                PersonP  per= (PersonP)o1;
                PersonP  per2= (PersonP)o1;
                return per.P_ID-per2.P_ID;
            }
          return  0;
        });
    }
}

想要搞清楚为什么 ConcurrentSkipListSet是线程安全的,那就需要看一下源码------>>>

我们平常说的线程安全大部分都是指读写,写写之间会出现的一些问题,读读之间没有什么影响;

简单的看了一些源码------>>

下面没有再继续分析,感兴趣你可以分析一下;

jdk1.5开始,Collection接口又增加了一个子接口 Queue

Queue 接口

继承实现关系---->>
public interface Queue extends Collection

描述:

专为在处理前保存元素而设计的集合。除了基本的收集操作外，队列还提供额外的插入、提取和检查操作。这些方法都以两种形式存在：一种是操作失败时抛出异常，另一种是返回特殊值（或者，取决于操作）。插入操作的后一种形式是专门为容量限制实现而设计的：在大多数实现中，插入操作不能失败。

Queue的子接口---->>>Deque

继承实现关系------>>>
public interface Deque extends Queue

描述:
支持两端元素插入和删除的线性集合。双端队列"的简称，通常发音为"甲板"。大多数实施对可能包含的元素数量没有固定限制，但此接口支持容量限制的 deque 以及没有固定大小限制的除数。Deque提供插入、删除和检查元素的方法。这些方法都以两种形式存在：一种是操作失败时抛出异常，另一种是返回特殊值（或者，取决于操作）。插入操作的后一种形式是专门为容量限制实现而设计的：在大多数实现中，插入操作不能失败。

方法:

接口中定义了一些方法,需要子类去实现,先看看ArrayDeque吧.

ArrayDeque

public class ArrayDeque
extends AbstractCollection
implements Deque, Cloneable, Serializable

描述:
可调整阵列实现。阵列偏点没有容量限制;它们根据需要生长以支持使用。它们不安全：在没有外部同步的情况下，它们不支持多个线程的并发访问。禁止使用空元素。

构造方法:

ArrayDeque的底层原理:

维护了数组,头部和尾部;
ArrayDeque的扩容原理-------->>

public class QueueDemo {
    public static void main(String[] args) {
        Dequedeque= new ArrayDeque<>();
        deque.add(0);
        System.out.println(deque.size());
        deque.addFirst(99);//可以向前插,也可以向后插
        deque.addLast(88);//add也是用到了addLast()
        System.out.println(deque.element());//返回第一个元素
        System.out.println(deque.getFirst());//头
        System.out.println(deque.getLast());//尾
        Iterator integerIterator = deque.descendingIterator();//得到一个倒叙的迭代器
        for (Iterator it = integerIterator; it.hasNext(); ) {
            Integer integer = it.next();
            System.out.print(integer+"");
        }
        System.out.println(deque);
        }
        }

ArrayDeque的优势:

此类在用作堆栈时可能比堆栈更快即比stack要快(因为Stack中的方法有些是加了锁的)，在用作队列时比链接列表快即比 linkedList要快,不用维护节点,底层是数组的形式;
大多数操作在摊销的恒定时间内运行。例外情况包括删除、删除第一次发生、删除上次事件、包含、重复器、删除（）和批量操作，所有这些操作都是在线性时间运行的。
ArrayDeque实现了先进先出或者先进后出,而Stack是先进后出;

public class QueueDemo {
    public static void main(String[] args) {
        Dequedeque= new ArrayDeque<>();
        //进栈
        deque.add(0);//tail
        deque.addLast(1);
        deque.addLast(2);
        deque.addFirst(3);
        deque.addFirst(4);
        deque.addFirst(5);
//      出栈
        deque.getFirst();
        deque.getLast();
        deque.poll();
        deque.pollFirst();
        deque.pollLast();
        //Stack
        Stackstack= new Stack<>();
        stack.add(1);
        stack.peek();

    }
}

ConcurrentlinkedDeque

继承实现关系------>>>
public class ConcurrentlinkedDeque
extends AbstractCollection
implements Deque, Serializable

无界并发双端队列基于链接节点。并发插入、移除和访问操作安全执行跨多个线程。一种 ConcurrentlinkedDeque是一个合适的选择，当许多线程将共享对公共集合的访问。像大多数其他并发集合实现一样，这个类不允许使用 null元素。

底层实现原理—>>节点

import java.util.Queue;
import java.util.concurrent.ConcurrentlinkedDeque;
public class ConcurrentlinkedDequeDemo {
    public static void main(String[] args) {
        Queue q= new ConcurrentlinkedDeque<>();
        q.add(1);//底层是用的offer，所以推荐用offer方法
        System.out.println(q.poll());//返回第一个并在队列中删除
        System.out.println(q.size());
        q.offer(2);
        System.out.println(q.peek());//返回第一个但是不删除
        System.out.println(q.element());//底层是peek方法,所以推荐用peek
        System.out.println(q.remove());//底层是poll方法
        q.offer(null);//抛异常
        System.out.println(q);
    }
}

Deque子接口----BlockingDeque接口

继承实现关系---->>
public interface BlockingDeque
extends BlockingQueue, Deque

另一种支持阻塞操作的Deque容器，在检索元素时等待Deque容器变为非空容器，在存储元素时等待Deque容器中有可用空间。

BlockingDeque方法有四种形式，具有不同的处理操作的方法，这些操作不能立即得到满足，但可能在将来的某个时候得到满足: 第一个抛出异常，第二个返回一个特殊值(null或false，取决于操作)，第三个阻塞当前线程，直到操作成功，第四个阻塞只有给定的最大时间限制，然后放弃。

linkedBlockingDeque

继承实现关系----->>
public class linkedBlockingDeque
extends AbstractQueue
implements BlockingDeque, Serializable
底层----->维护了节点,同时因为加了锁,可以保证线程安全;

import java.util.concurrent.BlockingDeque;
import java.util.concurrent.linkedBlockingDeque;

public class BlockingQueueDemo {
    public static void main(String[] args) {
//        默认创建一个Integer.MAX_VALUE大小的阻塞队列
        BlockingDeque bd=new linkedBlockingDeque<>()  ;
        System.out.println(bd.size());
        bd.add(1);
        bd.offer(2);
        bd.addFirst(3);
        bd.addLast(4);
        bd.offerFirst(5);
        bd.offerLast(10);
        bd.removeFirst();
        bd.removeLast();
        System.out.println(bd.size());
    }
}

import java.util.concurrent.linkedBlockingDeque;
public class linkedBlockingDequeDemo {   static  linkedBlockingDeque blockingDeque=new linkedBlockingDeque<>();
static{
    for (int i = 1; i < 1000; i++) {
        blockingDeque.offerFirst("第--"+i+"张票");
    }
}

    public static void main(String[] args) {
        for (int i = 0; i < 100; i++) {
            new Thread(()->{
                while (true){
                    String s = blockingDeque.pollFirst();
                    if(s==null) break;
                    System.out.println(s);
                }
            }).start();
        }

    }

}

linkedBlockingDeque与ArrayDeque对比

相同点:
1, 都是双向队列,都继承了Deque
不同点:

1,linkedBlokingDeque线程安全,而ArrayDeque不安全
ArrayDeque默认初始容量为16+1,而linkedBlockingDeque默认为Integer最大值;

linkedBlockingDeque是一个线程安全的双向队列
在Deque的体系结构，实现一个Deque可以使用数组（ArrayDeque），同时也可以使用链表（linkedList），还可以同实现一个支持阻塞的线程安全版本队列linkedBlockingDeque。

Queue 接口

继承实现关系----->
public interface Queue extends Collection

描述:
设计用于在处理之前保存元素的集合。除了基本款 Collection操作，队列提供额外的插入、提取和检查操作。这些方法中的每一种都以两种形式存在：一种是抛出异常如果操作失败，另一个返回一个特殊值（或者 null或者 false，取决于操作）。这后一种形式的插入操作是专门为与容量限制一起使用 Queue实施；多数情况实现，插入操作不会失败。

队列通常**（但不一定）对元素中的元素进行排序 FIFO（先进先出）方式。** 例外情况包括优先级队列，根据提供的元素对元素进行排序比较器，或元素的自然顺序，和 LIFO 队列（或堆栈）对元素 LIFO（后进先出）进行排序。

ConcurrentlinkedQueue

无界线程安全队列基于链接节点。该队列对元素 FIFO（先进先出）进行排序。的头部队列是已经在队列中的那个元素排队时间最长。的尾部队列是已经在队列中的那个元素排队时间最短。新元素插入到队列尾部，队列检索操作获取队列头部的元素。一种 ConcurrentlinkedQueue是一个合适的选择，当许多线程将共享对公共集合的访问。像大多数其他并发集合实现一样，这个类不允许使用 null元素。

此实现采用了高效的非阻塞基于在中描述的算法简单、快速、实用的非阻塞和阻塞并发队列算法 ;

import java.util.Queue;
import java.util.concurrent.ConcurrentlinkedQueue;

public class ConcurrentlinkedQueueDemo {
    public static void main(String[] args) {

        Queuelq= new ConcurrentlinkedQueue<>();
        Thread []threads=new Thread[10];
        for (int i = 0; i < 10; i++) {
          threads[i]=  new Thread(()->{
                for (int j = 0; j < 1000; j++) {
                    lq.offer(j);
                }
            });
        }
        for (int i = 0; i < threads.length; i++) {
            threads[i].start();
            try {
                threads[i].join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        System.out.println(lq.size());
    }
}

添加方法/移除基于CAS操做,所以效率是比较高的;

Queue 的子接口---->BlockingQueue

public interface BlockingQueue extends Queue

描述:
支持在检索元素时等待队列变得非空的操作的队列，以及在存储元素时等待队列中可用的空间。

BlockingQueue实现设计主要用于生产者-消费者队列，但还支持集合界面。因此，例如，可以从队列中删除任意元素。但是，此类操作通常执行效率不高，并且仅用于偶尔使用，例如当已排队的消息被取消时。remove(x)

BlockingQueue实现是线程安全的。所有排队方法都使用内部锁或其他形式的并发控制实现其原子效果。但是，批量收集操作，并且不一定以原子方式执行，除非在实施中另有说明。因此，例如，在只添加一些元素后，可能会失败（抛出一个例外）

class Producer implements Runnable {
   private final BlockingQueue queue;
   Producer(BlockingQueue q) { queue = q; }
   public void run() {
     try {
       while (true) { queue.put(produce()); }
     } catch (InterruptedException ex) { ... handle ...}
   }
   Object produce() { ... }
 }

 class Consumer implements Runnable {
   private final BlockingQueue queue;
   Consumer(BlockingQueue q) { queue = q; }
   public void run() {
     try {
       while (true) { consume(queue.take()); }
     } catch (InterruptedException ex) { ... handle ...}
   }
   void consume(Object x) { ... }
 }

 class Setup {
   void main() {
     BlockingQueue q = new SomeQueueImplementation();
     Producer p = new Producer(q);
     Consumer c1 = new Consumer(q);
     Consumer c2 = new Consumer(q);
     new Thread(p).start();
     new Thread(c1).start();
     new Thread(c2).start();
   }
 }

Queue的实现类---->

ArrayBlockingQueue

public class ArrayBlockingQueue extends AbstractQueue implements BlockingQueue, Serializable

描述:
有界阻塞队列。该队列对元素 FIFO（先进先出）进行排序。这头部队列的是已经在队列中的那个元素排队时间最长。的尾部队列是排队时间最短的元素。新元素插入到队列尾部，队列检索操作获取队列头部的元素。

这是一个经典的“有界缓冲区”，其中一个固定大小的数组包含生产者插入的元素和由消费者提取。一旦创建，容量就不能改变了。尝试去 put一个元素进入一个完整的队列会导致操作阻塞；尝试去 take一个来自空队列的元素同样会阻塞。

此类支持用于订购的可选公平策略等待生产者和消费者线程。默认情况下，此排序不保证。然而，一个用公平集构造的队列到 true按 FIFO 顺序授予线程访问权限。公平通常会降低吞吐量但会减少可变性并避免饥饿。

此类及其迭代器实现了所有可选的的方法 Collection和 Iterator接口。

构造方法—>>

public class ArrayBlockingQueueDemo {
    public static void main(String[] args) {
        //指定容量
        BlockingQueue blockingQueue = new ArrayBlockingQueue<>(3);
        blockingQueue.add(1);
        blockingQueue.add(2);
        blockingQueue.add(3);
        System.out.println(blockingQueue);

        blockingQueue.poll();//不保证先进先出原则
        blockingQueue.add(4);
        System.out.println(blockingQueue);
        blockingQueue.remove();//尝试从空队列中移除元素将同样阻塞
        System.out.println(blockingQueue);
        //设置为true,以保证先进先出
        BlockingQueue blockingQueue2 = new ArrayBlockingQueue<>(3, true);
        ArrayDeque arrayDeque = new ArrayDeque<>();
        BlockingQueue blockingQueue3 = new ArrayBlockingQueue<>(3, true, arrayDeque);
        blockingQueue3.add(1);
        blockingQueue3.add(1);
        blockingQueue3.add(1);

        System.out.println(blockingQueue3);
    }

进一步分析底层实现原理------->>>

入队和出队的源码分析---->>

import java.util.ArrayDeque;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

public class ArrayBlockingQueueDemo {
    public static void main(String[] args) {
        //指定容量
        BlockingQueue blockingQueue = new ArrayBlockingQueue<>(10);
        //添加10个元素
        for (int i = 0; i < 10; i++) {
            blockingQueue.add("a"+i);
        }
//满了之后在添加,add方法添加时报异常
       // boolean qq = blockingQueue.add("qq");//java.lang.IllegalStateException: Queue full
//        满了之后在添加,offer不报异常,返回添加成功或者失败
        boolean qq = blockingQueue.offer("qq");
//        往外取
        for (int i = 0; i < 10; i++) {
            blockingQueue.poll();
        }
//       取空之后
        System.out.println("取空之后再取为---"+blockingQueue.poll());//null
        System.out.println(blockingQueue.remove());//remove 则报异常
    }

}

如果对于容量没有限制,可以用linkedBlockingQueue;

linkedBlockingQueue; PriorityBlockingQueue

继承实现关系---->>>
public class PriorityBlockingQueue
extends AbstractQueue
implements BlockingQueue, Serializable

描述:
一个无界阻塞队列，使用与类相同的排序规则 PriorityQueue和用品阻止检索操作。虽然这个队列在逻辑上是无限制，尝试添加可能会因资源耗尽而失败（导致 OutOfMemoryError）。不允许 null元素。依赖优先级队列自然排序的也不允许插入不可比较的对象（这样做会导致 ClassCastException).

此类及其迭代器实现了所有可选的的方法 Collection和 Iterator接口。方法中提供的迭代器 iterator()和方法中提供的Spliterator spliterator(),不保证遍历 PriorityBlockingQueue 中的元素任何特定的顺序。如果您需要有序遍历，请考虑使用 Arrays.sort(pq.toArray()). 还有方法 drainTo能够用于删除按优先级顺序部分或全部元素和将它们放在另一个集合中。

浅谈java中容器的发展史之collection接口

Java相关栏目本月热门文章