Java集合类
集合类
集合类其实就是为了更好地组织、管理和操作我们的数据而存在的，包括列表、集合、队列、映射等数据结构。
集合根接口
Java中已经帮我们将常用的集合类型都实现好了，我们只需要直接拿来用就行了
所有的集合类最终都是实现自集合根接口的，比如我们下面就会讲到的ArrayList类，它的祖先就是Collection接口：
这个接口定义了集合类的一些基本操作：
public interface Collection<E> extends Iterable<E> { //-------这些是查询相关的操作---------- //获取当前集合中的元素数量 int size(); //查看当前集合是否为空 boolean isEmpty(); //查询当前集合中是否包含某个元素 boolean contains(Object o); //返回当前集合的迭代器，我们会在后面介绍 Iterator<E> iterator(); //将集合转换为数组的形式 Object[] toArray(); //支持泛型的数组转换，同上 <T> T[] toArray(T[] a); //-------这些是修改相关的操作---------- //向集合中添加元素，不同的集合类具体实现可能会对插入的元素有要求， //这个操作并不是一定会添加成功，所以添加成功返回true，否则返回false boolean add(E e); //从集合中移除某个元素，同样的，移除成功返回true，否则false boolean remove(Object o); //-------这些是批量执行的操作---------- //查询当前集合是否包含给定集合中所有的元素 //从数学角度来说，就是看给定集合是不是当前集合的子集 boolean containsAll(Collection<?> c); //添加给定集合中所有的元素 //从数学角度来说，就是将当前集合变成当前集合与给定集合的并集 //添加成功返回true，否则返回false boolean addAll(Collection<? extends E> c); //移除给定集合中出现的所有元素，如果某个元素在当前集合中不存在，那么忽略这个元素 //从数学角度来说，就是求当前集合与给定集合的差集 //移除成功返回true，否则false boolean removeAll(Collection<?> c); //Java8新增方法，根据给定的Predicate条件进行元素移除操作 default boolean removeIf(Predicate<? super E> filter) { Objects.requireNonNull(filter); boolean removed = false; final Iterator<E> each = iterator(); //这里用到了迭代器，我们会在后面进行介绍 while (each.hasNext()) { if (filter.test(each.next())) { each.remove(); removed = true; } } return removed; } //只保留当前集合中在给定集合中出现的元素，其他元素一律移除 //从数学角度来说，就是求当前集合与给定集合的交集 //移除成功返回true，否则false boolean retainAll(Collection<?> c); //清空整个集合，删除所有元素 void clear(); //-------这些是比较以及哈希计算相关的操作---------- //判断两个集合是否相等 boolean equals(Object o); //计算当前整个集合对象的哈希值 int hashCode(); //与迭代器作用相同，但是是并行执行的，我们会在下一章多线程部分中进行介绍 @Override default Spliterator<E> spliterator() { return Spliterators.spliterator(this, 0); } //生成当前集合的流，我们会在后面进行讲解 default Stream<E> stream() { return StreamSupport.stream(spliterator(), false); } //生成当前集合的并行流，我们会在下一章多线程部分中进行介绍 default Stream<E> parallelStream() { return StreamSupport.stream(spliterator(), true); } }
List列表
List列表（线性表），线性表支持随机访问，相比之前的Collection接口定义，功能还会更多一些。
ArrayList的底层是用数组实现的，内部维护的是一个可动态进行扩容的数组，也就是顺序表，跟我们之前自己写的ArrayList相比，它更加的规范，并且功能更加强大，同时实现自List接口。
List是集合类型的一个分支，它的主要特性有：
- 是一个有序的集合，插入元素默认是插入到尾部，按顺序从前往后存放，每个元素都有一个自己的下标位置
- 列表中允许存在重复元素
List接口中，定义了列表类型需要支持的全部操作，List直接继承自前面介绍的Collection接口，其中很多地方重新定义了一次Collection接口中定义的方法，这样做是为了更加明确方法的具体功能
//List是一个有序的集合类，每个元素都有一个自己的下标位置 //List中可插入重复元素 //针对于这些特性，扩展了Collection接口中一些额外的操作 public interface List<E> extends Collection<E> { ... //将给定集合中所有元素插入到当前结合的给定位置上（后面的元素就被挤到后面去了，跟我们之前顺序表的插入是一样的） boolean addAll(int index, Collection<? extends E> c); ... //Java 8新增方法，可以对列表中每个元素都进行处理，并将元素替换为处理之后的结果 default void replaceAll(UnaryOperator<E> operator) { Objects.requireNonNull(operator); final ListIterator<E> li = this.listIterator(); //这里同样用到了迭代器 while (li.hasNext()) { li.set(operator.apply(li.next())); } } //对当前集合按照给定的规则进行排序操作，这里同样只需要一个Comparator就行了 @SuppressWarnings({"unchecked", "rawtypes"}) default void sort(Comparator<? super E> c) { Object[] a = this.toArray(); Arrays.sort(a, (Comparator) c); ListIterator<E> i = this.listIterator(); for (Object e : a) { i.next(); i.set((E) e); } } ... //-------- 这些是List中独特的位置直接访问操作 -------- //获取对应下标位置上的元素 E get(int index); //直接将对应位置上的元素替换为给定元素 E set(int index, E element); //在指定位置上插入元素，就跟我们之前的顺序表插入是一样的 void add(int index, E element); //移除指定位置上的元素 E remove(int index); //------- 这些是List中独特的搜索操作 ------- //查询某个元素在当前列表中的第一次出现的下标位置 int indexOf(Object o); //查询某个元素在当前列表中的最后一次出现的下标位置 int lastIndexOf(Object o); //------- 这些是List的专用迭代器 ------- //迭代器我们会在下一个部分讲解 ListIterator<E> listIterator(); //迭代器我们会在下一个部分讲解 ListIterator<E> listIterator(int index); //------- 这些是List的特殊转换 ------- //返回当前集合在指定范围内的子集 List<E> subList(int fromIndex, int toIndex); ... }
ArrayList基本实现：
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { //默认的数组容量 private static final int DEFAULT_CAPACITY = 10; ... //存放数据的底层数组，这里的transient关键字我们会在后面I/O中介绍用途 transient Object[] elementData; //记录当前数组元素数的 private int size; //这是ArrayList的其中一个构造方法 public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; //根据初始化大小，创建当前列表 } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } ... public boolean add(E e) { ensureCapacityInternal(size + 1); // 这里会判断容量是否充足，不充足需要扩容 elementData[size++] = e; return true; } ... //默认的列表最大长度为Integer.MAX_VALUE - 8 //JVM都C++实现中，在数组的对象头中有一个_length字段，用于记录数组的长 //度，所以这个8就是存了数组_length字段（这个只做了解就行） private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; private void grow(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); //扩容规则跟我们之前的是一样的，也是1.5倍 if (newCapacity - minCapacity < 0) //要是扩容之后的大小还没最小的大小大，那么直接扩容到最小的大小 newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) //要是扩容之后比最大的大小还大，需要进行大小限制 newCapacity = hugeCapacity(minCapacity); //调整为限制的大小 elementData = Arrays.copyOf(elementData, newCapacity); //使用copyOf快速将内容拷贝到扩容后的新数组中并设定为新的elementData底层数组 } }
一般的，如果我们要使用一个集合类，我们会使用接口的引用：
public static void main(String[] args) { List<String> list = new ArrayList<>(); //使用接口的引用来操作具体的集合类实现，是为了方便日后如果我们想要更换不同的集合类实现，而且接口中本身就已经定义了主要的方法，所以说没必要直接用实现类 list.add("科技与狠活"); //使用add添加元素 list.add("上头啊"); System.out.println(list); //打印集合类，可以得到一个非常规范的结果 }
在使用Integer时，要注意传参问题：
public static void main(String[] args) { List<Integer> list = new ArrayList<>(); list.add(10); //添加Integer的值10 list.remove((Integer) 10); //注意，不能直接用10，默认情况下会认为传入的是int类型值，删除的是下标为10的元素，我们这里要删除的是刚刚传入的值为10的Integer对象 System.out.println(list); //可以看到，此时元素成功被移除 }
快速生成一个只读的List：
public static void main(String[] args) { List<String> list = Arrays.asList("A", "B", "C"); //非常方便 System.out.println(list); }
List是只读的，不能进行修改操作，只能使用获取内容相关的方法，否则抛出 UnsupportedOperationException 异常。要生成正常使用的，我们可以将这个只读的列表作为参数传入：
public static void main(String[] args) { List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C")); System.out.println(list); }
LinkedList同样是List的实现类，只不过它是采用的链式实现，也就是我们之前讲解的链表，只不过它是一个双向链表，也就是同时保存两个方向：
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0; //引用首结点 transient Node<E> first; //引用尾结点 transient Node<E> last; //构造方法，很简单，直接创建就行了 public LinkedList() { } ... private static class Node<E> { //内部使用的结点类 E item; Node<E> next; //不仅保存指向下一个结点的引用，还保存指向上一个结点的引用 Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } ... }
LinkedList的使用和ArrayList的使用几乎相同，各项操作的结果也是一样的，在什么使用使用ArrayList和LinkedList，我们需要结合具体的场景来决定，尽可能的扬长避短。
只不过LinkedList不仅可以当做List来使用，也可以当做双端队列使用。
迭代器
集合类都是支持使用foreach语法的：
public static void main(String[] args) { List<String> list = Arrays.asList("A", "B", "C"); for (String s : list) { //集合类同样支持这种语法 System.out.println(s); } }
编译之后：
public static void main(String[] args) { List<String> list = Arrays.asList("A", "B", "C"); Iterator var2 = list.iterator(); //这里使用的是List的迭代器在进行遍历操作 while(var2.hasNext()) { String s = (String)var2.next(); System.out.println(s); } }
迭代器默认有一个指向集合中第一个元素的指针。
每一次next操作，都会将指针后移一位，直到完成每一个元素的遍历，此时再调用next将不能再得到下一个元素。
集合类的实现方案有很多，可能是链式存储，也有可能是数组存储，不同的实现有着不同的遍历方式，而迭代器则可以将多种多样不同的集合类遍历方式进行统一，只需要各个集合类根据自己的情况进行对应实现就行了。
迭代器操作：
public interface Iterator<E> { //看看是否还有下一个元素 boolean hasNext(); //遍历当前元素，并将下一个元素作为待遍历元素 E next(); //移除上一个被遍历的元素（某些集合不支持这种操作） default void remove() { throw new UnsupportedOperationException("remove"); } //对剩下的元素进行自定义遍历操作 default void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); while (hasNext()) action.accept(next()); } }
在Java8提供了一个支持Lambda表达式的forEach方法，这个方法接受一个Consumer，也就是对遍历的每一个元素进行的操作：
public static void main(String[] args) { List<String> list = Arrays.asList("A", "B", "C"); list.forEach(System.out::println); }
default void forEach(Consumer<? super T> action) { Objects.requireNonNull(action); for (T t : this) { //foreach语法遍历每一个元素 action.accept(t); //调用Consumer的accept来对每一个元素进行消费 } }
实际上只要是实现了迭代器接口的类（我们自己写的都行），都可以使用foreach语法
ListIterator迭代器是针对于List的强化版本，增加了更多方便的操作，因为List是有序集合，所以它支持两种方向的遍历操作，不仅能从前向后，也可以从后向前：
public interface ListIterator<E> extends Iterator<E> { //原本就有的 boolean hasNext(); //原本就有的 E next(); //查看前面是否有已经遍历的元素 boolean hasPrevious(); //跟next相反，这里是倒着往回遍历 E previous(); //返回下一个待遍历元素的下标 int nextIndex(); //返回上一个已遍历元素的下标 int previousIndex(); //原本就有的 void remove(); //将上一个已遍历元素修改为新的元素 void set(E e); //在遍历过程中，插入新的元素到当前待遍历元素之前 void add(E e); }
Queue和Deque
LinkedList除了可以直接当做列表使用之外，还可以当做其他的数据结构使用，可以看到它不仅仅实现了List接口：
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
Deque接口的继承结构：
public interface Queue<E> extends Collection<E> { //队列的添加操作，是在队尾进行插入（只不过List也是一样的，默认都是尾插） //如果插入失败，会直接抛出异常 boolean add(E e); //同样是添加操作，但是插入失败不会抛出异常 boolean offer(E e); //移除队首元素，但是如果队列已经为空，那么会抛出异常 E remove(); //同样是移除队首元素，但是如果队列为空，会返回null E poll(); //仅获取队首元素，不进行出队操作，但是如果队列已经为空，那么会抛出异常 E element(); //同样是仅获取队首元素，但是如果队列为空，会返回null E peek(); }
LinkedList当做一个队列来使用：
public static void main(String[] args) { Queue<String> queue = new LinkedList<>(); //当做队列使用，还是很方便的 queue.offer("AAA"); queue.offer("BBB"); System.out.println(queue.poll()); System.out.println(queue.poll()); }
双端队列就是队列的升级版，允许在队列的两端进行入队和出队操作，普通队列中从队尾入队，队首出队
双端队列既可以当做普通队列使用，也可以当做栈来使用
Deque双端队列接口的：
//在双端队列中，所有的操作都有分别对应队首和队尾的 public interface Deque<E> extends Queue<E> { //在队首进行插入操作 void addFirst(E e); //在队尾进行插入操作 void addLast(E e); boolean offerFirst(E e); boolean offerLast(E e); //在队首进行移除操作 E removeFirst(); //在队尾进行移除操作 E removeLast(); E pollFirst(); E pollLast(); //获取队首元素 E getFirst(); //获取队尾元素 E getLast(); E peekFirst(); E peekLast(); //从队列中删除第一个出现的指定元素 boolean removeFirstOccurrence(Object o); //从队列中删除最后一个出现的指定元素 boolean removeLastOccurrence(Object o); // *** 队列中继承下来的方法操作是一样的，这里就不列出了 *** ... // *** 栈相关操作已经帮助我们定义好了 *** //将元素推向栈顶 void push(E e); //将元素从栈顶出栈 E pop(); // *** 集合类中继承的方法这里也不多种介绍了 *** ... //生成反向迭代器，这个迭代器也是单向的，但是是next方法是从后往前进行遍历的 Iterator<E> descendingIterator(); }
除了LinkedList实现了队列接口之外，还有其他的实现类，但是并不是很常用
public static void main(String[] args) { Deque<String> deque = new ArrayDeque<>(); //数组实现的栈和队列 Queue<String> queue = new PriorityQueue<>(); //优先级队列 }
优先级队列可以根据每一个元素的优先级，对出队顺序进行调整，默认情况按照自然顺序：
public static void main(String[] args) { Queue<Integer> queue = new PriorityQueue<>(); queue.offer(10); queue.offer(4); queue.offer(5); System.out.println(queue.poll()); System.out.println(queue.poll()); System.out.println(queue.poll()); }
优先级队列并不是队列中所有的元素都是按照优先级排放的，优先级队列只能保证出队顺序是按照优先级进行的
Set集合
Set支持的功能其实也就和Collection中定义的差不多，只不过：
- 不允许出现重复元素
- 不支持随机访问（不允许通过下标访问）
public interface Set<E> extends Collection<E> { // Set集合中基本都是从Collection直接继承过来的方法，只不过对这些方法有更加特殊的定义 int size(); boolean isEmpty(); boolean contains(Object o); Iterator<E> iterator(); Object[] toArray(); <T> T[] toArray(T[] a); //添加元素只有在当前Set集合中不存在此元素时才会成功，如果插入重复元素，那么会失败 boolean add(E e); //这个同样是删除指定元素 boolean remove(Object o); boolean containsAll(Collection<?> c); //同样是只能插入那些不重复的元素 boolean addAll(Collection<? extends E> c); boolean retainAll(Collection<?> c); boolean removeAll(Collection<?> c); void clear(); boolean equals(Object o); int hashCode(); //这个方法我们同样会放到多线程中进行介绍 @Override default Spliterator<E> spliterator() { return Spliterators.spliterator(this, Spliterator.DISTINCT); } }
HashSet，它的底层就是采用哈希表实现的，可以非常高效的从HashSet中存取元素
在Set接口中并没有定义支持指定下标位置访问的添加和删除操作，只能简单的删除Set中的某个对象
由于底层采用哈希表实现，无法维持插入元素的顺序
想要使用维持顺序的Set集合可以使用LinkedHashSet，LinkedHashSet底层维护的不再是一个HashMap，而是LinkedHashMap，它能够在插入数据时利用链表自动维护顺序，因此这样就能够保证我们插入顺序和最后的迭代顺序一致了
public static void main(String[] args) { Set<String> set = new LinkedHashSet<>(); set.addAll(Arrays.asList("A", "0", "-", "+")); System.out.println(set); }
TreeSet，它会在元素插入时进行排序，可以自定义排序规则
public static void main(String[] args) { TreeSet<Integer> set = new TreeSet<>((a, b) -> b - a); //同样是一个Comparator set.add(1); set.add(3); set.add(2); System.out.println(set); }
