Java集合[1]–java集合分类

之前大概分为三种，Set，List，Map三种，JDK5之后，增加Queue.主要由Collection和Map两个接口衍生出来,同时Collection接口继承Iterable接口，所以我们也可以说java里面的集合类主要是由Iterable和Map两个接口以及他们的子接口或者其实现类组成。我们可以认为Collection接口定义了单列集合的规范，每次只能存储一个元素，而Map接口定义了双列集合的规范，每次能存储一对元素。

Iterable接口:主要是实现遍历功能

  • Collection接口: 允许重复
    • Set接口：无序，元素不可重复,访问元素只能通过元素本身来访问。
    • List接口：有序且可重复，可以根据元素的索引来访问集合中的元素。
    • Queue接口：队列集合

Map接口：映射关系，简单理解为键值对<Key，Value>，Key不可重复，与Collection接口关系不大，只是个别函数使用到。

整个接口框架关系

20190414213527553

Iterable接口

1
2
3
4
5
6
7
8
9
10
// 返回一个内部元素为T类型的迭代器（JDK1.5只有这个接口）
Iterator<T> iterator();

// 遍历内部元素，action意思为动作，指可以对每个元素进行操作（JDK1.8添加）
default void forEach(Consumer<? super T> action) {}

// 创建并返回一个可分割迭代器（JDK1.8添加），分割的迭代器主要是提供可以并行遍历元素的迭代器，可以适应现在cpu多核的能力，加快速度。
default Spliterator<T> spliterator() {
    return Spliterators.spliteratorUnknownSize(iterator(), 0);
}

Iterator

1
public interface Iterator<E>

Java集合最源头的接口，实现这个接口的作用主要是集合对象可以通过迭代器去遍历每一个元素。

Modifier and Type Method and Description
default void forEachRemaining(Consumer<? super E> action) 执行给定的每个剩余元素的动作，直到所有的元素都被处理或操作抛出异常。
boolean hasNext() 返回 true如果迭代具有更多的元素。
E next() 返回迭代中的下一个元素。
default void remove() 从基础集合中移除这个迭代器返回的最后一个元素（可选操作）。

iterator方法

遍历Collection的两种方式：

​ ① 使用迭代器Iterator ② foreach循环（或增强for循环）

Iterator对象称为迭代器(设计模式的一种)，主要用于遍历 Collection 集合中的元素。

GOF给迭代器模式的定义为：提供一种方法访问一个容器(container)对象中各个元素，而又不需暴露该对象的内部细节。迭代器模式，就是为容器而生。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
@Test
public void test1 (){
    Collection coll = new ArrayList();
    coll.add(123);
    coll.add(456);
    coll.add(new String("asdfg"));
    coll.add(new String("zxcvb"));
    coll.add(false);
    coll.add(456);

    Iterator iterator = coll.iterator();
    // hasNext():判断是否还下一个元素
    while(iterator.hasNext()){
        // next():①指针下移  ②将下移以后集合位置上的元素返回
        Object obj = iterator.next();
        if ("zxcvb".equals(obj)){
            // 内部定义了remove(),可以在遍历的时候，删除集合中的元素。
            iterator.remove(); 
        }
    }
    Iterator iterator1 = coll.iterator();
    while(iterator1.hasNext()){
        System.out.println(iterator1.next());
    }

    System.out.println("*****************************************");
    // for(集合元素的类型 局部变量 : 集合对象)
    for(Object obj : coll){
        System.out.println(obj);
    }
    
    //        // 错误方式一： 一次iterator.next()进行一次指针移动
    //        while(iterator.next() != null){
    //            System.out.println(iterator.next());
    //        }
    //
    //        // 错误方式二： 一次coll.iterator()返回一个迭代器对象
    //        while(coll.iterator().hasNext()){
    //            System.out.println(coll.iterator().next());
    //        }

}

如果还未调用next()或在上一次调用 next 方法之后已经调用了 remove 方法，再调用remove都会报IllegalStateException。 这是由于Fail-fast。

forEach方法

其实就是把对每一个元素的操作当成了一个对象传递进来，对每一个元素进行处理。

1
2
3
4
5
6
7
default void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
    for (T t : this) {
        action.accept(t);
    }
}
list.forEach(x -> System.out.print(x));

当然像ArrayList自然也是有自己的实现的，那我们就可以使用这样的写法,简洁优雅。forEach方法在java8中参数是java.util.function.Consumer,可以称为消费行为或者说动作类型。

spliterator方法

这是一个为了并行遍历数据元素而设计的迭代方法，返回的是Spliterator，是专门并行遍历的迭代器。以发挥多核时代的处理器性能，java默认在集合框架中提供了一个默认的Spliterator实现，底层也就是Stream.isParallel()实现的，我们可以看一下源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
// stream使用的就是spliterator
default Stream<E> stream() {
    return StreamSupport.stream(spliterator(), false);
}
default Spliterator<E> spliterator() {
    return Spliterators.spliterator(this, 0);
}
public static <T> Stream<T> stream(Spliterator<T> spliterator, boolean parallel) {
    Objects.requireNonNull(spliterator);
    return new ReferencePipeline.Head<>(spliterator,
                                        StreamOpFlag.fromCharacteristics(spliterator),
                                        parallel);
}

Collection接口：

1
public interface Collection<E> extends Iterable<E>

image-20210326162900813

Collection接口是Set,Queue,List的父接口。Collection接口中定义了多种方法可供其子类进行实现，以实现数据操作。

Modifier and Type Method and Description
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() 返回 true如果集合不包含任何元素。
Iterator<E> iterator() 返回此集合中的元素的迭代器。
default Stream<E> parallelStream() 返回一个可能并行 Stream与集合的来源。
boolean remove(Object o) 从这个集合中移除指定元素的一个实例，如果它是存在的（可选操作）。
boolean removeAll(Collection<?> c) 删除此集合中包含的所有元素（可选操作）的所有元素（可选操作）。
default boolean removeIf(Predicate<? super E> filter) 删除满足给定谓词的这个集合的所有元素。
boolean retainAll(Collection<?> c) 仅保留包含在指定集合中的这个集合中的元素（可选操作）。
int size() 返回此集合中的元素的数目。
default Spliterator<E> spliterator() 创建此集合中的元素的 Spliterator。
default Stream<E> stream() 返回一个序列 Stream与集合的来源。
Object[] toArray() 返回包含此集合中所有元素的数组。
<T> T[] toArray(T[] a) 返回包含此集合中所有元素的数组；返回数组的运行时类型是指定的数组的运行时类型。

可以看出Collection用法有：添加元素，删除元素，返回Collection集合的个数以及清空集合等。
其中重点介绍iterator()方法，该方法的返回值是Iterator。

List extends Collection

1
public interface List<E> extends Collection<E>

继承于Collection接口，有顺序，取出的顺序与存入的顺序一致，有索引，可以根据索引获取数据，允许存储重复的元素，可以放入为null的元素。
最常见的三个实现类就是ArrayList，Vector,LinkedList，ArrayList和Vector都是内部封装了对数组的操作，唯一不同的是，Vector是线程安全的，而ArrayList不是，理论上ArrayList操作的效率会比Vector好一些。

Modifier and Type Method and Description
boolean add(E e) 将指定的元素到这个列表的末尾（可选操作）。
void add(int index, E element) 在列表中指定的位置上插入指定的元素（可选操作）。
boolean addAll(Collection<? extends E> c) 追加指定集合的所有元素到这个列表的末尾，按他们的指定集合的迭代器返回（可选操作）。
boolean addAll(int index, Collection<? extends E> c) 将指定的集合中的所有元素插入到指定位置的列表中（可选操作）。
void clear() 从这个列表中移除所有的元素（可选操作）。
boolean contains(Object o) 返回 true如果这个列表包含指定元素。
boolean containsAll(Collection<?> c) 返回 true如果这个列表包含指定集合的所有元素。
boolean equals(Object o) 将指定的对象与此列表进行比较，以进行相等性。
E get(int index) 返回此列表中指定位置的元素。
int hashCode() 返回此列表的哈希代码值。
int indexOf(Object o) 返回此列表中指定元素的第一个出现的索引，或-如果此列表不包含元素，或- 1。
boolean isEmpty() 返回 true如果此列表不包含元素。
Iterator<E> iterator() 在这个列表中的元素上返回一个正确的顺序。
int lastIndexOf(Object o) 返回此列表中指定元素的最后一个发生的索引，或-如果此列表不包含元素，或- 1。
ListIterator<E> listIterator() 返回列表元素的列表迭代器（在适当的顺序）。
ListIterator<E> listIterator(int index) 在列表中的元素上返回列表迭代器（在适当的顺序），从列表中的指定位置开始。
E remove(int index) 移除此列表中指定位置的元素（可选操作）。
boolean remove(Object o) 从该列表中移除指定元素的第一个发生，如果它是存在的（可选操作）。
boolean removeAll(Collection<?> c) 从这个列表中移除包含在指定集合中的所有元素（可选操作）。
default void replaceAll(UnaryOperator<E> operator) 用将运算符应用到该元素的结果替换此列表中的每个元素。
boolean retainAll(Collection<?> c) 仅保留包含在指定集合中的列表中的元素（可选操作）。
E set(int index, E element) 用指定元素替换此列表中指定位置的元素（可选操作）。
int size() 返回此列表中元素的数目。
default void sort(Comparator<? super E> c) 分类列表使用提供的 Comparator比较元素。
default Spliterator<E> spliterator() 创建此列表中的元素的 Spliterator。
List<E> subList(int fromIndex, int toIndex) 返回一个视图之间的指定 fromIndex，包容，和 toIndex这份名单的部分，独家。
Object[] toArray() 返回一个数组，包含在这个列表中的所有元素在适当的顺序（从第一个到最后一个元素）。
<T> T[] toArray(T[] a) 返回一个数组，包含在这个列表中的所有元素在适当的顺序（从第一到最后一个元素）；返回数组的运行时类型是指定的数组的运行时类型。

Collection接口：单列集合，用来存储一个一个的对象

常用类

  • List接口：存储序的、可重复的数据。 –>“动态”数组,替换原的数组
    • ArrayList：作为List接口的主要实现类；线程不安全的，效率高；底层使用Object[] elementData存储
    • LinkedList：对于频繁的插入、删除操作，使用此类效率比ArrayList高；底层使用双向链表存储
    • Vector：作为List接口的古老实现类；线程安全的，效率低；底层使用Object[] elementData存储

Set extends Collection

1
public interface Set<E> extends Collection<E>
Modifier and Type Method and Description
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() 返回 true如果这个集合不包含元素。
Iterator<E> iterator() 返回此集合中元素的迭代器。
boolean remove(Object o) 如果当前（可选操作），则从该集合中移除指定的元素。
boolean removeAll(Collection<?> c) 从这个集合中移除包含在指定集合中的所有元素（可选操作）。
boolean retainAll(Collection<?> c) 仅保留包含在指定集合中的此集合中的元素（可选操作）。
int size() 返回该集合中元素个数（其基数）。
default Spliterator<E> spliterator() 在这个集合中的元素创建一个 Spliterator。
Object[] toArray() 返回一个包含此集合中所有元素的数组。
<T> T[] toArray(T[] a) 返回包含此集合中的所有元素的数组；返回的数组的运行时类型是指定的数组的运行时类型。

Set存储的数据特点：无序的、不可重复的元素

常用类

以HashSet为例说明：

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

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

Set接口中没额外定义新的方法，使用的都是Collection中声明过的方法。

Collection接口：单列集合，用来存储一个一个的对象

  • Set接口：存储无序的、不可重复的数据 –>高中讲的“集合”

    • HashSet：作为Set接口的主要实现类；线程不安全的；可以存储null值

      • LinkedHashSet：作为HashSet的子类；遍历其内部数据时，可以按照添加的顺序遍历。

        在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据。对于频繁的遍历操作，LinkedHashSet效率高于HashSet.

    •          TreeSet：可以照添加对象的指定属性，进行排序。

Queue extends Collection

1
public interface Queue<E> extends Collection<E>
Modifier and Type Method and Description
boolean add(E e) 插入指定元素为该队列是否有可能立即这样做不违反容量限制，还 true成功后抛出 IllegalStateException如果没有空间是可用的。
E element() 检索，但不删除此队列的头。
boolean offer(E e) 如果可能立即在不违反容量限制的情况下这样做的话，将指定的元素插入到队列中。
E peek() 检索，但不删除，这个队列头，或返回 null如果队列为空。
E poll() 检索并移除此队列的头，或返回 null如果队列为空。
E remove() 检索和删除此队列的头。

队列接口，在Collection接口的接触上添加了增删改查接口定义，一般默认是先进先出，即FIFO，除了优先队列和栈，优先队列是自己定义了排序的优先顺序，队列中不允许放入null元素。

  • Deque（接口）:Queue的子接口，双向队列，可以从两边存取

    • ArrayDeque：Deque的实现类，底层用数组实现，数据存贮在数组中

  • AbstractQueue：Queue的子接口，仅实现了add、remove和element三个方法

    • PriorityQueue：按照默认或者自己定义的顺序来排序元素，底层使用堆（完全二叉树）实现，使用动态数组实现，

  • BlockingQueue： 在java.util.concurrent包中，阻塞队列，满足当前无法处理的操作

Map接口

1
Interface Map<K,V>
  • 定义双列集合的规范Map<K，V>，每次存储一对元素，即key和value。
  • key的类型可以和value的类型相同，也可以不同，任意的引用类型都可以。
  • key是不允许重复的，但是value是可以重复的，所谓重复是指计算的hash值系统。
Modifier and Type Method and Description
void clear() 从这个映射中移除所有的映射（可选操作）。
default V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 试图计算出指定键和当前的映射值的映射（或 null如果没有当前映射）。
default V computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction) 如果指定的键是不是已经与价值相关的（或映射到 null），尝试使用给定的映射功能，进入到这个Map除非 null计算其价值。
default V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction) 如果指定键的值是存在和非空的，尝试计算一个新的映射，给出了键和它当前的映射值。
boolean containsKey(Object key) 返回 true如果这Map包含一个指定的键映射。
boolean containsValue(Object value) 返回 true如果映射到指定的值的一个或多个键。
Set<Map.Entry<K,V>> entrySet() 返回一个 Set视图的映射包含在这个Map。
boolean equals(Object o) 将指定的对象与此映射的相等性进行比较。
default void forEach(BiConsumer<? super K,? super V> action) 在该映射中的每个条目执行给定的操作，直到所有的条目被处理或操作抛出异常。
V get(Object key) 返回指定的键映射的值，或 null如果这个Map不包含的键映射。
default V getOrDefault(Object key, V defaultValue) 返回指定的键映射的值，或 defaultValue如果这个Map不包含的键映射。
int hashCode() 返回此映射的哈希代码值。
boolean isEmpty() 返回 true如果这个Map不包含键值的映射。
Set<K> keySet() 返回一个 Set的关键视图包含在这个Map。
default V merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction) 如果指定的键已与值相关联的值或与空值相关联的，则将其与给定的非空值关联。
V put(K key, V value) 将指定的值与此映射中的指定键关联（可选操作）。
void putAll(Map<? extends K,? extends V> m) 从指定的映射到这个Map（可选操作）复制所有的映射。
default V putIfAbsent(K key, V value) 如果指定的键是不是已经与价值相关的（或映射到 null）将其与给定的值并返回 null，否则返回当前值。
V remove(Object key) 如果存在（可选操作），则从该Map中移除一个键的映射。
default boolean remove(Object key, Object value) 仅当它当前映射到指定的值时，为指定的键移除条目。
default V replace(K key, V value) 仅当它当前映射到某一值时，替换指定的键的条目。
default boolean replace(K key, V oldValue, V newValue) 仅当当前映射到指定的值时，替换指定的键的条目。
default void replaceAll(BiFunction<? super K,? super V,? extends V> function) 将每个条目的值替换为在该项上调用给定函数的结果，直到所有的条目都被处理或函数抛出异常。
int size() 返回这个映射中的键值映射的数目。
Collection<V> values() 返回一个 Collection视图的值包含在这个Map。

Map:双列数据，存储key-value对的数据 —类似于高中的函数：y = f(x)

  • HashMap:作为Map的主要实现类；线程不安全的，效率高；存储null的key和value

    •          LinkedHashMap:保证在遍历map元素时，可以照添加的顺序实现遍历。
    •                原因：在原的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。
    •                对于频繁的遍历操作，此类执行效率高于HashMap。

  • TreeMap:保证照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序

    底层使用红黑树

  • Hashtable:作为古老的实现类；线程安全的，效率低；不能存储null的key和value

    •   Properties:常用来处理配置文件。key和value都是String类型

  • HashMap的底层：数组+链表 （jdk7及之前)

数组+链表+红黑树 （jdk 8)

思考

为什么有数组了，还要提供集合？

数组的优点：

  • 数组的效率高于集合类
  • 数组能存放基本数据类型和对象；集合中只能放对象

数组的缺点：

  • 不是面向对象的，存在明显的缺陷
  • 数组长度固定且无法动态改变；集合类容量动态改变
  • 数组无法判断其中实际存了多少元素，只能通过length属性获取数组的申明的长度
  • 数组存储的特点是顺序的连续内存；集合的数据结构更丰富

JDK 提供集合的意义：

  • 集合以类的形式存在，符合面向对象，通过简单的方法和属性调用可实现各种复杂操作
  • 集合有多种数据结构，不同类型的集合可适用于不同场合
  • 弥补了数组的一些缺点，比数组更灵活、实用，可开发效率