集合

Collection

• 单列集合的顶层接口，没有实现类
• Collection接口有两个子接口Set(不可重复)和List（可重复）

Collection接口

1.继承了Iterable接口 迭代接口，拥有有迭代器Iterator对象

2.重写了Object类的equals和hashCode方法

3.定义了一系列待实现方法

//向集合中添加中添加一个元素，重写后根据集合类型进行限制
boolean add(E e)
//将指定集合中的所有元素添加到此集合中
boolean addAll(Collection<? extends E> c)
//清空集合
void clear()
//如果集合中包含指定元素返回true，如果指定元素是null也返回true
boolean contains(Object o)

boolean containsAll(Collection<?> c)
//如果该集合中包含指定集合中的所有元素的时候返回true。

boolean isEmpty()
//如果集合中没有元素返回true。

boolean remove(Object o)
//删除集合中的指定的元素。如果存在NULL，也删除。

boolean removeAll(Collection<?> c)
//删除当前集合中所有等于指定集合中的元素。

boolean retainAll(Collection<?> c)
//仅保留该指定集合中存在的所有元素。其余删除

int size()
//返回该集合中元素的个数。如果超过了Integer.MAX_VALUE，那么返回Integer.MAX_VALUE。

Object[] toArray()
//这个方法是集合和数组转化的桥梁。

//见名知意，返回包含此集合中所有元素的数组。如果这个集合的迭代器保证元素有序，那么该方法与其迭代器中元素顺序一致。并且该方法返回的数组是拷贝出来的(某些集合底层数组实现，区别这个)，可以进行任意的更改。

 T[] toArray(T[] a)
//该方法可以对返回的数组类型进行精确控制。而非像toArray方法一样返回Object[]。

//返回集合中所有元素到该数组中。如果这个数组可以容纳下的话，否则返回一个新new的数组，容量和集合中元素数量一致。如果指定的数组容量大于集合中元素个数，数组空闲位置填NULL。如果这个集合的Iterator具有顺序性的话，数组元素顺序与该迭代器一致。

List接口的特点：

继承了collection接口

（1）有序存储，指按索引下标存储

（2）可重复，可以存储null值

（3）部分子集合线程安全、部分不安全

（4）有索引，针对每个元素能够方便地查询和修改，

（5）判断元素是否重复依赖于equals方法，如果元素是系统类不需要重写，如果不是需要重写

（6）常用方法

void add(int index, E element) 
//指定 index 索引处理插入元素 element
boolean addAll(int index, Collection<? extends E> c) 
//在指定 index 索引处理插入集合元素 c
E remove(int index) 
//删除指定索引 index 处的元素
E set(int index, E element) 
//修改指定索引 index 处的元素为 element
E get(int index) + int size() 
//for循环遍历集合中的每一个元素
ListIterator listIterator() 
//通过列表迭代器遍历集合中的每一个元素
ListIterator listIterator(int index) 
//通过列表迭代器从指定索引处开始正向或者逆向遍历集合中的元素
E get(int index) 
//获取指定索引处的元素
int indexOf(Object o) 
//从左往右查找，获取指定元素在集合中的索引,如果元素不存在返回 -1
int lastIndexOf(Object o) 
//从右往左查找，获取指定元素在集合中的索引,如果元素不存在返回 -1
List subList(int fromIndex, int toIndex) 
// 截取从 fromIndex 开始到 toIndex-1 处的元素

Collection接口

1.继承了Iterable接口 迭代接口，拥有有迭代器Iterator对象

2.重写了Object类的equals和hashCode方法

3.定义了一系列待实现方法

//向集合中添加中添加一个元素，重写后根据集合类型进行限制
boolean add(E e)
//将指定集合中的所有元素添加到此集合中
boolean addAll(Collection<? extends E> c)
//清空集合
void clear()
//如果集合中包含指定元素返回true，如果指定元素是null也返回true
boolean contains(Object o)

boolean containsAll(Collection<?> c)
//如果该集合中包含指定集合中的所有元素的时候返回true。

boolean isEmpty()
//如果集合中没有元素返回true。

boolean remove(Object o)
//删除集合中的指定的元素。如果存在NULL，也删除。

boolean removeAll(Collection<?> c)
//删除当前集合中所有等于指定集合中的元素。

boolean retainAll(Collection<?> c)
//仅保留该指定集合中存在的所有元素。其余删除

int size()
//返回该集合中元素的个数。如果超过了Integer.MAX_VALUE，那么返回Integer.MAX_VALUE。

Object[] toArray()
//这个方法是集合和数组转化的桥梁。

//见名知意，返回包含此集合中所有元素的数组。如果这个集合的迭代器保证元素有序，那么该方法与其迭代器中元素顺序一致。并且该方法返回的数组是拷贝出来的(某些集合底层数组实现，区别这个)，可以进行任意的更改。

 T[] toArray(T[] a)
//该方法可以对返回的数组类型进行精确控制。而非像toArray方法一样返回Object[]。

//返回集合中所有元素到该数组中。如果这个数组可以容纳下的话，否则返回一个新new的数组，容量和集合中元素数量一致。如果指定的数组容量大于集合中元素个数，数组空闲位置填NULL。如果这个集合的Iterator具有顺序性的话，数组元素顺序与该迭代器一致。

LinkedList（顺序读取集合）

LinkedList是可以在任何位置高效插入和移除的有序序列，它是基于双向链表实现的。通过一个Node内部类实现链表结构，能够储存null，能够向前迭代还能向后迭代，在迭代过程中可以修改值、添加值、还能移除值。

LinkedList是继承与abstractSequentialList（顺序读取抽象类）的双向链表，它可以被当成堆栈、队列或双端队列进行操作。

LinkedList实现了List接口，能对它进行队列操作

LinkedList实现Deque接口，能当双端队列使用

实现了Cloneable接口，能克隆

实现了序列化接口，支持序列化传输

LinkedList是线程不安全的

LinkedList在进行查找的时候是需要进行遍历的，这是由于它的底层实现是链表。所以它的查询效果极差，而他的插入和删除性能好。

LinkedList继承了顺序读取抽象类abstractSequentialList，实现了List接口、Deque接口、Cloneable接口、序列化接口。

LinkedList有三个属性，实际元素个数，头结点，两个构造函数，

一个空参构造，一个有参（参数是Collection类型的集合）

public class LinkedList
extends AbstractSequentialList
implements List, Deque, Cloneable, java.io.Serializable
{
// 实际元素个数
transient int size = 0;
// 头结点
transient Node first;
// 尾结点
transient Node last;
}

Vector

是一个可变长数组，拥有两个迭代器：lterator 和ListIterator，发生fail-fast，而不是fail-safe。vector是一个线程安全的类

继承了abstractList类可以随机读取，实现了List接口，实现了randomAccess接口，使用for循环效率更高，没有实现的话迭代器效率更高。实现了cloneable接口，实现了序列化接口。

vector的大部分方法都加了synchronized，是一个线程安全类

两个属性

有四个构造方法

1.空构造，调用有参构造，初始化10

2.有参构造，int参数

3.有参构造（初始容量，扩容容量）

4.有参构造（collection集合）

常用方法：

1.add（e），向末尾添加

2.ensureCapacityHelper 没加锁，检查容量方法，让类中的其他方法能够多线程访问

3.grow 增加容量

stack栈

vector的子类，stack继承了vector，出栈、入栈、构造方法也是空的，用的也是数组，跟父类的扩增方式一样。线程安全

ArrayList和LinkedList总结

arrayList底层是用数组实现的顺序表，随机读取类型，可自动扩增，并且在初始化时，数组的长度是0，只有在增加元素的时候，长度才会增加。默认长度是10，不能无限增大，又上限。

LinkedList底层是一个双向链表，储存元素没有限制，直到内存满了再进行删除。

两个集合类型都是线程不安全类型，在使用Iterator迭代器的时候会发生，fail-fast，快速失效。

fail-fast

使用迭代器遍历的时候，有另外的线程堆ArrayList的存储数组进行了改变，Iterator就会报一个java.util.ConcurrentModificationException（并发修改异常）

在java.util.concurrent包下发生的都是fail-fast

fail-safe

在java.util.concurrent下的类，都是线程安全的类，在迭代过程中，如果有线程进行结构的改变，不会报异常，而是正常遍历，发生安全失败。

在concurrent下的集合类增加元素时使用arrays.copyOf(）来拷贝副本，在副本上增加元素，如果有其他线程进行改变集合的结构，是在副本上改变的，而不是在原集合上，而迭代器则是在遍历原集合，在遍历完后，改变原引用指向副本。此报下的类在进行增删时，会有一个副本，能防止fail-fast，这种机制不会出错，但是会发生fail-safe

vector发生fail-fast的原因是，它是针对原集合进行的，而concurrent类下的集合的增删时针对副本进行的。

vector线程安全，为什么在迭代时，还会有别的线程来改变其集合的结构呢？

在迭代的时候没有用到vector中的增删改查锁方法，这个锁其他线程可以使用，所以其他线程可以改变集合结构。

不使用vector的原因

1.每个方法都加锁，没必要，

2.多个thread执行一个加锁的方法，但是该方法中又有vector的存在，锁重复了

3.vector会发生快速失败，它也无法保证遍历安全，在遍历的时候还需要加锁

• Collection集合的遍历

  迭代器介绍

• 迭代器,集合的专用遍历方式

• Iterator iterator(): 返回此集合中元素的迭代器,通过集合对象的iterator()方法得到

• Iterator中的常用方法

  ? boolean hasNext(): 判断当前位置是否有元素可以被取出
  ? E next(): 获取当前位置的元素,将迭代器对象移向下一个索引位置

增强for循环【应用】

• 介绍

  • 它是JDK5之后出现的,其内部原理是一个Iterator迭代器
  • 实现Iterable接口的类才可以使用迭代器和增强for
  • 简化数组和Collection集合的遍历

• 格式

  ? for(集合/数组中元素的数据类型 变量名 : 集合/数组名) {

  ? // 已经将当前遍历到的元素封装到变量中了,直接使用变量即可

  ? }

  List集合

  List集合的概述和特点

  • List集合的概述

    • 有序集合,这里的有序指的是存取顺序
    • 用户可以精确控制列表中每个元素的插入位置,用户可以通过整数索引访问元素,并搜索列表中的元素
    • 与Set集合不同,列表通常允许重复的元素

  • List集合的特点

    • 存取有序

    • 可以重复

    • 有索引
      List集合的特有方法

      方法名	描述
      void add(int index,E element)	在此集合中的指定位置插入指定的元素
      E remove(int index)	删除指定索引处的元素，返回被删除的元素
      E set(int index,E element)	修改指定索引处的元素，返回被修改的元素
      E get(int index)	返回指定索引处的元素

List集合子类的特点

• ArrayList集合

  ? 底层是数组结构实现，查询快、增删慢

• LinkedList集合

  ? 底层是链表结构实现，查询慢、增删快

LinkedList集合的特有功能

• 特有方法

  方法名	说明
  public void addFirst(E e)	在该列表开头插入指定的元素
  public void addLast(E e)	将指定的元素追加到此列表的末尾
  public E getFirst()	返回此列表中的第一个元素
  public E getLast()	返回此列表中的最后一个元素
  public E removeFirst()	从此列表中删除并返回第一个元素
  public E removeLast()	从此列表中删除并返回最后一个元素

Set集合概述和特点

• 不可以存储重复元素
• 没有索引,不能使用普通for循环遍历

TreeSet集合概述和特点

TreeSet的底层数据结构是红黑树

• 不可以存储重复元素
• 没有索引
• 可以将元素按照规则进行排序
  • TreeSet()：根据其元素的自然排序进行排序
  • TreeSet(Comparator comparator) ：根据指定的比较器进行排序

自然排序Comparable的使用

实现步骤

1. 使用空参构造创建TreeSet集合

   • 用TreeSet集合存储自定义对象，无参构造方法使用的是自然排序对元素进行排序的

2. 自定义的Student类实现Comparable接口

   • 自然排序，就是让元素所属的类实现Comparable接口，重写compareTo(T o)方法

3. 重写接口中的compareTo方法

   • 重写方法时，一定要注意排序规则必须按照要求的主要条件和次要条件来写

   • 代码实现

     public class Student implements Comparable{
         private String name;
         private int age;
     
         public Student() {
         }
     
         public Student(String name, int age) {
             this.name = name;
             this.age = age;
         }
     
         public String getName() {
             return name;
         }
     
         public void setName(String name) {
             this.name = name;
         }
     
         public int getAge() {
             return age;
         }
     
         public void setAge(int age) {
             this.age = age;
         }
     
         @Override
         public String toString() {
             return "Student{" +
                     "name='" + name + '\'' +
                     ", age=" + age +
                     '}';
         }
     
         @Override
         public int compareTo(Student o) {
             //按照对象的年龄进行排序
             //主要判断条件: 按照年龄从小到大排序
             int result = this.age - o.age;
             //次要判断条件: 年龄相同时，按照姓名的字母顺序排序
             result = result == 0 ? this.name.compareTo(o.getName()) : result;
             return result;
         }
     }
     

     测试类

     public class MyTreeSet2 {
         public static void main(String[] args) {
             //创建集合对象
             TreeSet ts = new TreeSet<>();
     	    //创建学生对象
             Student s1 = new Student("zhangsan",28);
             Student s2 = new Student("lisi",27);
             Student s3 = new Student("wangwu",29);
             Student s4 = new Student("zhaoliu",28);
             Student s5 = new Student("qianqi",30);
     		//把学生添加到集合
             ts.add(s1);
             ts.add(s2);
             ts.add(s3);
             ts.add(s4);
             ts.add(s5);
     		//遍历集合
             for (Student student : ts) {
                 System.out.println(student);
             }
         }
     }
     

比较器排序Comparator的使用

• 用TreeSet集合存储自定义对象，带参构造方法使用的是比较器排序对元素进行排序的

• 比较器排序，就是让集合构造方法接收Comparator的实现类对象，重写compare(T o1,T o2)方法

• 重写方法时，一定要注意排序规则必须按照要求的主要条件和次要条件来写

• 代码实现

  public class Teacher {
      private String name;
      private int age;
  
      public Teacher() {
      }
  
      public Teacher(String name, int age) {
          this.name = name;
          this.age = age;
      }
  
      public String getName() {
          return name;
      }
  
      public void setName(String name) {
          this.name = name;
      }
  
      public int getAge() {
          return age;
      }
  
      public void setAge(int age) {
          this.age = age;
      }
  
      @Override
      public String toString() {
          return "Teacher{" +
                  "name='" + name + '\'' +
                  ", age=" + age +
                  '}';
      }
  }
  

  测试类

  public class MyTreeSet4 {
      public static void main(String[] args) {
        	//创建集合对象
          TreeSet ts = new TreeSet<>(new Comparator() {
              @Override
              public int compare(Teacher o1, Teacher o2) {
                  //o1表示现在要存入的那个元素
                  //o2表示已经存入到集合中的元素
                
                  //主要条件
                  int result = o1.getAge() - o2.getAge();
                  //次要条件
                  result = result == 0 ? o1.getName().compareTo(o2.getName()) : result;
                  return result;
              }
          });
  		//创建老师对象
          Teacher t1 = new Teacher("zhangsan",23);
          Teacher t2 = new Teacher("lisi",22);
          Teacher t3 = new Teacher("wangwu",24);
          Teacher t4 = new Teacher("zhaoliu",24);
  		//把老师添加到集合
          ts.add(t1);
          ts.add(t2);
          ts.add(t3);
          ts.add(t4);
  		//遍历集合
          for (Teacher teacher : ts) {
              System.out.println(teacher);
          }
      }
  }
  

两种比较方式总结

• 两种比较方式小结
  • 自然排序: 自定义类实现Comparable接口,重写compareTo方法,根据返回值进行排序
  • 比较器排序: 创建TreeSet对象的时候传递Comparator的实现类对象,重写compare方法,根据返回值进行排序
  • 在使用的时候,默认使用自然排序,当自然排序不满足现在的需求时,必须使用比较器排序
• 两种方式中关于返回值的规则
  • 如果返回值为负数，表示当前存入的元素是较小值，存左边
  • 如果返回值为0，表示当前存入的元素跟集合中元素重复了，不存
  • 如果返回值为正数，表示当前存入的元素是较大值，存右边

HashSet集合

• 底层数据结构是哈希表

• 存取无序

• 不可以存储重复元素

• 没有索引,不能使用普通for循环遍历

  哈希值

• 哈希值简介

  ? 是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值，通过对象地址获得或者自己重写哈希方法，HashSet集合存储自定义类型元素,要想实现元素的唯一,要求必须重写hashCode方法和equals方法

• 如何获取哈希值

  ? Object类中的public int hashCode()：返回对象的哈希码值

• 哈希值的特点

  • 同一个对象多次调用hashCode()方法返回的哈希值是相同的
  • 默认情况下，不同对象的哈希值是不同的。而重写hashCode()方法，可以实现让不同对象的哈希值相同

哈希表结构

• JDK1.8以前

  ? 数组 + 链表

• JDK1.8以后

  • 节点个数少于等于8个

    ? 数组 + 链表

  • 节点个数多于8个

    ? 数组 + 红黑树

Map集合

• Map集合概述

  interface Map  K：键的类型；V：值的类型
  

• Map集合的特点

  • 双列集合,一个键对应一个值
  • 键不可以重复,值可以重复

? Map集合的基本功能

Map集合的获取功能

HashMap集合概述和特点

• HashMap底层是哈希表结构
• 依赖hashCode方法和equals方法保证键的唯一
• 如果键要存储的是自定义对象，需要重写hashCode和equals方法

TreeMap集合概述和特点

• TreeMap底层是红黑树结构
• 依赖自然排序或者比较器排序,对键进行排序
• 如果键存储的是自定义对象,需要实现Comparable接口或者在创建TreeMap对象时候给出比较器排序规则

创建不可变集合

方法介绍

• 在List、Set、Map接口中,都存在of方法,可以创建一个不可变的集合
  • 这个集合不能添加,不能删除,不能修改
  • 但是可以结合集合的带参构造,实现集合的批量添加
• 在Map接口中,还有一个ofEntries方法可以提高代码的阅读性
  • 首先会把键值对封装成一个Entry对象,再把这个Entry对象添加到集合当中