乐趣区

关于后端:Java-SE基础巩固四集合类

jiezi

1 汇合概述

Java 中有很多汇合类，例如 ArrayList，LinkedList，HashMap，TreeMap 等。汇合的性能就是包容多个对象，它们就像容器一样（实际上，间接称为容器也没有故障，C++ 就是这样称说的），当须要的时候，能够从外面拿进去，十分不便。在 Java5 提供了泛型机制之后，使容器有了在编译期做类型查看的能力，应用起来更加平安、不便。

Java 中的汇合类次要是有两个接口派生进去的：Collection 和 Map，如下所示：

[](https://imgchr.com/i/i3JEbd)

[

](https://imgchr.com/i/i3JEbd)

[](https://imgchr.com/i/i3JZVA)

[

](https://imgchr.com/i/i3JZVA)

Collection 又次要有 Set，Queue，List 三大接口，在此基础上，又有多个实现类。Map 接口下同样有总多的实现类，例如 HashMap，EnumMap，HashTable 等。接下来我将会筛选几个罕用的汇合类来具体探讨探讨。

2 ArrayList 和 LinkedList

List 汇合能够说是最罕用的汇合了，比 HashMap 还罕用，个别咱们写代码的时候一旦遇到须要存储多个元素的状况，就优先想到应用 List 汇合，至于应用的是 ArrayList 实现类还是 LinkedList 实现类，那就具体情况具体分析了。
《2020 最新 Java 根底精讲视频教程和学习路线！》

2.1 ArrayList

ArrayList 实现了 List 接口，继承了 AbstractList 抽象类，AbstractList 抽象类实现了绝大部分 List 接口定义的形象办法，所以咱们在 ArrayList 源码中看不到大部分 List 接口中定义的形象办法的实现。ArrayList 的外部应用数组来存储对象，这也是 ArrayList 这个名字的由来，其各种操作，例如 get，add 等都是基于数组操作的，上面是 add 办法的源码：

public void add(int index, E element) {
    // 先查看 index 是否在一个正当的范畴内
    rangeCheckForAdd(index);
    
    // 保障数组的容量足够退出新的元素，发现不足够的话会进行扩容操作
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 进行一次数组拷贝，这里的 elementData 就是保留对象的 Object 数组
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 往数组中退出元素
    elementData[index] = element;
    // 批改 size 大小
    size++;
}
复制代码

解释在正文中给出了，get 办法也非常简单，就不浪费时间了。

2.2 LinkedList

LinkedList 继承了 AbstractSequentialList 类，AbstractSequentialList 类又继承了 AbstractList 类，同时 LinkedList 也当然有实现 List 接口的，而且还实现了 Deque 接口，这就比拟有意思了，阐明 LinkedList 不仅仅是 List，还是一个 Queue。下图示意其继承体系：

[](https://imgchr.com/i/i3JrqJ)

[

](https://imgchr.com/i/i3JrqJ)

LinkedList 的基于链表实现的 List，这是和 ArrayList 最大的区别。LinkedList 有一个 Node 外部类，用来示意节点，如下所示：

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;
    }
}
复制代码

该类有 next 指针和 prev 指针，可见是一个双向链表。接下来看看 LinkedList 的 add 操作：

public void add(int index, E element) {
    // 查看 index
    checkPositionIndex(index);
    
    // 如果 index 和 size 相等，阐明曾经到最初了，间接在 last 节点后插入节点接口
    if (index == size)
        linkLast(element);
    else // 否则就在 index 地位插入节点
        linkBefore(element, node(index));
}
复制代码

在 linkLast() 和 linkBefore() 办法里会波及到链表的操作，其中 LinkLast() 的实现比较简单，linkBefore() 略微简单一些，但只有学过数据结构的敌人，看这些源码应该没什么问题，在此不贴出源码了，比拟本文定位不是源码解析。

2.3 ArrayList 和 LinkedList 的区别

在后面的介绍中其实有说到过，在这里总结一下：

  1. ArayyList 是基于数组实现的，LinkedList 是基于链表实现的，因为实现不同，他们的效率之间必定是有差异的，ArrayList 的随机拜访效率较高，但插入操作会波及到数组拷贝，所以效率插入效率不高。LinkedList 的插入效率可高可低，如果是在尾部插入，因为有一个 last 节点，所以尾部插入的速度十分快，但在其余地位的插入效率并不高，对于随机拜访来说，因为须要从头开始遍历节点，所以随机拜访的效率并不高。
  2. 他们的继承体系略微有些区别，LinkedList 还实现了 Deque 接口，这是比拟有特点的。

3 SynchronizedList 和 Vector

之所以把他们俩发在一起是因为它们是线程平安的列表汇合。SynchronizedList 是 Collections 工具类里的一个外部动态类，实现了 List 接口，继承了 SynchronizedCollection 类，Vector 是 JDK 晚期的一个同步的 List，和 ArrayList 的继承体系齐全一样，而且也是基于数组实现的，只是他的各种办法都是同步的。

3.1 SynchronizedList

SynchronizedList 类是一个 Collections 类中包级公有的动态外部类，咱们在编写代码的时候无奈间接调用这个类，只能通过 Collection.synchronizedList() 办法并传入一个 List 来应用它，这个办法实际上就是帮咱们将原来没有同步措施的一般 List 包装成了 SynchronizedList，使其领有线程平安的个性，对其进行操作就是对原 List 的操作，如下所示：

public void add(int index, E element) {synchronized (mutex) {list.add(index, element);}
}
复制代码

3.2 Vector

Vector 是 JDK1.0 就有的类，算是一个远古期间的类了，在过后因为没有比拟好的同步工具，所以在并发场景下会应用到这个类，但当初随着并发技术的提高，有了更好的同步工具类，所以 Vector 曾经快成为半废除状态了。为什么呢？次要还是因为同步效率太低，同步伎俩太粗犷了，粗犷到间接将绝大多数办法弄成同步办法（在办法上退出 synchronized 关键字），连 clone 办法都没放过：

public synchronized Object clone() {
    try {@SuppressWarnings("unchecked")
            Vector<E> v = (Vector<E>) super.clone();
        v.elementData = Arrays.copyOf(elementData, elementCount);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}
复制代码

这样做尽管能确保线程平安，但效率切实太低了啊，尤其是在竞争强烈的环境下，效率可能还不如单线程。相比之下，SynchronizedList 就好很多，只是在必要的中央进行加锁而已（不过实际上效率还是挺低的）。基于它的 CRUD 操作就不多说了，和 ArrayList 没什么大的区别。

SynchronizedList 和 Vector 的区别

他们最大区别就在同步效率，Vector 的同步伎俩过于粗犷以至于效率太低，SynchronizedList 的同步伎俩没那么粗犷，只是在有必要的中央进行同步而已，效率较 Vector 会好一些，但实际上也不会太好，比拟同步伎俩比拟繁多，只是用内置锁一种计划而已。

4 HashMap、HashTable 和 ConcurrentHashMap

当咱们想要存储键值对或者说是想要表白某种映射关系的时候，都会用到 HashMap 这个类，HashTable 则是 HashMap 的同步版本，是线程平安的，但效率很低，ConcurrentHashMap 是 JDK1.5 之后代替 HashTable 的类，效率较高，所以当初在并发环境下个别不再应用 HashTable，而是应用 ConcurrentHashMap。

顺便说一下，ConcurrentHashMap 是在 J.U.C 包下的，该包的次要作者是 Doug Lea，这位大佬简直一个人撑起了 Java 并发技术。

4.1 HashMap

HashMap 的内部结构是数组（称作 table）+ 链表（达到阈值会转换成红黑树）的模式。数组和链表存储的元素都是 Node，如下所示：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey() { return key;}
    public final V getValue() { return value;}
    public final String toString() { return key + "=" + value;}

    public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {if (o == this)
            return true;
        if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}
复制代码

当向 HashMap 插入键值对的时候，会先拿 key 进行 hash 运算，失去一个 hashcode，而后依据 hashcode 来确定该键值对（最终的模式上其实是 Node）应该搁置在 table 的哪个地位，这个过程中如果有 Hash 抵触，即 table 中该地位曾经有了 Node 节点 A，那么就会将这个新的键值对插入到以 A 节点为头节点的链表中（此尾插法，在 JDK1.8 中改为头插法），如果在遍历链表的途中遇到 key 雷同的状况，那么就间接用新的 value 值替换到原来的值，这种状况就不再创立新的 Node 了，如果在途中没有遇到的话，就在最初创立一个 Node 节点，并将其插入到链表开端。

对于 HashMap 更多的内容，例如什么并发扩容导致的问题，以及扩容因子对性能的影响等等，倡议网上搜寻，网上这样的文章十分十分多，多到关上一个社区，都 TM 是将 HashMap 的文章 …..

4.2 HashTable

HashTable 的算法实现和 HashMap 并没有太多区别，能够简略把 HashTable 了解成 HashMap 的线程平安版本，HashTable 实现线程平安的伎俩也是十分粗犷的，和 Vector 简直一样，间接将绝大多数办法设置成同步办法，如下所示：

public synchronized boolean contains(Object value) {if (value == null) {throw new NullPointerException();
    }

    Entry<?,?> tab[] = table;
    for (int i = tab.length ; i-- > 0 ;) {for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {if (e.value.equals(value)) {return true;}
        }
    }
    return false;
}
复制代码

所以，其效率能够说是非常低的，个别很少用了，而是应用接下来要讲到的 ConcurrentHashMap 代替。

4.3 ConcurrentHashMap

该类位于 java.util.concurrent（简称 J.U.C）包下，是一款优良的并发工具类。ConcurrentHashMap 外部元素的存储构造和 HashMap 简直一样，都是数组 + 链表（达到阈值会转换成红黑树）的构造。不同的是，CouncurrentHashMap 是线程平安的，但并不像 HashTable 那样粗犷的在每个办法上退出 synchronized 内置锁。而是采纳一种叫做“分段锁”的技术，将一整个 table 数组分成多个段，每个段有不同的锁，每个锁只能影响到本人所在的段，对其余段没有影响，也就是说，在并发环境下，多个线程能够同时对 ConcurrentHashMap 的不同的段进行操作。成果就是吞吐量进步了，效率也比 HashTable 高很多，但麻烦的是一些全局性变量不太好保障一致性，例如 size。

对于 ConcurrentHashMap 更多的内容，还是倡议自行查找材料，网上有很多剖析 ConcurrentHashMap 的优良文章。

4.4 HashMap、HashTable 和 ConcurrentHashMap 的区别

其实下面几个大节都始终有比拟，就在这里总结一下：

  1. HashTable 是 HashMap 的同步版本，但因为同步伎俩太粗犷，效率较低，ConcurrentHashMap 在 JDK1.5 之后呈现，是 HashTable 的代替类，在此之前，如果想要保障 HashMap 的线程平安，要么应用 HashTable，要么应用 Collections.synchronizedMap 来包装 HashMap，但这两个计划的效率都比拟低。
  2. 他们三者的实现形式简直一样，外部存储构造并没有什么差异。
  3. HashTable 简直处于半废除的状态，不倡议在新我的项目中应用了，举荐应用 ConcurrentHashMap。

5 Java8 中 Stream 对汇合类的加强

Java8 中除了 lambda 表达式，最大的个性就是 Stream 流了。Stream API 能够将汇合看做流，汇合中的元素看做一个一个的流元素。这样的形象能够将对汇合的操作变得很简略、清晰，例如在以前要想合并两个汇合，就不得不做创立一个新的汇合，而后遍历两个汇合将元素放入到新的汇合中，但用流 API 的话就非常简单了，只须要将两个汇合看做两个流，间接将两个流合成一个流即可。

Stream API 还提供了很多高阶函数用于操作流元素，流入 map，reduce，filter 等，上面是一个应用 Stream API 的示例：

public void streamTest() {Random random = new Random();
    List<Integer> integers = IntStream.generate(() -> random.nextInt(100))
            .limit(100).boxed()
            .collect(Collectors.toList());

    integers.stream().map(num -> num * 10)
            .filter(num -> num % 2 == 0)
            .forEach(System.out::println);
}
复制代码

就这几行代码，实际上只能算是三行代码，就实现了随机生成元素放入 list 中，并且做了一个 map 操作和 filter 操作，还顺带遍历了一下 List。如果要用以前的办法，就不得不这样写：

public void originTest() {Random random = new Random();
    List<Integer> integers = new ArrayList<>();
    for (int i = 0; i < 100; i++) {integers.add(random.nextInt(100));
    }
    for (int i = 0; i < 100; i++) {integers.set(i, integers.get(i) * 10); //map
    }
    for (int i = 0; i < 100; i++) {if (integers.get(i) % 2 == 0)  //filter
            System.out.println(integers.get(i)); //foreach
    }
}
复制代码

这三个 for 循环看起来切实是难看。这就是 Stream API 的长处，简洁，不便，形象水平高，但可读性会差一些，如果对 lambda 和 Stream 不相熟的敌人第一次看到可能会比拟吃力（但实际上，这是很简略的代码）。

那是不是当前对汇合的操作都应用 Stream API 呢？别那么极其，Stream API 的确简洁，但可读性很差，Debug 难度十分高，更多的时候是靠人肉 Debug，而且性能上可能会低于传统的办法，也有可能高，所以，我的倡议是：在应用之前，最初先测试一下，将两种计划比照一下，最终依据测试后果筛选一个比拟好的计划。

6 小结

汇合类是 Java 开发者必须要把握的，通过浏览源码了解它们比看文章详解来的更加粗浅。本文只是简略的讲了几个罕用的汇合类，还有很多其余的例如 TreeMap，HashSet，TreeSet，Stack 都没有波及，不是说这些汇合类不重要，只是受篇幅限度，无奈一一道来，心愿读者能好好认真看看这些类的源码，看源码的时候不须要从头看到尾，能够先看几个罕用的办法，例如 get，put 等，而后一步一步跟进去，也能够应用调试器单步跟踪代码。

退出移动版