Java 集合框架

​

 集合概述

什么是集合

通俗来讲集合就是用来存放数据的容器。Java 的集合中只能存储对象的引用(即引用类型)，在集合中每一个元素都是一个引用变量，实际内容是存放在堆内或方法区里的；不能存储 Java 中 8 种基本数据类型，因为基本数据类型是在栈内存上分配空间的，而栈上的数据随时会被收回，但是因为 8 种基本数据类型都有对应的包装类(对象)，所以当我们将基本数据类型的数据存入集合中，Java 会将基本数据类型自动装箱为对应的包装类(如 int 变为 Integer)，然后再将引用类型存入到集合中。

集合和数组的区别

• 数组存放的类型只能是基本数据类型或引用数据类型，集合中存放的数据类型只能是引用数据类型。

• 数组是静态的，一个数组实例具有固定的大小，一旦创建了不能改变容量。而集合是可以动态扩展容量，可以根据需要动态改变大小。

• 初始化数组时需要声明存放在数组中的数据类型，而集合可以声明或不声明，当不声明时默认为 Object 类型，Object 是 Java 中的超类，这就意味着一个集合中可以存放混合类型的数据(既存放 String 类型的数据又存放 Integer 类型的数据)

Collection 和 Collections 的区别

• java.util.Collection 是一个集合接口（集合类的一个顶级接口）。它提供了对集合对象进行基本操作的通用接口方法。Collection 接口在 Java 类库中有很多具体的实现。Collection 接口的意义是为各种具体的集合提供了最大化的统一操作方式。

• Collections 则是集合类的一个工具类/帮助类，其中提供了一系列静态方法，用于对集合中元素进行排序、搜索以及线程安全等各种操作。

Java 集合框架的基础接口

• Collection，Collection 是集合框架的基础接口之一，在 Java 中不提供该接口的任何直接实现。

• Map，Map 是一个将 key 映射到 value 的对象，一个 Map 不能包含重复的 key,每个 key 最多映射到一个 value。

• List，List 是一个可以包含重复元素的集合

• Set，Set 是一个不能包含重复元素的集合

• Queue，Queue 接口是数据结构中队列结构的实现

• Iterable，Iterable 接口的实现类可以对集合进行遍历(如 Iterator)

Collection 接口相关类图

​

Map 接口相关类图

Java 集合框架常用集合类

​

List 接口

实现 List 接口的集合是有序的，List 接口主要有四个实现类： 分别是 ArrayList、Vector、LinkedList 和 CopyOnWriteArrayList

如何遍历一个 List 集合

• for 循环遍历

​​

for (int i = 0; i < list.size(); i++) {    System.out.println(list.get(i));}复制代码

• Iterator 迭代器遍历

//获取迭代器Iterator iterator = list.iterator();//判断是否还有元素while(iterator.hasNext()){   System.out.println(iterator.next());}复制代码

• forEach 循环遍历。forEach 内部也是采用 Iterator 迭代器实现集合遍历的，在使用时无需显式地声明 Iterator 迭代器，但是使用 forEach 遍历 List 集合时，不允许在遍历的过程中对集合元素进行删除或者修改。

for (Object o : list) {    System.out.println(o);}复制代码

最佳实践

​

​​

•  在 Java 集合中提供了一个RandomAccess(随机存取)接口，如果一个集合实现了该接口，那么该集合就支持随机快速存取，例如 ArrayList 就实现了该接口，那么它就支持随机快速存取，其底层遍历集合元素时采用的是 for 循环，遍历或者查询速度都非常快。

public class ArrayList<E> extends AbstractList<E>        implements List<E>, RandomAccess, Cloneable, java.io.Serializable复制代码

• 在集合工具类 Collections 中，binarySearch()二分查找方法，就运用到这一点，在采用该方法进行元素查找是，会先判断集合是否实现了 RandomAccess 接口从而判断是使用 indexedBinarySearch()[索引] 方法还是 iteratorBinarySearch()[迭代器] 方法。

public class Collections {    public static <T>    int binarySearch(List<? extends Comparable<? super T>> list, T key) {        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)            return Collections.indexedBinarySearch(list, key);        else            return Collections.iteratorBinarySearch(list, key);    }}复制代码

Iterator 与 ListIterator 的区别

Arra

yList 使用迭代器遍历集合时，获取迭代器的 iterator()方法是List接口中的 iterator()方法，调用该方法返回的是 Iterator对象，而 LinkedList 获取迭代器的 iterator()方法是AbstractSequentialList抽

象类中的 iterator()方法,在该方法中又调用了AbstractList抽象类中的listIterator()方法返回一个ListIterator对象。

​

Iterator 和 ListIterator 区别

• Iterator 可以遍历 Set 和 List 集合，而 ListIterator 只能用于遍历 List。

• Iterator 和 ListIterator 都可实现删除元素，但是 ListIterator 可以实现遍历时对元素的修改，用 set()方法实现。Iterator 仅能遍历，不能修改。

• Iterator 只能单向遍历 [ hasNext()、next()方法）]，而 ListIterator 可以双向遍历（向前/后遍历）[ 从后往前 hasPrevious()、previous()方法 ]。

• ListIterator 接口继承于 Iterator 接口，然后添加了一些额外的功能，比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置。

• 获取 ListIterator 方式：List.listIterator()、List.listIterator(int index),index 为指定游标的所在的位置。

• 获取 Iterator 方式：List.iterator()

ListIterator 继承 Iterator 接口后，自己新增的方法

• void hasPrevious() 判断游标前面是否有元素;

• Object previous() 返回游标前面的元素，同时游标向前移动一位。

• int nextIndex() 返回游标后边元素的索引位置，初始为 0，遍历 N 个元素结束时为 N;

• int previousIndex() 返回游标前面元素的位置，初始时为 -1。

• void add(E) 在游标前面插入一个元素

• void set(E) 更新迭代器最后一次操作的元素为 E，也就是更新最后一次调用 next() 或者 previous() 返回的元素。

• void remove()删除迭代器最后一次操作的元素

​

//ListIterator实现从前向后、从后向前遍历List<Integer> list = Arrays.asList(1,2,3,4);
ListIterator<Integer> listItr = list.listIterator();
System.out.print("从前向后：");while(listItr.hasNext())    System.out.print(listItr.next()+ "");
System.out.print("从后向前：");while(listItr.hasPrevious())    System.out.print(listItr.previous());复制代码

fast-fail(快速失败)迭代器

Iterator 就是一种 fast-fail 迭代器，当一个线程通过迭代器遍历 List 中的元素时，另一个线程修改或删除 List 中的元素是不允许的（），迭代器会通ConcurrentModificationException异常阻止这种情况发生，这种迭代器就叫做fast-fail迭代器。

使用 forEach 循环边遍历边移除元素出现异常

​​

ArrayList<Integer> list = new ArrayList<Integer>();    list.add(1);    list.add(2);    list.add(3);    for (Integer ele : list) {        list.remove(ele);    }    System.out.println(list.size());    //抛异常Exception in thread "main" java.util.ConcurrentModificationException	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:911)	at java.util.ArrayList$Itr.next(ArrayList.java:861)	at com.gjy.demo.collection.list.main(list.java:47)    复制代码

编译后如下：

​​

//编译后：ArrayList<Integer> list = new ArrayList();    list.add(1);    list.add(2);    list.add(3);    Iterator var2 = list.iterator();
    while(var2.hasNext()) {        Integer ele = (Integer)var2.next();        list.remove(ele);    }
    System.out.println(list.size());复制代码

从编译后的代码中可以看出，当我们使用 forEach 循环一边遍历一边移除元素时，底层其实是用 iterator 迭代器来遍历的，而移除元素用的却是 ArrayList 的 remove 方法，这样迭代器无法感知 ArrayList 中元素的变化，所以，当用 ArrayList 的 remove()方法移除掉一个元素后，下一次迭代器调用 next()方法时会调用checkForComodification()方法用于检测迭代器执行过程中是否有并发修改 （判断 modCount 和 expectedModCount 是否相等 [集合中有一个 modCount 属性，在初始化迭代器时，modCount 的值会赋给 expectedModCount，在迭代的过程中，只要 modCount 改变了，expectedModCount = modCount 等式就不成立] ），如果有则抛出 ConcurrentModificationException 异常，阻止并发修改 ArrayList 对象。因此，正确的边遍历边移除元素应该使用 Iterator 迭代器来实现。

Set 接口

实现 Set 接口的集合主要用于存储无序(存入和取出的顺序不一定相同)元素，值不能重复。对象的相等本质是根据对象的 hashCode 值 ( 在没有重写 hashCode()方法时，调用 Object 的 hashCode()方法是依据对象的内存地址计算进行计算的 ) 判断的，如果想要让两个不同的对象视为相等的，就必须重写 Object 的 hashCode()方法和 equals()方法。

hashCode()与 equals()

• 如果两个对象相等，则 hashcode 一定也是相同的,Object 类中的 hashCode 默认是根据对象的内存地址计算算出来的 int 类型的数值。

• 两个对象相等,对两个 equals 方法返回 true

• 两个对象有相同的 hashcode 值，它们也不一定是相等的

• 综上，equals 方法被覆盖过，则 hashCode 方法也必须被覆盖

• hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

Set 和 List 的区别

• List , Set 都是继承自 Collection 接口。

• List 特点：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个 null 元素，元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。

• Set 特点：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个 null 元素，必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。List 支持 for 循环，也就是通过下标来遍历，也可以用迭代器，但是 set 只能用迭代，因为它是无序，无法用下标来取得想要的值。

• Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。

• List：和数组类似，List 可以动态增长(自动扩容)，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变(如 ArrayList、Vector)。

Map 接口

Map 接口与 List 和 Set 接口不同，没有继承 Collection，是一个双列集合，它是由一系列键值对组成的集合，提供了 key 到 Value 的映射。在 Map 接口中保证了 key 与 value 之间的一一对应关系，即一个 key 对应一个 value，它不能存在相同的 key 值(唯一)且不要求 key 是有序的，但是 value 值是可以相同的。常用的 Map 实现类有 HashMap、HashTable、ConcurrentHashMap.

​