数据结构 笔记 Easy Coding 集合 HashMap ArrayList

《码出高效》系列笔记（四）：数据结构与集合的框架篇

向代码致敬，寻找你的第[83]行。

Posted by MatthewHan on 2020-03-10

良好的编码风格和完善统一的规约是最高效的方式。

前言

本篇汲取了本书中较为精华的知识要点和实践经验加上读者整理，作为本系列里的第四篇章第一节：数据结构与集合的框架篇。

本系列目录：

数据结构

Java中的集合不同于数学概念，可以是有序的，也可以是重复的。而集合作为数据结构的载体，同时也作为程序的主要构成，是所有编程语言的基础。

数据结构的分类：

  1. 线性结构：0至1个直接前继和直接后继。当线性非空时，有唯一的首元素和尾元素，除两者外，所有的元素都有唯一的直接前继和直接后继。该类结构一般有：顺序表、链表、栈、队列等，其中栈、队列是访问受限的结构。
  2. 树结构：0至1个直接前继和0至n个直接后继（n大于等于2）。具有层次、稳定的特性，类似大自然的树木。
  3. 图结构：0至n个直接前继和直接后继（n大于等于2）。该类结构一般有：简单图、多重图、有向图、无向图等。
  4. 哈希结构：没有直接前继和直接后继。该结构是通过某种特定的哈希函数将索引与存储的值关联起来，是一种查找效率非常非常高的数据结构。

复杂度：

数据结构的复杂度分为时间复杂度和空间复杂度两种，因为目前存储设备的技术进步，时间复杂度成为了重点考量的因素。

时间复杂度是一种衡量计算性能的指标。通常用大写的O和一个函数描述，比如O(n3)表示程序执行时间随输入规模呈现三次方倍的增长，这是比较差的算法实现。

从好到坏的常用算法复杂度排序如下：常数级 O(1)、对数级 O(logn)、线性级 O(n)、线性对数级 O(nlogn)、平方级 O(n2)、立方级 O(n3)、指数级 O(2n)。

集合框架

Java中的集合是用于存储对象的工具类容器，实现了我们上述所说的这些的数据结构，提供了一系列的公开方法用于增删改查以及遍历数据，让宁⑧用自己写轮子辣！

这里本来应该有一张Java结合框架图的，不过都应该烂熟于心了⑧。除了Map没有直接继承collection接口，Queue、List、Set均是直接继承collection接口。

List集合

List集合是线性数据结构的主要实现，所以集合的元素通常明确上一个和下一个元素，也存在第一个和最后一个元素。

ArrayList是容量可变的非线程安全集合。内部使用数组进行存储，扩容时会创建更大的数组空间，然后再把原来的数据复制到新的数组中。该集合支持对元素的随机访问，插入与删除速度通常很慢，因为涉及到移动元素（数组）。

LinkedList的本质是双向链表。与ArrayList相比，插入和删除的速度更快，但是随机访问的速度很慢。LinkedList包含了3个重要的成员：size、first、last。size是双向链表中节点的个数。first和last分别指向第一个和最后一个节点的应用。

Queue集合

先进先出，一种特殊的线性表，只允许表在一端进行获取操作，在另一端进行插入操作。当不存在元素时，则为空队列。自从BlockingQueue（阻塞队列）问世以来，队列的地位得到极大地提升，在各种高并发编程的场景，经常被作为Buffer（数据缓冲区）使用。

Map集合

Map集合是以Key-Value键值对作为存储元素实现的哈希结构，Key安某种哈希函数计算后是唯一的，Value是可以重复的。

  • 可以使用keySet()方法查看所有的Key；
  • 使用values()方法查看所有的Value；
  • 使用entrySet()方法查看所有的键值对。

Hashtable因为性能瓶颈原因已被淘汰，如今广泛使用HashMap，但是是线程不安全的，底层也就是数组 + 链表。ConcurrentHashMap是线程是安全的，在JDK8中进行了锁的大幅度优化，体现了8错的性能。

在多线程并发的场景中，优先推荐使用ConcurrentHashMap，而不是HashMap。

TreeMap是Key有序的Map类集合，树结构保证有序，Key⑧能为null。

LinkedHashMap底层是链表结构，较与HashMap可以保元素的有序。

Set集合

Set是不允许出现重复元素的集合类型。Set体系最常用的是HashSet、TreeSet和LinkedHashSet三个集合类。

HashSet与HashMap较为类似，只是Value固定为一个静态对象，使用Key保证集合元素的唯一性，但它不保证集合元素的顺序。

TreeSet也是如此，与TreeMap类似，同样底层是树结构，保证有序，元素不能为null。

LinkedHashSet继承自HashSet，具有HashSet的优点，使用链表维护了元素插入顺序。

集合初始化

集合初始化通常进行分配容量、设置特定参数等相关工作。

该书中特别强调例如ArrayList在初始化的过程中，需要显式地设定集合容量大小。

ArrayList部分源码解析

本书分析的底层源码基本来源于较新的JDK11，而在我本地的源码是JDK8，下面分析的是本地的JDK8源码。

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
/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
  	// ①
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
  	// ②
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
  if (minCapacity < 0) // overflow
    throw new OutOfMemoryError();
  return (minCapacity > MAX_ARRAY_SIZE) ?
    Integer.MAX_VALUE :
  	MAX_ARRAY_SIZE;
}

上述代码是JDK8中的源码，扩容在grow()方法里完成。而在JDK11中，扩容的具体实现则是由newCapacity()方法实现。

首先我们明确几个概念：

  1. oldCapacity：当前容量，由于要扩容了所以是老的容量数值；
  2. newCapacity：扩容后的容量大小；
  3. minCapacity：扩容的必须满足最小的要求！源码是size + 1，也就是当前的容量 + 1。

  • 什么时候扩容？

    JDK8的源码部分没贴上来，调用的方法太多了占内容空间。如果原始容量为10，当第11个元素即将调用add()方法时会启动grow()方法启动扩容机制，JDK11同理。

  • 默认的容量大小是什么？

    如果没有显式的初始化容量大小，那么在最开始，容量大小其实是0而不是默认的10哦。当显式的设定了容量大小，那么容量大小会赋设定的值。只有当调用add()方法时才会启动扩容，变成默认DEFAULT_CAPACITY = 10，大小为10。所以不显式的初始化容量大小，调用add()方法的话时必定会扩容一次的。

    1
    2
    3
    4
    5
    6
    List<String> list = new ArrayList<>();
    Class<?> listClazz = list.getClass();
    Field elementData = listClazz.getDeclaredField("elementData");
    elementData.setAccessible(true);
    Object[] objects1 = (Object[])elementData.get(list);
    System.out.println("不显式的初始化，容量大小为：" + objects1.length);

    上述代码输出不显式的初始化，容量大小为：0

    1
    2
    3
    4
    // add一个元素
    list.add("回家做80个俯卧撑！");
    Object[] objects2 = (Object[])elementData.get(list);
    System.out.println("添加一个元素，现在容量大小为：" + objects2.length);

    接着添加一个元素，运行输出添加一个元素，现在容量大小为：10

    1
    2
    3
    4
    5
    6
    List<String> list2 = new ArrayList<>(666);
    Class<?> newListClazz = list2.getClass();
    Field elementData2 = newListClazz.getDeclaredField("elementData");
    elementData2.setAccessible(true);
    Object[] objects3 = (Object[])elementData.get(list2);
    System.out.println("显式初始化容量大小为666，容量大小为：" + objects3.length);

    显式初始化容量大小为666，运行输出显式初始化容量大小为666，容量大小为：666

  • 如何扩容？

    • JDK8之前的扩容算法与JDK8有所不同，源码中上述方法里，int newCapacity = oldCapacity + (oldCapacity >> 1);扩容后的容量大小算法是通过右移一位再加上老容量大小得到。
      • 位移运算：JDK8中采用了（有符号）位运算符计算，位移的过程中采用补码的形式。假设原始容量为13，二进制数是1101，其中反码也是1101，整数的反码、补码都是本身。补码右移一位这是110，得到十进制为6，所以新的容量大小为6 + 13 = 19。JDK7之前的公式则是oldCapacity * 1.5 + 1；
    • ①：如果新的容量大小比最小要求要小的话，则按照最小要求设定（size + 1）；
    • ②：如果新的容量大小比MAX_ARRAY_SIZE还大的话，其中该变量的大小为Integer.MAX_VALUE - 8也就是231-1再减8。在走hugeCapacity(int minCapacity)方法判断最后设定一个容量大小或者OOM了。

之所以本手册中明确强调需要显式的初始化容量大小，是因为假设有1000个元素需要放置在ArrayList中，则需要被动扩容13次才可以完成，在这过程中数组不断地复制原有的数据再到新的数组中，若能够提前给定一个合适的容量大小，就是性能的提升，也避免了一些OOM的风险。OS：这过程更像是调优，实际开发中很难对每个ArrayList清晰的定义和认识吧，属于经验学的范畴。

嗯？！感觉关于ArrayList的可以单独出一篇啊。

HashMap部分源码解析

本书分析的底层源码基本来源于较新的JDK11，而在我本地的源码是JDK8，下面分析的是本地的JDK8源码。

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
/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/* ---------------- Fields -------------- */
/**
  * The table, initialized on first use, and resized as
  * necessary. When allocated, length is always a power of two.
  * (We also tolerate length zero in some operations to allow
  * bootstrapping mechanics that are currently not needed.)
  */
transient Node<K,V>[] table;
  • DEFAULT_INITIAL_CAPACITY：默认初始容量1 << 4，aka 16，必须是2n幂，注解里很直白的写着，所以你即使在初始化的过程这样写new HashMap<>(3);，实际上也会被改成22，比3大且最近的一个2的幂次方；
  • MAXIMUM_CAPACITY：最大容量大小，默认1 << 30，相当于230；
  • DEFAULT_LOAD_FACTOR：负载因子，也叫填充比例，默认0.75，可在初始化过程中自定一个float类型的数值。
  • table：

HashMap和ArrayList一样，容量不是在new的时候分配，而是在第一次put的时候。

put、putVal()、reszie()方法有些晦涩复杂就不贴上来了。很多细节，👴属实有点看不明白。这里有个概念threshold作为临界值就是loadfactory（负载因子）和capacity（容量）的乘积。也就是说默认情况下，当HashMap中元素个数达到了容量的3/4的时候就会进行自动扩容。

  • 为什么负载因子是0.75？

    JDK源码里这样写，一定有它的道理，这里不太想去探究。查阅网上的资料，和哈希冲突有很大关系，以及一些数学计算、log2、对数之类的有一定关系，反正一般不要去自己去设定就vans了。

  • 什么时候扩容？

    • 和ArrayList一样，到了某个临界值才会被动扩容，而且扩容的过程中会重新计算所有元素的哈希值。扩容的条件是达到了threshold这个参数，而它是capacity和loadfactory的乘积，所以我们可以通过代码来验证一下：

    • ```java
      Map map = new HashMap<>(0);
      Class<?> mapClazz = map.getClass();
      Method capacity = mapClazz.getDeclaredMethod(“capacity”);
      capacity.setAccessible(true);
      System.out.println(“容量大小为：” + capacity.invoke(map));

      1
      2
      3
      4
      5
      6

      - 输出`容量大小为：1`，因为是2<sup>0</sup>

      - ```java
        map.put("MatthewHan", "developer");
        System.out.println("添加一个元素后，容量大小为：" + capacity.invoke(map));

    • put一个元素之后，查看capacity大的大小，输出添加一个元素后，容量大小为：2。为什么不是1呢，因为capacity和loadfactory的乘积是0.75 * 1 < 1，满足扩容的条件。所以从20扩容成了21。当然你这样写new HashMap<>(0, 1f);输出的就是1了。

  • 以前看到过的一道美团笔试题：如果一个HashMap要装载100个元素，那么初始化容量大小是设定最佳？

    • 最佳的大小，一定是满足不会多次扩容调用resize()方法的。所以就是一定要大于100 ÷ 0.75 = 133.333...，比该数大且最接近的2n的是28 = 256。而27 = 128看起来比100大，但是需要多扩容一次，全部重新计算哈希算法，属实⑧行。上面写了目前对时间性能的要求远远大于空间，用空间换时间。
    • 或者可以这样new HashMap<>(128, 0.79f);但是一般不会改变负载因子的值，该方法实际表现未知。
CATALOG
    FEATURED TAGS
    数据结构 笔记 Easy Coding 集合 HashMap ArrayList
    FRIENDS