乐趣区

关于java:java集合1-俯瞰Java集合分类

jiezi

（一）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 接口关系不大，只是个别函数应用到。

整个接口框架关系如下（来自百度百科）：

（1）Iterable 接口

1. 外部定义的办法

java 汇合 最源头的接口，实现这个接口的作用次要是汇合对象能够通过迭代器去遍历每一个元素。

源码如下：

// 返回一个外部元素为 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);
}

从下面能够看出，foreach迭代以及可宰割迭代，都加了 default 关键字，这个是 Java 8 新的关键字，以前接口的所有接口，具体子类都必须实现，而对于 deafult 关键字标识的办法，其子类能够不必实现，这也是接口标准发生变化的一点。
上面咱们别离展现三个接口的调用：

1.1 iterator 办法
public static void iteratorHasNext(){List<String> list=new ArrayList<String>();
    list.add("Jam");
    list.add("Jane");
    list.add("Sam");
    // 返回迭代器
    Iterator<String> iterator=list.iterator();
    // hashNext 能够判断是否还有元素
    while(iterator.hasNext()){//next()作用是返回以后指针指向的元素, 之后将指针移向下个元素
        System.out.println(iterator.next());
    }
}

当然也能够应用 for-each loop 形式遍历

for (String item : list) {System.out.println(item);
}

然而实际上，这种写法在 class 文件中也是会转成迭代器模式，这只是一个语法糖。class文件如下：

public class IterableTest {public IterableTest() { }
    public static void main(String[] args) {iteratorHasNext();
    }
    public static void iteratorHasNext() {List<String> list = new ArrayList();
        list.add("Jam");
        list.add("Jane");
        list.add("Sam");
        Iterator<String> iterator = list.iterator();
        Iterator var2 = list.iterator();
        while(var2.hasNext()) {String item = (String)var2.next();
            System.out.println(item);
        }
    }
}

须要留神的一点是，迭代遍历的时候，如果删除或者增加元素，都会抛出批改异样，这是因为疾速失败 【fast-fail】 机制, 属于一种自我爱护的机制。

    public static void iteratorHasNext(){List<String> list=new ArrayList<String>();
        list.add("Jam");
        list.add("Jane");
        list.add("Sam");
        for (String item : list) {if(item.equals("Jam")){list.remove(item);
            }
            System.out.println(item);
        }
    }

从上面的谬误咱们能够看出，第一个元素是有被打印进去的，也就是 remove 操作是胜利的，只是遍历到第二个元素的时候，迭代器查看，发现被扭转了，所以抛出了异样。

Jam
Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
    at java.util.ArrayList$Itr.next(ArrayList.java:859)
    at IterableTest.iteratorHasNext(IterableTest.java:15)
    at IterableTest.main(IterableTest.java:7)
1.2 forEach 办法

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

    default void forEach(Consumer<? super T> action) {Objects.requireNonNull(action);
        for (T t : this) {action.accept(t);
        }
    }

当然像 ArrayList 天然也是有本人的实现的，那咱们就能够应用这样的写法, 简洁优雅。forEach()在 java8 中参数是 java.util.function.Consumer, 能够称为 消费行为 或者说 动作 类型。

list.forEach(x -> System.out.print(x));

同时，咱们只有实现 Consumer 接口，就能够自定义动作，如果不自定义，默认迭代程序是依照元素的程序。

public class ConsumerTest {public static void main(String[] args) {List<String> list=new ArrayList<String>();
        list.add("Jam");
        list.add("Jane");
        list.add("Sam");
        MyConsumer myConsumer = new MyConsumer();
        Iterator<String> it = list.iterator();
        list.forEach(myConsumer);
    }
    static class MyConsumer implements Consumer<Object> {
        @Override
        public void accept(Object t) {System.out.println("自定义打印：" + t);
        }

    }

}

输入的后果：

自定义打印：Jam
自定义打印：Jane
自定义打印：Sam
1.3 spliterator 办法

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

    // 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);
    }

应用的办法如下：

    public static void spliterator(){List<String> list = Arrays.asList("1", "2", "3","4","5","6","7","8","9","10");
        // 获取可迭代器
        Spliterator<String> spliterator = list.spliterator();
        // 一个一个遍历
        System.out.println("tryAdvance:");
        spliterator.tryAdvance(item->System.out.print(item+" "));
        spliterator.tryAdvance(item->System.out.print(item+" "));
        System.out.println("\n-------------------------------------------");

        // 顺次遍历剩下的
        System.out.println("forEachRemaining:");
        spliterator.forEachRemaining(item->System.out.print(item+" "));
        System.out.println("\n------------------------------------------");

        // spliterator1:0~10
        Spliterator<String> spliterator1 = list.spliterator();
        // spliterator1:6~10 spliterator2:0~5
        Spliterator<String> spliterator2 = spliterator1.trySplit();
        // spliterator1:8~10 spliterator3:6~7
        Spliterator<String> spliterator3 = spliterator1.trySplit();
        System.out.println("spliterator1:");
        spliterator1.forEachRemaining(item->System.out.print(item+" "));
        System.out.println("\n------------------------------------------");
        System.out.println("spliterator2:");
        spliterator2.forEachRemaining(item->System.out.print(item+" "));
        System.out.println("\n------------------------------------------");
        System.out.println("spliterator3:");
        spliterator3.forEachRemaining(item->System.out.print(item+" "));
    }
  • tryAdvance（） 一个一个元素进行遍历
  • forEachRemaining() 程序地分块遍历
  • trySplit()进行分区造成另外的 Spliterator，应用在并行操作中，分进去的是后面一半，就是一直把后面一部分分进去

后果如下：

tryAdvance: 
1 2 
-------------------------------------------
forEachRemaining: 
3 4 5 6 7 8 9 10 
------------------------------------------
spliterator1: 
8 9 10 
------------------------------------------
spliterator2: 
1 2 3 4 5 
------------------------------------------
spliterator3: 
6 7

还有一些其余的用法在这里就不列举了，次要是 trySplit() 之后，能够用于多线程遍历。现实的时候，能够均匀分成两半，有利于并行计算，然而不是肯定平分的。

2. Collection 接口 extend Iterable<E>

Collection接口能够算是汇合类的一个根接口之一，个别不可能间接应用，只是定义了一个标准，定义了增加，删除等治理数据的办法。继承 Collection 接口的有 List，Set,Queue, 不过Queue 定义了本人的一些接口，相对来说和其余的差别比拟大。

2.1 外部定义的办法

源码如下：

boolean add(Object o)    // 增加元素

boolean remove(Object o)  // 移除元素

boolean addAll(Collection c) // 批量增加

boolean removeAll(Collection c)  // 批量移除

void retainAll(Collection c)   // 移除在 c 中不存在的元素

void clear()  // 清空集合

int size()   // 汇合大小

boolean isEmpty()    // 是否为空

boolean contains(Object o)    // 是否蕴含在汇合中

boolean containsAll(Collection c)    // 是否蕴含所有的元素

Iterator<E> iterator()    // 获取迭代器

Object[] toArray()      // 转成数组

default boolean removeIf(Predicate<? super E> filter) {} // 删除汇合中复合条件的元素，删除胜利返回 true

boolean equals(Object o)

int hashCode()

default Spliterator<E> spliterator() {} // 获取可宰割迭代器

default Stream<E> stream() {}   // 获取流

default Stream<E> parallelStream() {} // 获取并行流

外面获取并行流的办法 parallelStream(), 其实就是通过默认的ForkJoinPool（次要用来应用分治法(Divide-and-Conquer Algorithm) 来解决问题），进步多线程工作的速度。咱们能够应用 ArrayList 来演示一下平行解决能力。例如上面的例子，输入的程序就不肯定是 1,2,3…，可能是乱序的，这是因为工作会被分成多个小工作，工作执行是没有特定的程序的。

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
list.parallelStream()
       .forEach(out::println);
2.2 继承 Collection 的次要接口
graph LR;
Collection -->List- 有程序, 可反复 
List- 有程序, 可反复  -->LinkedList- 应用链表实现, 线程不平安
List- 有程序, 可反复  -->ArrayList- 数组实现, 线程不平安
List- 有程序, 可反复  -->Vector- 数组实现, 线程平安
Vector- 数组实现, 线程平安 -->Stack- 堆栈, 先进后出

Collection-->Set- 不可反复, 外部排序
Set- 不可反复, 外部排序 -->HashSet-hash 表存储
HashSet-hash 表存储 -->LinkHashSet- 链表保护插入程序
Set- 不可反复, 外部排序 -->TreeSet- 二叉树实现, 排序

Collection-->Queue- 队列, 先进先出
2.2.1 List extend Collection<E>

继承于 Collection 接口，有程序，取出的程序与存入的程序统一，有索引，能够依据索引获取数据，容许存储反复的元素，能够放入为 null 的元素。
最常见的三个实现类就是 ArrayList，Vector,LinkedList，ArrayList 和Vector都是外部封装了对数组的操作，惟一不同的是，Vector是线程平安的，而 ArrayList 不是，实践上 ArrayList 操作的效率会比 Vector 好一些。

外面是接口定义的办法：

int size();  // 获取大小

boolean isEmpty();  // 判断是否为空

boolean contains(Object o);  // 是否蕴含某个元素

Iterator<E> iterator(); // 获取迭代器

Object[] toArray();  // 转化成为数组（对象）<T> T[] toArray(T[] a);  // 转化为数组（特定位某个类）boolean add(E e); // 增加

boolean remove(Object o);  // 移除元素

boolean containsAll(Collection<?> c); // 是否蕴含所有的元素

boolean addAll(Collection<? extends E> c); // 批量增加

boolean addAll(int index, Collection<? extends E> c); // 批量增加，指定开始的索引

boolean removeAll(Collection<?> c); // 批量移除

boolean retainAll(Collection<?> c); // 将 c 中不蕴含的元素移除

default void replaceAll(UnaryOperator<E> operator) {}// 替换

default void sort(Comparator<? super E> c) {}// 排序

void clear();// 革除所有的元素

boolean equals(Object o);// 是否相等

int hashCode(); // 计算获取 hash 值

E get(int index); // 通过索引获取元素

E set(int index, E element);// 批改元素

void add(int index, E element);// 在指定地位插入元素

E remove(int index);// 依据索引移除某个元素

int indexOf(Object o);  // 依据对象获取索引

int lastIndexOf(Object o); // 获取对象元素的最初一个元素

ListIterator<E> listIterator(); // 获取 List 迭代器

ListIterator<E> listIterator(int index); // 依据索引获取以后的地位的迭代器

List<E> subList(int fromIndex, int toIndex); // 截取某一段数据

default Spliterator<E> spliterator(){} // 获取可切分迭代器

下面的办法都比较简单，值得一提的是外面呈现了 ListIterator，这是一个性能更加弱小的迭代器，继承于Iterator, 只能用于List 类型的拜访，拓展性能例如：通过调用 listIterator() 办法取得一个指向 List 结尾的 ListIterator，也能够调用listIterator(n) 获取一个指定索引为 n 的元素的 ListIterator, 这是一个能够双向挪动的迭代器。
操作数组索引的时候须要留神，因为 List 的实现类底层很多都是数组，所以索引越界会报错 IndexOutOfBoundsException。
说起 List 的实现子类：

  • ArrayList：底层存储构造是数组构造，减少删除比较慢，查找比拟快，是最罕用的 List 汇合。线程不平安。
  • LinkedList：底层是链表构造，减少删除比拟快，然而查找比较慢。线程不平安。
  • Vector：和 ArrayList 差不多，然而是线程平安的，即同步。
2.2.2 Set extend Collection<E>

Set接口，不容许放入反复的元素，也就是如果雷同，则只存储其中一个。

上面是源码办法：

int size(); // 获取大小

boolean isEmpty();  // 是否为空
 
boolean contains(Object o); // 是否蕴含某个元素

Iterator<E> iterator(); // 获取迭代器

Object[] toArray(); // 转化成为数组

<T> T[] toArray(T[] a); // 转化为特定类的数组

boolean add(E e);   // 增加元素

boolean remove(Object o);   // 移除元素

boolean containsAll(Collection<?> c);   // 是否蕴含所有的元素

boolean addAll(Collection<? extends E> c);  // 批量增加

boolean retainAll(Collection<?> c); // 移除所有不存在于 c 汇合中的元素

boolean removeAll(Collection<?> c); // 移除所有在 c 汇合中存在的元素

void clear();   // 清空集合

boolean equals(Object o);   // 是否相等

int hashCode(); // 计算 hashcode

default Spliterator<E> spliterator() {}     // 获取可宰割迭代器

次要的子类：

  • HashSet

    • 容许空值
    • 通过 HashCode 办法计算获取 hash 值，确定存储地位，无序。

  • LinkedHashSet

    • HashSet的子类
    • 有程序

  • TreeSet

    • 如果无参数构建 Set，则须要实现Comparable 办法。
    • 亦能够创立时传入比拟办法，用于排序。
2.2.3 Queue extend Collection<E>

队列接口，在 Collection 接口的接触上增加了增删改查接口定义，个别默认是先进先出，即FIFO，除了优先队列和栈，优先队列是本人定义了排序的优先程序，队列中不容许放入 null 元素。

上面是源码：

boolean add(E e);   // 插入一个元素到队列，失败时返回 IllegalStateException（如果队列容量不够）boolean offer(E e); // 插入一个元素到队列，失败时返回 false

E remove(); // 移除队列头的元素并移除

E poll();   // 返回并移除队列的头部元素，队列为空时返回 null

E element();    // 返回队列头元素

E peek();   // 返回队列头部的元素，队列为空时返回 null

次要的子接口以及实现类有：

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

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

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

    • PriorityQueue：依照默认或者本人定义的程序来排序元素，底层应用堆（齐全二叉树）实现，应用动静数组实现，
  • BlockingQueue：在 java.util.concurrent 包中，阻塞队列，满足以后无奈解决的操作。

（2）Map 接口

  • 定义双列汇合的标准 Map<K，V>，每次存储一对元素，即key 和value。
  • key的类型能够和 value 的类型雷同，也能够不同，任意的援用类型都能够。
  • key是不容许反复的，然而 value 是能够反复的，所谓反复是指计算的 hash 值。

上面的源码的办法：

V put(K key, V value);  // 增加元素

V remove(Object key);   // 删除元素

void putAll(Map<? extends K, ? extends V> m); // 批量增加

void clear()  // 移除所有元素

V get(Object key);  // 通过 key 查问元素

int size();    // 查问汇合大小

boolean isEmpty();    // 汇合是否为空

boolean containsKey(Object key);     // 是否蕴含某个 key
    
boolean containsValue(Object value);     // 是否蕴含某个 value

Set<K> keySet(); // 获取所有 key 的 set 汇合

Collection<V> values(); // 获取所有的 value 的 set 汇合

Set<Map.Entry<K, V>> entrySet();    // 返回键值对的 set，每一个键值对是一个 entry 对象

boolean equals(Object o);   // 用于比拟的函数

int hashCode(); // 计算 hashcode

default V getOrDefault(Object key, V defaultValue) // 获取 key 对应的 Value，没有则返回默认值（）default void forEach(BiConsumer<? super K, ? super V> action) {}  // 遍历

default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {}  // 批量替换

// 短少这个 key 的时候才会增加进去
// 返回值是是 key 对应的 value 值，如果不存在，则返回的是刚刚放进去的 value
default V putIfAbsent(K key, V value) {} 

default boolean remove(Object key, Object value) {}  // 移除元素

default boolean replace(K key, V oldValue, V newValue) {}   // 替换

default V replace(K key, V value) {}  // 替换

// 和 putIfAbsent 有点像，只不过传进去的 mappingFunction 是映射函数，也就是如果不存在 key 对应的 value，将会执行函数，函数返回值会被当成 value 增加进去，同时返回新的 value 值
default V computeIfAbsent(K key,Function<? super K, ? extends V> mappingFunction) {} 
// 和 computeIfAbsent 办法相同，只有 key 存在的时候，才会执行函数，并且返回
default V computeIfPresent(K key,BiFunction<? super K, ? super V, ? extends V> remappingFunction) {}

// 不论如何都会执行映射函数，返回 value            
default V compute(K key,BiFunction<? super K, ? super V, ? extends V> remappingFunction) {}
    
default V merge(K key, V value,BiFunction<? super V, ? super V, ? extends V> remappingFunction) {}

值得注意的是，Map 外面定义了一个 Entry 类，其实就是定义了一个存储数据的类型，一个 entry 就是一个<key,value>.
Map 的罕用的实现子类：

  • HashMap：由数组和链表组成，线程不平安，无序。
  • LinkedHashMap：如果咱们须要是有序的，那么就须要它，工夫和空间效率没有 HashMap 那么高，底层是保护一条双向链表，保障了插入的程序。
  • ConcurrentHashMap：线程平安，1.7JDK 应用锁拆散，每一段 Segment 都有本人的独立锁，相对来说效率也比拟高。JDK1.8 摈弃了 Segment，应用 Node 数组 + 链表和红黑树实现，在线程安全控制上应用 Synchronize 和CAS，能够认为是 优化的线程平安的HashMap。
  • HashTable：比照与 HashMap 次要是应用关键字synchronize，加上同步锁，线程平安。

（二）总结

这些汇合原始接口到底是什么？为什么须要？

我想，这些接口其实都是一种规定 / 标准的定义，如果不这么做也能够，所有的子类本人实现，然而从迭代以及保护的角度来说，这就是一种形象或者分类，比方定义了 Iterator 接口，某一些类就能够去继承或者实现，那就得恪守这个标准 / 契约。能够有所拓展，每个子类的拓展不一样，所以每个类就各有千秋，然而都有一个核心，就是原始的汇合接口。比方实现 Map 接口的所有类的中心思想都不变，都是 <key,value> 只是各有千秋，各分千秋，造成了大千汇合世界。

此文章仅代表本人（本菜鸟）学习积攒记录，或者学习笔记，如有侵权，请分割作者删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有谬误之处，还望指出，感激不尽~

技术之路不在一时，山高水长，纵使迟缓，驰而不息。
公众号：秦怀杂货店

退出移动版