1. 集合框架概述

1.1 集合与数组的对比

• 一方面，面向对象语言对事物的体现都是以对象的形式，为了方便对多个对象的操作，就要对对象进行存储。另一方面，使用Array存储对象方面存在一些弊端，而Java集合就像一种容器，可以动态地把多个对象的引用放入容器中。

  • 数组在内存存储方面的特点

    • 数组初始化以后，长度就确定了
    • 数组声明的类型，就决定了进行元素初始化时的类型

  • 数组在存储数据方面的弊端

    • 数组初始化以后长度不可变，不便于扩展
    • 数组中提供的属性和方法少，不便于进行添加、删除、插入等操作，且效率不高，同时无法直接获取存储元素的个数
    • 数组存储的数据是有序的、可以重复的，存储数据的特点单一
• Java集合类可以用于存储数量不等的多个对象，还可以用于保存具有映射关系的关联数组

1.2 集合常用API

Java集合可分为Collection和Map两种体系：

• Collection接口：单列数据，定义了存取一组对象的方法的集合

  • List：元素有序、可重复的集合（动态数组）

    • ArrayList、LinkList、Vector

  • Set：元素无序、不可重复的集合（）

    • HashSet、LinkedHashSet、TreeSet

• Map接口：双列数据，保存具有映射关系“key-value”的集合

  • HashMap、LinkedHashMap、TreeMap、HashTable、Properties

1.3 Collection接口中的常用方法

为了使得Collection类中的一些方法可以返回预期结果，建议添加的数据重写了equals()方法

• add(Object e)：将元素e添加到集合中
• size()：获取添加的元素的个数
• addAll(Collection coll)：将coll集合中的元素添加到当前集合中
• isEmpty()：判断当前集合是否为空
• clear()：清空集合元素

@Test
public void test1() {
    Collection collection1 = new ArrayList();
    collection1.add("AA");
    collection1.add("BB");
    collection1.add("CC");
    collection1.add(123);
    collection1.add(new Date());

    System.out.println(collection1.size());

    Collection collection2 = new ArrayList();
    collection2.addAll(collection1);
    System.out.println(collection2.size());
    System.out.println(collection1.isEmpty());
    collection1.clear();
    System.out.println(collection1.isEmpty());
}

• contains(Object obj)：判断一个对象是否包含在集合中
• containsAll(Collection coll1)：判断形参coll1中的所有元素是否都在当前集合中

@Test
public void test() {
    Collection coll = new ArrayList();
    coll.add(123);
    coll.add(456);
    coll.add("123");
    coll.add(new Person("hxuanyu", 123));
    coll.add(false);
    Collection coll1 = new ArrayList();
    coll1.add(123);
    coll1.add(456);

    // contains(Object obj) ，对于对象，内部使用equals()进行判断
    System.out.println("coll.contains(123): " + coll.contains(123));
    System.out.println("coll.contains(\"123\"): " + coll.contains("123"));
    System.out.println("coll.contains(new String(\"123\")): " + coll.contains(new String("123")));
    System.out.println("coll.containsAll(coll1): " + coll.containsAll(coll1));

}

运行结果：

coll.contains(123): true
coll.contains("123"): true
coll.contains(new String("123")): true
coll.containsAll(coll1): true

• remove(Object obj)：移除某个元素，移除成功则返回true
• removeAll(Collection coll1)：从当前集合中删除coll1中有的元素（差集运算）

@Test
public void test1() {
    Collection coll = new ArrayList();
    coll.add(123);
    coll.add(456);
    coll.add("123");
    coll.add(new Person("hxuanyu", 123));
    coll.add(false);
    Collection coll1 = new ArrayList();
    coll1.add(123);
    coll1.add(456);

    System.out.println("coll.removeAll(coll1): " + coll.removeAll(coll1));
    System.out.println("coll.remove(123): " + coll.remove(123));
}

运行结果：

coll.removeAll(coll1): true
coll.remove(123): false

• retainAll(Collection coll1)：获取当前集合与coll1的交集，并返回给当前集合
• equals(Object obj)：判断两个集合中的元素是否相同（内容相同，在有序列表中顺序也需相同）

@Test
public void test2() {
    Collection coll = new ArrayList();
    coll.add(123);
    coll.add(456);
    coll.add("123");
    coll.add(new Person("hxuanyu", 123));
    coll.add(false);

    Collection coll1 = new ArrayList();
    coll.add(123);
    coll.add(456);
    coll.add("123");

    Collection coll2 = Arrays.asList(123, "abc", "hello", false);

    coll1.retainAll(coll);
    System.out.println(coll1.toString());
    System.out.println("coll.equals(coll2): " + coll.equals(coll2));
}

运行结果：

[]
coll.equals(coll2): false

• hashCode()：返回当前对象的哈希值
• toArray()：将集合转换为对象数组
• Arrays.asList()：将数组转换为列表，注意参数列表中如果使用基本数据类型的数组，则会识别为只有一个数组元素的列表，如果使用包装类对象的数组，则可以正常转换为对应的列表。

@Test
public void test3() {
    Collection coll = new ArrayList();
    coll.add(123);
    coll.add(456);
    coll.add("123");
    coll.add(new Person("hxuanyu", 123));
    coll.add(false);
    System.out.println("coll.hashCode(): " + coll.hashCode());

    Object[] objects = coll.toArray();
    for (Object object : objects) {
        System.out.println(object);
    }

    List<Object> objectList = Arrays.asList(objects);
    List<int[]> list = Arrays.asList(new int[]{1, 2, 3});
    System.out.println("list.size(): " + list.size());

    List list1 = Arrays.asList(new Integer[]{1, 2, 3});
    System.out.println("list1.size(): " + list1.size());


}

运行结果：

coll.hashCode(): 1735702141
123
456
123
Person{name='hxuanyu', age=123}
false
list.size(): 1
list1.size(): 3

2. 集合元素的遍历

2.1 使用Iterator接口

• Iterator对象称为迭代器（设计模式的一种）主要用于遍历Collection集合中的元素。
• GOF给迭代器的定义为：提供一种方法访问一个容器对象中各个元素，而又不暴露该对象的内部细节。迭代器模式，就是为容器而生。类似于“公交车上的售票员”、“火车上的乘务员”、“空姐 ”
• Collection接口继承了java.lang.Iterable接口，该接口有一个iterator()方法，那么所有实现了Collection接口的集合类都有一个iterator()方法，用以返回一个实现了Iterator接口的对象。
• Iterator仅用于遍历集合，Iterator本身并不提供承装对象的能力。如果需要创建Iterator对象，则必须有一个被迭代的集合
• 集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前
• 内部定义了remove()方法，可以在遍历集合时删除集合中的元素。此方法不同于集合直接调用remove()方法

@Test
public void test1() {
    Collection coll = new ArrayList();
    coll.add(123);
    coll.add(456);
    coll.add("123");
    coll.add(new Person("hxuanyu", 123));
    coll.add(false);
    Iterator iterator = coll.iterator();
    // 开发中推荐写法
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}

运行结果：

123
456
123
Person{name='hxuanyu', age=123}
false

iterator的错误写法：

while(iterator.next() != null){
    System.out.println(iterator.next());
}

这种写法会导致丢失元素，同时遍历到结尾会出现异常

while (coll.iterator().hasNext()) {
    System.out.println(iterator.next());
}

这种写法会导致出现死循环，因为每次循环条件中都会重新生成一个迭代器对象，新的迭代器对象的指针将默认位于集合的第一个元素之前。

remove()方法的使用：

@Test
public void test3() {
    Collection coll = new ArrayList();
    coll.add(123);
    coll.add(456);
    coll.add("123");
    coll.add(new Person("hxuanyu", 123));
    coll.add(false);
    Iterator iterator = coll.iterator();
    while (iterator.hasNext()) {
        Object obj = iterator.next();
        if ("123".equals(obj)) {
            iterator.remove();// 移除元素
        }
    }
    iterator = coll.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }

}

• iterator可以删除集合的元素，但是遍历过程中是通过迭代器对象的remove()方法，而不是集合对象的remove()方法。
• 如果还未调用next()或在上一次调用next()后已经调用了remove()，再调用remove()会报IllegalStateException

2.2 foreach新特性

• Java5.0提供了foreach循环迭代访问Collection数组。
• 遍历操作不需要获取Collection或数组长度，无需使用索引访问元素。
• 遍历集合的底层调用iterator完成操作。
• foreace还可以用来遍历数组。

public void test1() {
    Collection coll = new ArrayList();
    coll.add(123);
    coll.add(456);
    coll.add("123");
    coll.add(new Person("hxuanyu", 123));
    coll.add(false);
    
    // for（集合元素变量类型 局部变量 : 集合对象）
    for (Object obj : coll) {
        System.out.println(obj);
    }
}

@Test
public void test2() {
    int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7};// 遍历数组
    for (int i : arr) {
        System.out.println(i);
    }
}

过程：

foreach循环会在内部依次获取集合中的元素赋值给局部变量，并在之后的每一次调用都把游标后移一位，直到遍历完集合中的所有元素。底层也使用了迭代器

注意：增强循环遍历数组时会将数组元素重新赋值给一个局部变量，如果在内部对该变量进行修改，则不会影响原有数组的值。

3. List接口

3.1 List接口概述

• 鉴于Java中数组用来存储数据的局限性，我们通常使用List代替数组
• List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引。
• List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据 序号存取容器中的元素。
• JDK API中List接口的实现类常用的有：ArrayList、LinkedList和Vector。

ArrayList、LinkedList、Vector的异同：

• 不同点：

  • Vector：在JDK1.0中出现，作为List接口的古老实现类，线程安全，效率较低；底层使用Object[]存储数据
  • ArrayList：作为List接口的主要实现类，线程不安全，效率较高；底层使用Object[]存储数据
  • LinkedList：底层使用双向链表存储数据，对于频繁插入和删除操作效率比ArrayList高

• 相同点：

  • 都实现了List接口，存储数据的特点相同：有序可重复

3.1 ArrayList

• JDK7：底层维护一个数组，初始容量为10，如果本次添加导致底层数组容量不够，则扩容，默认情况下扩容为原来容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中。
• JDK8：相对于JDK7的变化：初始容量为0，当第一次添加元素时再创建一个容量为10的数组。其余操作与JDK7中基本一致。

开发中，建议使用带参数的构造器，显式指定数组的长度，可以避免底层进行扩容操作，提高效率。

3.2 LinkedList

• 底层使用双向链表进行数据存储，内部没有声明数组，而是定义了Node类型的first和last， 用于记录首末元素。同时，定义内部类Node，作为LinkedList中保存数据的基 本结构。Node除了保存数据，还定义了两个变量：

  • prev变量记录前一个元素的位置
  • next变量记录下一个元素的位置

• 新增方法：

  • void addFirst()：在链表头部新增元素
  • void addLast() ：在链表尾部新增元素
  • Object getFirst()：获取链表头部的元素
  • Object getLast()：获取链表尾部的元素
  • Object removeFirst()：移除头部元素并返回
  • Object removeLast()：移除尾部元素并返回

3.3 Vector

• Vector是一个古老的集合，JDK1.0就有了。大多数操作与ArrayList相同，区别之处在于Vector是线程安全的。
• 在各种list中，最好把ArrayList作为缺省选择。当插入、删除频繁时， 使用LinkedList；Vector总是比ArrayList慢，所以尽量避免使用。
• ArrayList与LinkedList的异同：二者都线程不安全，相对线程安全的Vector，执行效率高。此外，ArrayList是实现了基于动态数组的数据结构，LinkedList是基于链表的数据结构。对于随机访问get()和set()，ArrayList优于LinkedList，因为LinkedList需要移动指针。对于新增和删除操作add()和remove()，LinkedList有优势，因为ArrayList要移动数据。
• ArrayList和Vector的区别：Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized)，属于 强同步类。因此开销就比ArrayList要大，访问要慢。正常情况下,大多数的Java程序员使用 ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。Vector每次扩容请求其大 小的2倍空间，而ArrayList是1.5倍。Vector还有一个子类Stack。

3.4 List接口中常用方法

List除了从Collection集合继承的方法外，还添加了一些根据索引来操作集合元素的方法。

• void add(int index, Object ele)：在index位置插入指定元素
• boolean addAll(int index, Collection eles)：从index位置开始将eles中的所有元素添加进来
• Object get(int index)：获取指定index位置的元素
• int indexOf(Object obj)：返回obj在集合中首次出现的位置
• int lastIndexOf(Object obj)：返回obj在集合中最后一次出现的位置
• Object remove(int index)：移除指定index位置的元素，并返回此元素
• Object set(int index, Object ele)：设置指定index位置的元素为ele
• List subList(int fromIndex, int toIndex)：返回从fromIndex到toIndex位置的子集合

@Test
public void test() {
    ArrayList list = new ArrayList();
    list.add(123);
    list.add("456");
    list.add("AA");
    list.add(123);
    System.out.println("初始list：" + list);

    // 在指定位置插入
    list.add(1, "BB");
    System.out.println("list.add(1, \"BB\")：" + list);

    List list2 = Arrays.asList(1, 2, 3);
    // 将其它列表的所有元素添加到当前列表
    list.addAll(list2);
    System.out.println("list.addAll(list2)：" + list);

    // 获取指定位置元素
    Object o = list.get(1);
    System.out.println("list.get(1)：" + o);

    // 获取元素在列表中的索引，找不到返回 -1
    int i = list.indexOf(123);
    System.out.println("list.indexOf(123)：" + i);

    // 获取某元素在列表中最后一次出现的位置
    int i1 = list.lastIndexOf(123);
    System.out.println("list.lastIndexOf(123)：" + i1);

    // 根据索引删除元素,返回删除位置的元素
    Object o1 = list.remove(1);
    System.out.println("list.remove(1)：" + list);

    // 返回子集合
    List list3 = list.subList(3, 6);
    System.out.println("list.subList(3, 6)：" + list3);
}

运行结果：

初始list：[123, 456, AA, 123]
list.add(1, "BB")：[123, BB, 456, AA, 123]
list.addAll(list2)：[123, BB, 456, AA, 123, 1, 2, 3]
list.get(1)：BB
list.indexOf(123)：0
list.lastIndexOf(123)：4
list.remove(1)：[123, 456, AA, 123, 1, 2, 3]
list.subList(3, 6)：[123, 1, 2]

4. Set接口

• Set接口是Collection的子接口，set接口没有提供额外的方法
• Set集合不允许包含相同的元素，如果试把两个相同的元素加入同一个Set集合中，则添加失败
• Set判断两个对象是否相同不是使用==运算符，而是根据equals()方法。

4.1 HashSet

• HashSet是Set接口的典型实现，大多数时候使用Set集合时都是用这个实现类。
• HashSet按Hash算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。

• HashSet具有以下特点：

  • 不能保证元素的排列顺序
  • HashSet不是线程安全的
  • 集合元素可以是null
• HashSet判断两个元素相等的标准：两个对象通过hashCode()方法比较相等，并且两个对象的equals()方法返回值也相等
• 对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode()方法，以实现对象相等规则。即：“相等的对象必须具有相等的散列码”。

• 向HashSet中添加元素的过程：

  • 当向HashSet集合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据hashCode值，通过某种散列函数决定该对象在HashSet底层数组中的存储位置。（这个散列函数会与底层数组的长度相计算得到在数组中的下标，并且这种散列函数计算还尽可能保证能均匀存储元素，越是散列分布，该散列函数设计的越好）
  • 如果计算得到位置后该位置上已经有元素，则比较新增元素与原有元素的哈希值是否相等。

  • 如果两个元素的hashCode()相等，会再继续调用equals()方法，如果equals()返回值为true，则添加失败，如果为false，会保存该元素，但是由于该数组位置已经有了元素，会通过链表的方式继续链接。

    • JDK7：新增元素放到数组中，指向原有的元素
    • JDK8：原来的元素继续放在数组中，并指向新增元素
  • 如果两个元素的equals()方法返回true，但是它们的hashCode()返回值不同，hashSet将会把它们存储在不同的位置，但是依旧可以添加成功。

HashSet底层也是数组，初始容量为16，如果使用率超过0.75，就会扩大容量为原来的2倍。

重写hashCode()方法的基本原则：

• 在程序运行时，同一个对象多次调用hashCode()方法应该返回相同的值。
• 当两个对象的equals()方法比较返回true时，这两个对象的hashCode()方法的返回值也应相等
• 对象中用作equals()方法比较的Field，都应该用来计算hashCode值

重写equals()方法的基本原则：

• 当一个类有自己特有的“逻辑相等”概念，当改写equals()的时候，总是要改写hashCode()，根据一个类的equals()方法，两个截然不同的实例有可能在逻辑上是相等的，但是，根据Object.hashCode()方法，它们仅仅是两个对象。因此，违反了“相等的对象必须具有相等的散列码”原则
• 故复写equals()方法的时候一般都同时复写hashCode()方法。通常参与计算hashCode的对象的属性也应该参与到equals()中进行计算。

@Test
public void test() {
    Set<Object> set = new HashSet<Object>();
    set.add(123);
    set.add(456);
    set.add("AA");
    set.add("BB");
    set.add("CC");
    System.out.println(set);
}

运行结果：

[AA, BB, CC, 456, 123]

运行结果中输出顺序与添加顺序不同

4.2 LinkedHashSet

• LinkedHashSet是HashSet的子类
• LinkedHashSet根据元素的hashCode值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的
• LinkedHashSet插入性能略低于HashSet，但在迭代访问Set里的全部元素时有很好的性能
• LinkedHashSet不允许集合元素重复

@Test
public void test2() {
    Set<Object> set = new LinkedHashSet<>();
    set.add(123);
    set.add(456);
    set.add("AA");
    set.add("BB");
    set.add("CC");
    System.out.println(set);
}

运行结果：

[123, 456, AA, BB, CC]

LinkedHashSet中可以维持元素添加的顺序

4.3 TreeSet

• TreeSet是SortedSet接口的实现类，TreeSet可以确保集合元素处于排序状态。
• TreeSet底层使用红黑树结构存储数据
• 要求添加的数据是同一个类的对象，并且新增时调用的是compareTo()方法判断对象的大小以及是否相等。

• 新增的方法如下：

  • Comparator comparator()
  • Object first()
  • Object last()
  • Object lower(Object e)
  • Object higher(Object e)
  • SortedSet subSet(fromElement, toElement)
  • SortedSet headSet(toElement)
  • SortedSet tailSet(fromElement)
• TreeSet有两种排序方法：自然排序和定制排序。默认情况下，TreeSet采用自然排序。

@Test
public void test1() {
    TreeSet set = new TreeSet();
    set.add(new User("AA", 10));
    set.add(new User("BB", 10));
    set.add(new User("CC", 10));
    set.add(new User("EE", 10));
    set.add(new User("DD", 10));
    set.add(new User("AA", 11));

    for (Object o : set) {
        System.out.println(o);
    }
}

运行结果：

User{name='AA', age=10}
User{name='AA', age=11}
User{name='BB', age=10}
User{name='CC', age=10}
User{name='DD', age=10}
User{name='EE', age=10}

其中，User类实现了Compareable接口，并在compareTo()方法中指定优先按name排序，name相等时按age排序。

4.4 TreeSet的排序：

自然排序：

• 向TreeSet中添加元素时，只有第一个元素无需比较compareTo()方法，后面添加的所有元素都会调用compareTo()方法进行比较。
• 因为只有相同类的两个实例才会比较大小，所以向TreeSet中添加的应该是同一个类的对象
• 对于TreeSet集合而言，它判断两个对象是否相同的标准是：两个对象通过compareTo()方法比较返回值。
• 当需要把一个对象放入TreeSet中，重写该对象对应的equals()方法时，应保证该方法与compareTo方法有一致的返回结果

定制排序：

• TreeSet的自然排序要求元素所属的类实现Comparable接口，如果元素所属的类没 有实现Comparable接口，或不希望按照升序(默认情况)的方式排列元素或希望按照 其它属性大小进行排序，则考虑使用定制排序。定制排序，通过Comparator接口来 实现。需要重写compare(T o1,T o2)方法。
• 利用int compare(T o1,T o2)方法，比较o1和o2的大小：如果方法返回正整数，则表 示o1大于o2；如果返回0，表示相等；返回负整数，表示o1小于o2。
• 要实现定制排序，需要将实现Comparator接口的实例作为形参传递给TreeSet的构 造器。
• 此时，仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异 常。
• 使用定制排序判断两个元素相等的标准是：通过Comparator比较两个元素返回了0。

@Test
public void test2() {
    Comparator comparator = new Comparator() {
        @Override
        public int compare(Object o1, Object o2) {
            if(o1 instanceof User && o2 instanceof User){
                User u1 = (User)o1;
                User u2 = (User)o2;
                return Integer.compare(u1.getAge(), u2.getAge());
            }else {
                throw new RuntimeException("输入数据类型不匹配");
            }
        }
    };
    TreeSet set = new TreeSet(comparator);
    set.add(new User("AA", 10));
    set.add(new User("BB", 11));
    set.add(new User("CC", 30));
    set.add(new User("EE", 50));
    set.add(new User("DD", 21));
    set.add(new User("AA", 1));
    for (Object o : set) {
        System.out.println(o);
    }
}

运行结果：

User{name='AA', age=1}
User{name='AA', age=10}
User{name='BB', age=11}
User{name='DD', age=21}
User{name='CC', age=30}
User{name='EE', age=50}