Collection接口（List和Set）

图片来源于：Java：集合，Collection接口框架图

Java集合大致可分为Set、List和Map三种体系，其中Set代表无序、不可重复的集合；List代表有序、重复的集合；而Map则代表具有映射关系的集合。Java 5之后，增加了Queue体系集合，代表一种队列集合实现。Java集合框架主要由Collection和Map两个根接口及其子接口、实现类组成。本文仅探讨Collection接口的常用抽象方法，以及List和Set实现接口。

Collection接口抽象方法

返回值	方法	描述
boolean	add(E e)	添加元素
boolean	addAll(Collection<? extends E> c)	将指定集合中的元素添加到该元素中
void	clear()	清除集合中的所有元素
boolean	contains(Object o)	如果集合含有该元素，则返回true
boolean	containsAll(Collection<?> c)	如果集合含有指定集合的所有元素，则返回true
boolean	equals(Object o)	对比该集合与指定集合元素是否相同
int	hashCode()	返回集合的哈希值
boolean	isEmpty()	判断集合是否为空
Iterator<E>	iterator()	返回该集合的迭代器
boolean	remove(Object o)	删除集合中的单个实例元素（如果含有，返回true）
boolean	removeAll(Collection<?> c)	删除集合中的和指定集合中的所有元素的交集（只要有交集则代表删除成功返回true）
boolean	retainAll(Collection<?> c)	获取当前集合和指定集合的交集，并返回给当前集合
int	size()	返回集合中元素的个数
Object[]	toArray()	返回一个包含当前集合所有元素的数组
<T> T[]	toArray(T[] a)	返回一个包含此集合中所有元素的数组； 返回数组的运行时类型是指定数组的运行时类型。

List接口

public interface List<E> extends Collection<E>{}

List.java

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list. Unlike sets, lists typically allow duplicate elements. More formally, lists typically allow pairs of elements {@code e1} and {@code e2} such that {@code e1.equals(e2)}, and they typically allow multiple null elements if they allow null elements at all…

List接口可以包含有序的、可重复的数据。

ArrayList.java（@since 1.2）

Resizable-array implementation of the {@code List} interface. Implements all optional list operations, and permits all elements, including {@code null}. In addition to implementing the {@code List} interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to {@code Vector}, except that it is unsynchronized.)

ArrayList作为List接口的一个实现类，可以看成一个动态数组，允许所有类型元素的插入，功能上和Vector类类似，但是它是线程不安全的，底层使用Object[] elementData存储。

LinkedList.java（@since 1.2）

Doubly-linkedlist implementation of the {@code List} and {@code Deque} interfaces. Implements all optional list operations, and permits all elements (including {@code null})…

Note that this implementation is not synchronized…

LinkedList允许所有类型元素的插入，线程不安全的，内部声明了Node类型的first和last属性，默认值为null，使用双向链表存储。对于频繁的插入、删除等操作此类效率比ArrayList高。

private static class Node<E> {
    E item;
    LinkedList.Node<E> next;
    LinkedList.Node<E> prev;

    Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Vector.java（@since 1.0）

此类方法与ArrayList相似，但是它是线程安全的，因此效率较低。

List遍历

@Test
public void test(){
    ArrayList list = new ArrayList();
    list.add(123);
    list.add(456);
    list.add(456);
    list.add("AA");
    list.add(new Person("Tom",12));
}

Iterator

// 方式一：Iterator
Iterator iterator = list.iterator();
while(iterator.hasNext()){
    System.out.println(iterator.next());
}

for循环

// 方式三：for循环
for(int i = 0; i < list.size(); i++){
    System.out.print(list.get(i) + "\t");
}

foreach（增强for）循环

int count = 0;
for(Object obj : list){
    System.out.printf("list[%s] = %s\t", count++, obj);// 格式化输出
}

Set接口

public interface Set<E> extends Collection<E> {}

Set.java

A collection that contains no duplicate elements. More formally, sets contain no pair of elements {@code e1} and {@code e2} such that {@code e1.equals(e2)}, and at most one null element…

Set接口存储无序的，不重复的数据。

无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加。而实根据数据的哈希值决定的

不可重复性：保证添加的元素按照equals()判断时，不能返回true。即相同的元素只能添加一个

HashSet.java（@since 1.2）

This class implements the {@code Set} interface, backed by a hash table (actually a {@code HashMap} instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the {@code null} element…

Note that this implementation isnot synchronized…

HashSet使用的是相当复杂的方式来存储元素的，使用HashSet能够最快的获取集合中的元素，效率非常高（以空间换时间）。添加元素时，先计算元素的哈希值（hashCode），无重复哈希值则添加成功。若出现相同哈希值，则通过equals方法来判断添加元素与已有元素是否为相同，HashSet的底层为数组+链表的方式。HashSet是线程不安全的

遍历输出无序，根据哈希值决定。

@Test
public void test1(){
    Set set = new HashSet();
    // Set set = new LinkedHashSet();
    set.add(123);
    set.add(123);
    set.add("AA");
    set.add("CC");
    set.add(new User("Tom",12));
    set.add(new User("Tom",12));
    set.add(129);
    set.add(null);

    // 按照元素计算得到的哈希值输出
    System.out.println(set); // [AA, CC, null, 129, 123, User{name='Tom', age=12}]
}

LinkedHashSet.java

Hash table and linked list implementation of the {@code Set} interface, with predictable iteration order. This implementation differs from {@code HashSet} in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order). Note that insertion order is not affected if an element is re-inserted into the set. (An element {@code e} is reinserted into a set {@code s} if {@code s.add(e)} is invoked when {@code s.contains(e)} would return {@code true} immediately prior to the invocation.)…

Note that this implementation is not synchronized…

LinkedHashSet作为HashSet的子类，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个和后一个数据（双向链表）。

对于比较频繁的遍历操作，LinkedHashSet效率高于HashSet，LinkedHashSet是线程不安全的

遍历输出有序，根据添加顺序

@Test
public void test2(){
    Set set = new LinkedHashSet();
    set.add(123);
    set.add(123);
    set.add("AA");
    set.add("CC");
    set.add(new User("Tom",12));
    set.add(new User("Tom",12));
    set.add(129);

    // 按照添加顺序输出
    System.out.println(set); // [123, AA, CC, User{name='Tom', age=12}, 129]
}

TreeSet.java（@since 1.2）

A {@link NavigableSet} implementation based on a {@link TreeMap}. The elements are ordered using their {@linkplain Comparable natural ordering}, or by a {@link Comparator} provided at set creation time, depending on which constructor is used…Note that this implementation is not synchronized.

TreeSet是SortedSet接口的唯一实现，可以确保集合元素处于排序状态。TreeSet支持两种排序方式：自然排序和定制排序，默认情况下采用自然排序，同时TreeSet是线程不安全的

不可以添加不同类的对象！！无法进行自然排序！！

@Test
public void test1(){
    TreeSet set = new TreeSet();
    // 失败：不能添加不同类的对象
    set.add(123);
    set.add(456);
    set.add("AA");
    System.out.println(set);
}

自然排序

@Test
public void test1(){
    TreeSet set = new TreeSet();
    set.add(new User("Tom",12));
    set.add(new User("Jerry",32));
    set.add(new User("Jmy",3));
    set.add(new User("Mike",65));
    set.add(new User("Jack",33));
    set.add(new User("Jack",15));
    
    Iterator iterator = set.iterator();
    while(iterator.hasNext()){
        System.out.println(iterator.next());
    }
}

// 按照姓名从大到小排序，年龄从小到大排列
@Override
public int compareTo(Object o) {
    System.out.println("调用User重写Comparable接口的compareTo方法");
    if(o instanceof User){
        User user = (User) o;
        // return this.name.compareTo(user.name);
        int compare = this.name.compareTo(user.name);
        if(compare != 0){
            return compare;
        }else{
            return Integer.compare(this.age,user.age);
        }
    }else{
        throw new RuntimeException("输入的类型不匹配");
    }
}

输出结果

调用User重写Comparable接口的compareTo方法
调用User重写Comparable接口的compareTo方法
调用User重写Comparable接口的compareTo方法
调用User重写Comparable接口的compareTo方法
调用User重写Comparable接口的compareTo方法
调用User重写Comparable接口的compareTo方法
调用User重写Comparable接口的compareTo方法
调用User重写Comparable接口的compareTo方法
调用User重写Comparable接口的compareTo方法
调用User重写Comparable接口的compareTo方法
调用User重写Comparable接口的compareTo方法
User{name=’Jack’, age=15}
User{name=’Jack’, age=33}
User{name=’Jerry’, age=32}
User{name=’Jmy’, age=3}
User{name=’Mike’, age=65}
User{name=’Tom’, age=12}

定制排序

@Test
public void test2(){
    Comparator com = new Comparator() {
        // 按照年龄从小到大排列
        // 年龄相同的数据按照自然排序进行
        @Override
        public int compare(Object o1, Object o2) {
            if(o1 instanceof User && o2 instanceof User){
                User user1 = (User) o1;
                User user2 = (User) o2;
                int result;
                result = user1.getAge() > user2.getAge() ? 1 : user1.getAge() == user2.getAge() ? 0 : -1;
                if(result == 0){
                    result = user1.compareTo(user2);
                }
                return result;
            }else{
                throw new RuntimeException("传入的数据类型不匹配");
            }
        }
    };

    TreeSet set = new TreeSet(com); // 传入新建的Comparator对象
    set.add(new User("Tom",33));
    set.add(new User("Jerry",33));
    set.add(new User("Marry",33));
    set.add(new User("Jmy",33));
    set.add(new User("Mike",33));
    set.add(new User("Jack",33));
    set.add(new User("Jack",34));
    
    Iterator iterator = set.iterator();
    while(iterator.hasNext()){
        System.out.println(iterator.next());
    }
}

输出结果

User{name=’Tom’, age=20}
User{name=’Jack’, age=34}
User{name=’Jack’, age=43}
User{name=’Jerry’, age=45}
User{name=’Jmy’, age=45}
User{name=’Mike’, age=66}
User{name=’Marry’, age=78}

Set接口遍历方式同List

List和Set接口的常用方法

返回值	方法	描述
void	add(int index, E element)	指定索引处添加元素
boolean	addAll(int index, Collection<? extends E> c)	指定索引处添加指定集合的所有元素
E	get(int index)	返回执行索引处的元素
int	indexOf(Object o)	（从左往右）返回第一次出现元素o的索引位置，未出现则返回-1
int	lastIndexOf(Object o)	（从右往左）返回第一次出现元素o的索引位置，未出现则返回-1
E	remove(int index)	移除指定索引位置的元素，并返回此元素
E	set(int index, E element)	设置指定索引位置的元素为element
List<E>	subList(int fromIndex, int toIndex)	返回从fromIndex到toIndex位置的子集合