目录导读

• Collection
• List
• Set
• Queue

1.Collection集合的操作

(1)增

boolean add(Object o); //添加单个元素
boolean addAll(Collection c); //将c中的所有元素添加至this对应的集合中，类似于复制

(2)删

void clear(); //清空集合
boolean remove(Object o); //删除指定元素o，有多个o时，只删除第一个
boolean removeAll(Collection c);// 差集。从集合中删除c里包含的元素
boolean retainAll(Collection c); //交集。从集合中删除c里不包含的元素

(3)判断

boolean contains(Object o); // 判断是否包含o元素
boolean containsAll(Collection c); //判断是否包含c中所有的元素
boolean isEmpty(); //叛空

(4)获取

int size(); //返回集合元素的个数 

注意：
    数组[]是length属性
    字符串是length()方法
    集合是size()方法

Iterator iterator(); //返回Iterator对象，用于遍历集合

(5)转换

Object[] toArray(); //把集合元素转换为数组，底层是

(6)遍历

1.迭代器Iterator遍历

//如
Collection c = new ArrayList();
Iterator it = c.iterator();
while(it.hasNext()) {
    System.out.println(it.next());
}

2.foreach循环遍历
3.Java8新增的方法：forEachRemaining(Consumer action)

2.List集合

• ArrayList
• LinkedList
• Vector(可以忽略不记忆)

1) List 集合的通用情况

由于List集合是有序的，因此它的方法体系里多了一些利用索引操作集合的方法。除了同Collection部分的方法外，下面只展示不同的部分

(1)增

void add(int index, Object element); //将元素element插入到List集合的index处
boolean addAll(int index, Collection c); //将集合c中的所有的元素插入到List集合的index处

(2)删除

Object remove(int index); //删除并返回index处的元素
注意：List集合中判断两个对象是否相等是通过equals()方法返回true即可认为它们是相等的

(3)获取

Object get(int index); //返回集合index索引处的元素
int indexOf(Object o); //返回元素o在集合List中首次出现的索引
int lastIndextOf(Object o); //返回元素o在集合List中最后一次出现的索引
List subList(int fromIndex, int toIndex); //返回集合List中[fromIndex, toIndex)的元素组成的子集合
ListIterator<E> listIterator(); //双向迭代器
    ListIterator方法：
    · void add(E e); //增
    · void remove(); //删
    //向后遍历
    · boolean hasNext();
    · E next();
    //想前遍历
    · boolean hasPrevious();
    · E previous();

(4)修改

Object set(int index, Object element);//将index处的元素替换为element，返回被替换的元素

(5)遍历

1.普通for循环遍历，因为有get(int index)方法
2.foreach循环
3.迭代器

Iterator(后向迭代)
ListIterator(双向迭代)

(6)Java8新增方法

void sort(Comparator c); //根据Comparator参数对List集合的元素进行排序
void replaceAll(UnaryOperator operator); // 根据operator指定的计算规则重新设置List集合的所有元素

2) ArrayList 和 Vector 集合

支持的操作同List，自己没有什么单独的特色了。
ArrayList 和 Vector 集合的区别？

同：
  1.ArrayList和Vector是底层是基于数组实现的，它们封装了一个动态的允许再分配的Object[]数组。
  2.数组的默认长度为10,也可以在创建时指定长度

异：
  1.Vector：是古老的类，方法名称很长，缺点很多(一般不建议使用该类)，是线程安全的(故性能低)
  2.Vector有个子类Stack，是模拟'栈'的，也是线程安全、性能差的，同样不建议使用它来模拟栈
  3.ArrayList：是线程不安全的(性能稍高，可用Collections工具类将其包装成线程安全的)  
   注意：
    在Arrays工具类中，有个'static <T> List<T> asList(T... a)' 方法，该方法可以把一个数组或指定个数的对象转换为一个List集合，但这个List集合并不是ArrayList或Vector集合
的实例，而是Arrays的内部类ArrayList的实例，即Arrays$ArrayList

3) LinkedList 集合

LinkedList集合实现了List接口(故是个List集合)，同时也实现了Deque接口(故可以被当成双端队列来使用)，因此，LinkedList即可以当成'栈'用也可以当成'队'使用。

(1)当成List集合

方法同List的方法

注意：
    由于底层是基于链表实现的，所以，get(int index) 方法的执行效率并不高，时间为 O(N)

(2)当成栈

//增
void push(E e); //栈顶添加元素
//删
E poll(); // 栈顶元素出栈
E pollFirst(); //取出栈的第一个元素 
E pollLast(); //取出栈的最后一个元素

(3)当成队

//增
boolean offer(E e); //队尾添加元素
boolean offerFirst(E e); //对头添加
boolean offerLast(E e); //队尾添加

小分析：
  LinkedList(底层是链表实现)与ArrayList(数组实现)、ArrayDeque(数组实现)的实现机制完全不同，LinkedList的随机访问(作为List集合的特点)集合元素的性能较差，但在插入和删除元素时性能出色。ArrayList和ArrayDeque的随机访问性能较好。
  Vector虽然底层也是数组实现，但由于要实现线程同步(且实现机制还不好)，所以性能很差。

3.个List实现类的性能分析

List就是一个线性表接口，而ArrayList,LinkedList又是两种典型实现。

ArrayList是基于数组实现的，因此，它的随机访问性能比较好。适合在访问多于插入删除的场合

LinkedList是基于链表实现的，因此插入、删除性能较好，但是访问性能就不如ArrayList了。适合用于插入删除较多的场合

对于集合的遍历：
  ArrayList集合应该采用随机访问的方法来遍历
  LinkedList集合应该采用迭代器(Iterator)来遍历

4.Set集合

• HashSet(线程不安全)
• LinkedHashSet(线程不安全)
• TreeSet(内容较多, 线程不安全)
• EnumSet(有序, 线程不安全)

Set集合其实是由Map集合实现来的，value全为null的键值对

Set集合类似于一个瓶子，里面的元素没有顺序，且不允许元素重复，它的操作同Collection一样，并没有增加什么多余的方法

1.HashSet 集合类(重要)

- HashSet的底层是基Hash算法来存储集合中的元素，因此具有很好的存取和查找性能
- 元素无序，线程不安全
- 集合的元素可以为null

HashSet中添加元素的步骤：
  存入一个元素时，HashSet会调用该对象的hashCode()方法以获得该对象的hashCode值，然后根据这个值决定该对象存放的位置。 
  注意：
    1.我们认为的元素重复(字面内容重复就行)和HashSet中认为的元素重复(equals()和hashCode()方法都相等)是不一样的。
    2.在HashSet中如果两个对象通过equals()返回true,但它们的hashCode()返回值不一样，就会造成两个"一样的"的元素可以添加成功，这就与Set集合的特点(元素不重复)矛盾了。因此，当要重写HashSet的equals()方法时，其hashCode()方法也应该重写，而且返回值要一致。
    3.如果两个对象通过equals()返回false, 但它们的hashCode()返回值一样,那就会造成所谓的冲突(数据结构中有讲)，那么会处理冲突(如使用链地址法)，这样就会使得HashSet的性能下降。

2.LinkedHashSet 集合类

- 是HashSet的子类。也是根据元素的hashCode值来决定元素的存储位置，但同时也使用了链表来维护元素的添加次序，因此性能略低于HashSet集合
- 底层是基于Hash算法来存储元素，用链表来维护元素的有序

注意：
1.尽管LinkedHashSet是有序的(用链表维护插入顺序)，但它本质仍是HashSet集合，是靠hashCode值来决定存储位置的，因此，其内的元素是不允许重复的。
2.由于是用链表来维护内部顺序的，因此在迭代访问Set里的全部元素时将有很好的性能。

3.TreeSet 集合类

是SortedSet接口的实现类，可以保正元素处于排序的状态(注意，不是有序哦)。

底层是基于红黑树的数据结构来实现的数据存储及排序。

独有的几个方法(因为有序才增加了这些方法):
Comparator comparator(); //如果Treeset采用了定制排序，则该方法返回定制排序所使用的Comparator;如果采用的是自然排序，则返回null
Object first(); //返回集合中的第一个元素
Object last(); //返回集合中的最后一个元素
Object lower(Object e); //返回集合中位于e元素之前的元素，e可以不是集合中的元素
Object higher(Object e); //返回集合中位于e元素之后的元素，e可以不是集合中的元素
SortedSet subSet(Object fromElement, Object toElement); //返回[fromElement, toElement)的子集
SortedSet headSet(Object toElement); //返回所有小于toElement的子集
SortedSet tailSet(Object fromElement); //返回所有大于或等于fromElement的元素

TreeSet的两种排序方式：

自然排序(升序排序)
定制排序

实现：

1.自然排序(升序排序) —— 元素具备比较性
  使用TreeSet的无参构造器
            
当采用自然排序时，TreeSet会调用集合元素的compareTo(Object obj)方法来比较元素之间的大小关系，然后将元素安升序排列。这中方式就是自然排序。      
  注：
    1.这个compareTo(Object obj)方法是Comparable接口(java.lang包下的)的方法，要想加入TreeSet集合里，那么该对象须实现Comparable接口(只有添加的第一个对象可以不用实现Comparable接口？实验过了，还是会报错啊)，否则会报错java.lang.ClassCastException
    
//如何让自定义集合元素实现Comparable接口
public class Student implements Comparable {
  ...
  //重写compareToe()方法,根据年龄大小来比较
  public int compareTo(Object o) {
    Student s = (Student)o;
     return this.age - s.age;
  }
}

//集合添加元素 
public class TreeSetDemo {
  public static void main(String[] args) {
    TreeSet<Student> tr = new TreeSet<Student>();
    Student s1 = new Student("小明", 12);
    Student s1 = new Student("小江", 14);
    tr.add(s1);
    tr.add(s2); 
    System.out.println(tr); 
  }
}                   
    2.TreeSet中添加元素，判断两个元素是否相等唯一标准就是compareTo(Object o)是否返回0，与equals()方法无关
    3.自定义类中，重写equals()和compareTo(Object o)方法应该具有相一致的比较结果。
    4.实现了Comparable接口的常用类：
        - BigDecimal, BigInteger, 各种数值类型的包装类
        - Character 
        - Boolean(true > false)
        - String
        - Date, Time

2.定制排序 —— 集合具备比较性
通过Comparator接口的帮助，该接口里有 int compare(T o1, T o2)方法，用于比较o1与o2的大小。利用TreeSet的这个构造器  TreeSet(Comparator<? super E> comparator) 传入Comparator的实现类实例即可。

注意：
    TreeSet判断两个对象是否相等的唯一标准是：通过compare()方法返回值是否为0。       
//如下代码示例
public class TreeSetDemo {
  public static void main(String[] args) {
    TreeSet<String> tr = new TreeSet<String>(new MyComparator());
    tr.add("hello");
    tr.add("world"); //长度和“hello”相等，会当成是重复元素，故不会被添加进去
    tr.add("xi");
    tr.add("dian");
    System.out.println(tr); //[xi, dian, hello]
   }
}

//实现的Comparator接口
class MyComparator implements Comparator<String> {
  public int compare(String s1, String s2) {
    return s1.length() - s2.length();
  }
}

4.EnumSet 集合类

是专门为枚举类设计的集合类, 集合元素有序，是按枚举类内定义的顺序来决定集合的元素顺序的

集合元素不能为null, 加入null时会报错，判断是否有null元素及删除null元素时都不会抛异常

EnumSet可以将一个枚举类中全部或部分枚举值放入其中，并且是有序的(顺序同枚举类中的顺序) 。也可以将一个Collection集合的所有元素来创建新的EnumSet, 前提是该Collection集合中的元素是同一个枚举类的枚举值。

一句话总结：能放入EnumSet集合中的元素只能是枚举类的枚举值

5.各Set实现类的性能分析

HashSet和TreeSet是Set的两个典型的实现类。这这两个如何选择呢？
1.HashSet的性能总是比TreeSet好，特别是元素的存储(添加)和查找，查找性能O(1), 结合数据结构知识来理解
2.TreeSet需要额外的红黑树算法来维护集合的有序性，因此性能不如HashSet。只有当需要保持Set的有序性时才选择用它，否则都首选HashSet
3.EnumSet是Set实现类中性能最好的(HashSet可能会处理冲突，因此性能略低),但它只能存放同一枚举类的枚举值

6.Queue集合

• PriorityQueue
• ArrayDeque
• LinkedList

用于模拟队列这种数据结构，队列不允许随机访问队列中的元素，因此，该集合不存在按索引访问集合元素的任何方法

模拟队列的特性，设计的几个独特的操作方法：
//增
void add(Object e); //将指定元素添加至队尾
boolean offer(Object e); //将指定元素添加至队尾，当使用有容量限制的队列时，该方法通常比add()好
//删 
Object peek(); //获取队头元素，注意不是删除，若队为空，则返回null
Object element(); //获取队头的元素，注意不是删除啊,若队为空,会引发NoSuchElementException异常
Object poll(); //获取队头元素，并删除，若队为空，则返回null
Object remove(); //获取队头元素，并删除，如队为空，会引发NoSuchElementException异常

1) PriorityQueue 集合

- 存入该集合中的元素并不是按先后顺序存放，基本是按元素大小的顺序存放。但是执行，将元素一个一个取出时，却是按从小到大的顺序依次取出的
- PriorityQueue不允许添加null元素

PriorityQueue有两种排序方式：自然排序、定制排序`
实现方式同TreeSet一样
PriorityQueue(int initialCapacity, Comparator<? super E> comparator) 

2)Deque 接口与 ArrayDeque 实现类

Deque接口是Queue接口的子接口，它代表一个双端队列，可以用来模拟 队，栈

基于此，这个接口里定义了一些从两端来操作队列的元素:

当成栈

//增
void push(E e); //栈顶添加元素
//删
E poll(); // 栈顶元素出栈
E pollFirst(); //取出栈的第一个元素 
E pollLast(); //取出栈的最后一个元素

当成队

//增
void addFirst(Object o);
void addLast(Object o);
boolean offer(E e); //队尾添加元素
boolean offerFirst(E e); //对头添加
boolean offerLast(E e); //队尾添加

(1)ArrayDeque集合
基于数组实现的双端队列,底层封装了一个动态数组Object[]
创建Deque时可以指定Object[]数组大小，默认长度为16
        
注：
  1.可以用ArrayDeque来模拟栈这种数据结构，不要使用Stack类(Vector的子类)来模拟
  2.也可以用ArrayDeque来模拟队这种数据结构

3.LinkedList 集合类

LinkedList实现了Deque接口和List接口，因此，它同时具有这两个集合类的特性。

可以被当成：
(1)List集合
    注：可以用索引来访问集合元素，但性能不佳，因为底层是链表实现的
(2)栈
(3)双队列