Java 集合可分为 Collection 和 Map 两种体系:
- Collection 接口:定义了存取一组对象的方法的集合。
- List:元素有序、可重复的集合。
- Set:元素无序、不可重复的集合。
- Map 接口:保存具有映射关系 key-value 对的集合。
Collection 接口
Collection 接口是 List、Set 和 Queue 接口的父接口,该接口里定义的方法既可用于操作 Set 集合,也可用于操作 List 和 Queue 集合。
JDK 不提供此接口的任何直接实现,而是提供更具体的子接口的实现。
子接口 - List
List集合类中元素有序、且可重复,集合中的每个元素都有其对应的顺序索引。
JDK API 中 List 接口的实现类常用的有:ArrayList、LinkedList 和 Vector。
实现类 - ArrayList
在 JDK 1.8 中,ArrayList 的空参数构造器采用了懒惰式的初始化方法,首先声明一个空的 Object 数组。
1 | private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; |
在 add 时,再对底层数组进行初始化操作。
1 | public boolean add(E e) { |
其中 ensureCapacityInternal 方法保证了数组有足够的空间(扩容),以及初始化操作。
- 默认最小数组容量为 DEFAULT_CAPACITY(10)。
- 调用 ensureExplicitCapacity 方法,在必要时进行扩容。
1 | private void ensureCapacityInternal(int minCapacity) { |
在调用 grow 进行扩容时,默认扩容 1.5 倍,同时将原有数组中的元素复制到新的数组中。
1 | private void ensureExplicitCapacity(int minCapacity) { |
实现类 - LinkedList
LinkList 的底层为双向链表,类的内部定义了 Node 类型的 first 和 last,用于记录第一个和最后一个元素。
同时,定义内部类 Node,作为 LinkedList 中保存数据的基本结构。Node 除了保存数据,还定义了两个变量:
- prev 变量记录前一个元素的位置。
- next 变量记录下一个元素的位置。
1 | private static class Node<E> { |
ArrayList LinkedList Vector 的异同
相同点:
- 都是实现了 List 接口,存储的都是有序的、可重复的数据。
不同点:
- ArrayList:
- 作为 List 接口的主要实现类。
- 执行效率高,线程不安全。
- 底层使用
Object[]
类型存储。
- LinkedList:
- 对于频繁的插入、删除操作,效率比 ArrayList 高。
- 底层使用双向链表实现。
- Vector:
- 作为 List 接口的古老实现类,在 JDK 1.0 就实现了。
- 效率低,但是线程安全。
- 底层使用
Object[]
类型存储。
子接口 - Set
Set 集合不允许包含相同的元素,判断两个对象是否相同不是使用 ==
运算符:
- HashSet 和 LinkedHashSet:先使用 hashcode 方法判断,若 hashcode 相同则使用 equals 方法。
- TreeSet:
- 自然排序:使用 Comparable 接口的 compareTo 方法。
- 定制排序:使用 Comparator 接口的 compare 方法。
实现类 - HashSet
当向 HashSet 集合中存入一个元素时,HashSet 会调用该对象的 hashCode() 方法来得到该对象的 hashCode 值,然后根据 hashCode 值,通过散列函数决定该对象在 HashSet 底层数组中的存储位置。
如果两个元素的 hashCode() 值相等,会再继续调用 equals 方法,如果 equals 方法结果为 true,添加失败;如果为 false,那么会保存该元素,但是该数组的位置已经有元素了,那么会通过拉链法(JDK 1.8 为尾插法)进行存储。
HashSet 的底层为数组(HashMap),初始长度为 16。当如果使用率超过 0.75,就会扩大容量为原来的 2 倍。
- 在 JDK 7 中,HashMap 采用数组 + 链表。
- 在 JDK 8 中,HashMap 采用数组 + 链表 + 红黑树。
实现类 - LinkedHashSet
LinkedHashSet 是 HashSet 的子类,LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置,但它同时使用双向链表维护元素的次序,这使得元素看起来是以插入顺序保存的。
LinkedHashSet 插入性能略低于 HashSet,但在迭代访问 Set 里的全部元素时有很好的性能。
实现类 - TreeSet
TreeSet 的底层采用红黑树进行存储,特点是:有序、查询速度比 List 快。
在 TreeSet 中比较元素不再使用 hashcode 和 equals 比较:
- 自然排序:使用 Comparable 接口中的 compareTo 方法进行比较,返回零就认为是同一个元素。
- 定制排序:使用 Comparator 接口中的 compare 方法进行比较,返回零就认为是同一个元素。
HashSet LinkedHashSet TreeSet 对比
- HashSet:
- 作为 Set 接口的主要实现类。
- 线程不安全。
- 可以存储 null 值。
- LinkedHashSet:
- 作为 HashSet 的子类。
- 在遍历内部数据时,可以按照添加的顺序遍历。
- TreeSet:
- 底层作为红黑树存储,可以按照添加的对象指定属性进行排序。
Iterator 迭代器接口
Iterator 对象称为迭代器,主要用于遍历 Collection 集合中的元素。
Collection 接口继承了 java.lang.Iterable 接口,该接口有一个 iterator 方法,那么所有实现了 Collection 接口的集合类都有一个 iterator 方法,用以返回一个实现了 Iterator 接口的对象。
Iterator 仅用于遍历集合,Iterator 本身并不提供承装对象的能力。如果需要创建Iterator 对象,则必须有一个被迭代的集合。集合对象每次调用 iterator 方法都得到一个全新的迭代器对象,默认游标都在集合的第一个元素之前。
Iterator 接口方法
Iterator 接口方法如下:
在调用 it.next() 方法之前必须要调用 it.hasNext() 进行检测。若不调用,且下一条记录无效,直接调用 it.next() 会抛出 NoSuchElementException 异常。