数据结构

本文最后更新于：1 年前

Reference

数据结构比较

数据结构选择

Java 中数据结构的体现

数组（Array）

数组是一种效率最高的存储和随机访问对象引用序列的方式。数组就是一个简单的线性序列，这使得元素访问非常快速。但是这种速度所付出的代价是数组对象的大小被固定，并且在其生命周期中不可改变。

ArrayList

与数组相比：可变长度。
可变长度的实现原理：每当添加元素时，都会检查内部数组的大小是否够用，不够用时会扩容。
优化：尽量避免触发扩容。ArrayList 默认大小是 10，创建时估计好容量，使用带参数的构造方法创建。

允许元素为 null。

扩容？
扩容时会以当前容量的 1.5 倍大小重新创建数组，并将原数据复制到新数组中。

Vector

与 ArrayList 相比：线程安全、扩容时是 2 倍。
线程安全的实现原理：方法上使用 synchronized 关键字。

Stack

基于 Vector 实现，线程安全。

ArrayDeque

双向循环队列。当作为栈使用时，性能比 Stack 好；当作为队列使用时，性能比 LinkedList 好。
与 Stack 相比：线程不安全。

双向循环队列实现原理：引入两个游标，head 和 tail，如果向队列里插入一个元素，就把 tail 向后移动（如果 tail 已经指向了数组的最后一位，需要将 tail 重新指向数组的头）；如果从队列中删除一个元素，就把 head 向后移动。

初始容量是 2 的幂次方，扩容时是 2 倍。

PriorityQueue

优先队列。
优先队列实现原理：逻辑结构是堆。默认是小顶堆，可以通过比较器改为大顶堆。

  • 默认容量是 11，容量小于 64 时，扩容 2 倍 + 1；否则 扩容 1.5 倍。
  • 数组从 0 开始存数据，计算父节点索引使用(k - 1) >>> 1。
  • 不允许元素为 null。

堆的性质？

  1. 完全二叉树，与二叉树相比：叶子节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层的最左边；
  2. 堆中某个节点的值总是不大于（或不小于）其父节点的值，同一层节点的值不存在大小关系。

堆的插入

1、把新元素插入到最后一个节点往后一位的位置；
2、将新元素和父节点比较，如果新元素不大于父节点，就把新元素放在这个位置，否则，就交换它们的位置；循环执行此步骤。

为什么索引 0 不存元素？
方便通过索引/2的操作获取父节点的索引。

堆的删除

堆的删除特指删除堆顶元素。

把最后一个节点放到堆顶，然后与左、右子节点中小的节点交换位置；循环执行此步骤。

为什么 ArrayList 没有像 LinkedList 一样直接实现栈或双端队列？
因为 ArrayList 从队列头删除元素时，要把后面的元素向前拷贝，性能低。

链表（Linked List）

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

LinkedList

与链表相比：LinkedList 是双向链表。

允许元素为 null。

LinkedList 实现了栈和双端队列。

数组 + 链表 = 哈希表（Hash Table）

数据经过哈希算法之后得到的集合。这样关键字和数据在集合中的位置存在一定的关系，可以根据这种关系快速查询。

HashMap

与哈希表相比：

在 JDK 1.7 及以前，HashMap 的数据结构是数组 + 单向链表。
在 JDK 1.8 之后，HashMap 的数据结构在初始化的时候是数组 + 单向链表，链表会改为红黑树优化。

  • 最大容量是 2^30。
  • 容器没有在构造函数中初始化，而是在第一次插入时进行初始化，且会计算为 2 的幂次方，初始化时会进行第一次扩容。
  • 默认容量大小是 16，负载因子是 0.75，所以当插入第 13 个元素时会进行第二次扩容，扩容倍数是 2 倍。
  • 如果容量大于或等于 64 且链表大小大于或等于 8 时，链表改为红黑树，当链表大小小于或等于 6 时，红黑树改为链表。

优化：尽量避免触发扩容。HashMap 默认不触发扩容大小是 16 * 0.75 = 12，创建时估计好容量，使用带参数的构造方法创建。

允许 null 键和 null 值。

为什么不将链表全部换成红黑树？

  1. 由于数据量的不同，数组 + 链表 + 红黑树的结构不一定比数组 + 链表的结构性能高；
  2. HashMap 扩容时会重新计算节点的索引位置，也就是会将红黑树进行拆分和重组。

改变负载因子的后果？
负载因子过高会导致链表过长，查找键值对时间增加，负载因子过低会导致扩容频率增加。

HashMap 工作原理

插入

将 K/V 键值传给 put() 方法：
1、调用 hash(K) 方法计算 K 的 hash 值，然后结合数组长度，计算得数组下标；
2、如果 K 的 hash 值在 HashMap 中不存在，则执行插入；否则，发生 hash 冲突；
（3、发生 hash 冲突时，如果 equals 返回 true，则更新键值对；否则，插入链表（JDK 1.7 之前使用头插法、JDK 1.8 开始使用尾插法）或者红黑树中（树的添加方式）；）
（4、调整数组大小。当容器中的元素个数大于阈值时，容器会进行扩容。）

如何计算数组索引位置？

1
2
3
4
5
6
7
8
9
10
11
12
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
    ...
}
  1. (h = key.hashCode()) ^ (h >>> 16)：将 key 的 hashCode 值及其无符号右移16位后的值进行异或操作；
  2. i = (n - 1) & hash：将 hash 值与数组大小 - 1 的值取与。

为什么不直接使用 hashCode？
如果使用(n - 1) & hashCode，因为 n 的值一般情况下很小，基本上只有 hashCode 的低 16 位能参与计算，这会导致数据在数组中分布不均匀；(h = key.hashCode()) ^ (h >>> 16)是让 hashCode 的高 16 位也能间接参与计算，使数据在数组中均匀分布。

为什么使用 (n - 1) & hash 而不使用 hash % n ？
结果是等价的。但是 & 是二进制直接计算，效率高。
当数组大小是 2 的幂次方，也就是一个合数时，可能会导致 hash 冲突概率更高，因为质数比合数更保险。但是 2 的幂次方有利于(n - 1) & hash运算，如果是合数会导致有几个位置不可用，肯定会增加 hash 冲突的概率，而且质数扩容后也得是质数。所以 2 的幂次方和(n - 1) & hash的效率至少不低于质数 + hash % n。

扩容？
扩容时会以当前容量的 2 倍大小重新创建数组，并重新计算数据在数组中的位置。新位置可能是原位置，也可能是原位置 + 原数组大小。

读取

将 K 传给 get() 方法：
1、调用 hash(K) 方法计算 K 的 hash 值，然后结合数组长度，计算得数组下标；
2、遍历链表，使用 equals() 方法查找相同 K 值对应的 V 值。

HashTable

已被 ConcurrentHashMap 取代。

与 HashMap 相比：

1、线程安全。
线程安全的实现原理：方法用 synchronized 修饰。

2、HashTable 的数据结构是数组 + 单向链表。

  • 最大容量是 Integer.MAX_VALUE - 8。
  • 容器在构造函数中初始化。
  • 默认容量大小是 11，负载因子是 0.75，所以当插入第 9 个元素时会进行第一次扩容，扩容倍数是 2 倍 + 1。

优化：尽量避免触发扩容。HashTable 默认不触发扩容大小是 11 * 0.75 = 8.25，创建时估计好容量，使用带参数的构造方法创建。

不允许 null 键或 null 值。

HashTable 为什么不允许 null 键或 null 值？

  1. 作者希望每个 key 都会实现 hashCode 和 equals 方法；
  2. HashTable 开发时间早于 HashMap，是一个过时的类。

HashTable 工作原理

插入

将 K/V 键值传给 put() 方法：
1、计算数组下标；
2、如果 K 的 hash 值在 HashTable 中不存在，则执行插入；否则，发生 hash 冲突；
（3、发生 hash 冲突时，如果 equals 返回 true，则更新键值对；否则，插入链表；）
（4、调整数组大小。当容器中的元素个数大于或等于阈值时，容器会进行扩容。）

如何计算数组索引位置？

1
2
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

ConcurrentHashMap

与 HashMap 相比：

1、线程安全。
线程安全的实现原理：JDK 1.7 使用分段锁、JDK 1.8 使用 CAS（无锁算法） + synchronized（ConcurrentHashMap 是 JDK 1.5 推出的，在 JDK 1.6 时 JVM 引入偏向锁、轻量锁，等到 JDK 1.8 才优化）。

不允许 null 键或 null 值。

  • 默认并发数量是 16（即 segment 数组的大小），最大是 2^16，会计算为 2 的幂次方。

ConcurrentHashMap 有 fail-safe 机制。

fail-fast 和 fail-safe 机制？

  1. fail-fast 机制确保了遍历或多线程操作时，如果改变结构，就会抛出 ConcurrentModificationException，实现原理是通过变量 modCount 记录修改次数，在遍历时会判断 expectedModCount 是否和 modCount 相等。
    大部分非同步的类都支持 fail-fast，而且 Vector 和 HashTable 也支持，用于迭代器遍历。
  2. fail-safe 机制确保了改变结构时不会抛出 ConcurrentModificationException，实现原理是在原集合的 copy 上遍历，这会导致额外的空间和时间的开销，并且不能保证遍历的是最新的内容。

ConcurrentHashMap 分段锁的原理？

ConcurrentHashMap 持有一组锁（segment 数组），当写操作发生在不同的锁中时，就可以并行操作，实现了并发写；同时用 volatile 修饰 HashEntry 的 value，确保了并发读的一致性。

Segment 为什么能当锁？
Segment 类继承于 ReentrantLock 类。

volatile 作用？

  1. 实现有序性：比如确保实例化对象的顺序——1）分配内存空间、2）初始化对象、3）将内存空间的地址赋值给对应的引用；原理是 volatile 会转换为 CPU 的 lock 指令，建立内存屏障；
  2. 实现多线程可见性：每个线程拥有自己的一个高速缓存区内存，其他线程不可见，修改 volatile 修饰的变量时会强制将修改后的值刷新到主内存中，同时让其他线程中缓存的该变量的值失效，读取时使用主内存的值；
  3. 只能保证单次操作的原子性，所以无法完全代替 synchronized。

为什么使用 CAS + synchronized 取代分段锁？
在 JVM 中，对象在内存中的布局分为三块区域：对象头、实例数据和对齐填充。synchronized 是靠对象头和此对象对应的 monitor 来保证上锁的，也就是对象头里的重量级锁标志指向了 monitor，而 monitor 内部则保存了一个当前线程，也就是抢到了锁的线程。
synchronized 和 ReentrantLock 开销差距是释放锁时唤醒线程的数量，synchronized 是唤醒锁池里所有的线程 + 刚好来访问的线程，而 ReentrantLock 是当前线程后进来的第一个线程 + 刚好来访问的线程。synchronized 由于 JVM 优化后会经历偏向锁、轻量锁、自旋锁，不是重量级锁不存在线程挂起和唤醒的过程，所以性能高于 ReentrantLock。

链表 + 哈希表

LinkedHashMap

HashMap 的子类，与 HashMap 相比：保存了记录的插入顺序。
保存插入顺序的原理：使用双向链表，重写 newNode 方法，插入的同时会调用 linkNodeLast 方法将新元素插入链表。

树（Tree）

二叉查找树（Binary Search Tree）

与树相比：最多有两棵子树，左子树上所有结点的值均小于它的根结点的值，右子树上所有结点的值均大于它的根结点的值。

红黑树（Red-Black Tree）

与二叉查找树相比：一个枝叶分布非常平均的二叉树，所以不管访问哪个元素，时间复杂度都不会特别离谱。

  • 每个节点是红色或黑色；
  • 叶子节点（NIL）是黑色；
  • 根节点是黑色；
  • 不能有两个连续的红色节点；
  • 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

这些性质强制了红黑树的关键性质：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

在插入和删除元素时，可能需要旋转才能保持红黑树。

左旋

右旋

插入

1、为了避免违背性质 5，将插入的新节点着色为"红色"；
2、将红黑树当作一颗二叉查找树，将新节点插入；
3、插入后修复：
（1）父节点为黑色时——插入完成。
（2）父节点为红色且有叔叔节点（叔叔节点此时必为红色）时——让父辈节点都变黑色，爷爷节点变红色。此时爷爷节点相当于新插入的节点；

（3）只有红色父节点，且新节点、父节点、爷爷节点处于一侧时——让父节点旋转，同时父节点和爷爷节点变色。此时爷爷节点相当于新插入的节点；

（4）只有红色父节点，且新节点、父节点、爷爷节点不处于一侧时——先让新节点和父节点通过旋转变为同侧，再执行（3）；

删除

1、将红黑树当作一颗二叉查找树，将节点删除（被删除节点有两个子树时，将被删除节点替换为右子树最小值或左子树最大值的节点，这样就将有两个子树的节点转为最多只有一个子树的节点）；
2、删除后修复：
（1）被删除节点是红色节点时——删除完成。
（2）被删除节点是黑色节点，且兄弟节点是红色时——让兄弟节点旋转，同时父节点和兄弟节点变色，此时新的兄弟节点是黑色的，变为（3）（4）（5）之一；

（3）被删除节点是黑色节点，且兄弟节点是黑色，且兄弟节点的子节点都是黑色时——让父节点和兄弟节点变色。此时父节点相当于新插入的节点；

（4）被删除节点是黑色节点，且兄弟节点是黑色，且兄弟节点的近端子节点是黑色时——让兄弟节点旋转，同时兄弟节点的右节点变色。

（5）被删除节点是黑色节点，且兄弟节点是黑色，且兄弟节点的远端子节点是黑色时——让兄弟节点旋转，同时兄弟节点和近端子节点变色，在执行（4）；

TreeMap

与红黑树区别：允许 null 键和 null 值。

数据结构
https://weichao.io/44f2184e1eee/
作者
魏超
发布于
2020年3月12日
更新于
2022年12月4日
许可协议