《码出高效》系列笔记(四):数据结构与集合的框架篇

向代码致敬,寻找你的第[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接口,QueueListSet均是直接继承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体系最常用的是HashSetTreeSetLinkedHashSet三个集合类。

HashSetHashMap较为类似,只是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的时候。

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

  • 为什么负载因子是0.75?

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

  • 什么时候扩容?

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

    • ```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呢,因为capacityloadfactory的乘积是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);但是一般不会改变负载因子的值,该方法实际表现未知。