❮
❯
TOC
KINA

KINA-0

Start having fun with KINA right now!
分类 后端原理教程

集合框架源码解读：ArrayList、LinkedList、HashMap…

作者

本文剖析了Java集合框架中核心数据结构的源码，主要围绕最重要的ArrayList、LinkedList和HashMap。首先，介绍了数据结构的基本概念，如数组、链表、二叉树等概念。然后，详细分析了ArrayList与LinkedList之间的区别，特别是在存储结构和性能上的差异。接着，深入剖析了HashMap的实现原理，包括哈希表的工作机制、冲突解决方法以及扩容过程的细节。此外，文中还提及了JDK1.7和JDK1.8中HashMap的关键差异及多线程环境下的潜在问题。

Java集合框架

1 数据结构基础

相关资源：数据结构强化笔记

1.1 算法复杂度分析

时间复杂度表示算法的执行时间与数据规模之间的增长关系。
空间复杂度表示算法占用的额外存储空间与数据规模之间的增长关系。

大O表示法：$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(n^k)<O(2^n)<O(n!)$

1.2 数组

数组（Array）是一种用连续内存空间存储相同数据类型数据的线性数据结构。

数组

寻址：

  • 公式：数组的首地址 + 索引 × 存储数据的类型大小
  • 数组索引从0开始，因为若从1开始时，对于cpu来说增加了一个减法指令。

时间复杂度分析：

  • 随机存取：$O(1)$
  • 查找
    • 顺序查找：$O(n)$
    • 二分查找：$O(\log n)$
  • 插入、删除：平均 $O(n)$

1.3 链表

链表（Linked List）中的每一个元素称之为结点（Node），物理存储单元上，非连续、非顺序的存储结构。

1.3.1 单链表

每个结点包括两个部分——存储数据元素的数据域、存储下一个结点地址的后继指针next

单链表

查找、插入、删除的时间复杂度：

  • 头结点：$O(1)$
  • 其他结点：$O(n)$

1.3.2 双链表

结点除了有一个后继指针next指向后面的结点外，还有一个前驱指针prev指向前面的结点

双链表

查找、插入、删除的时间复杂度：

  • 头尾结点：$O(1)$
  • 其他结点：$O(n)$
  • 给定结点指针：$O(1)$

1.4 二叉树

⼆叉树（Binary Tree）：⼀种特殊的有序树，要么为空树，要么每个结点最多只有两棵⼦树，即结点的度只能为0、1、2，子树区分左右顺序（左、右子结点）。

二叉树

1.4.1 二叉搜索树

二叉搜索树（Binary Search Tree, BST）：一种常见的特殊二叉树，又名二叉排序树。

通常定义：

  1. 所有子树中，左儿子值 < 父结点值 < 右儿子值
  2. 没有键值相等的结点

时间复杂度分析：

  • 插入、删除：$O(\log n)$
  • 查找
    • 平均情况：$O(\log n)$
    • 最坏情况（退化成链表）：$O(n)$

二叉搜索树

1.4.2 红黑树

红黑树（Red Black Tree）：一种自平衡的二叉搜索树，曾称平衡二叉B树（Symmetric Binary B-Tree）。在添加或删除结点时，若不符合其定义会发生 $O(1)$ 时间复杂度的旋转，以满足其定义。

定义：

  1. 结点要么是红色，要么是黑色
  2. 根结点为黑色
  3. 叶结点均为黑色的空结点
  4. 红色结点的子结点均为黑色
  5. 从任一结点到叶子结点的所有路径都包含相同数目的黑色结点

查找、新增、删除时间复杂度：均为$O(\log n)$

红黑树

1.5 散列表

散列表（Hash Table）：又名哈希表。由数组演化而来的，利用了数组支持按照下标进行随机访问数据的特性，根据键（Key）直接访问内存中的值（Value）。

散列函数：将键映射为数组下标的函数，可表示为hashValue = hash(key)。基本要求如下

  • 计算结果应为大于等于0的整数
  • 若key1 == key2，则两者的哈希值也应相同，即hash(key1) == hash(key2)
  • 若key1 != key2，则两者的哈希值也必不相同，即hash(key1) != hash(key2)，实际几乎不可能完美实现

散列表

散列冲突：多个key映射到同一个数组下标位置。

拉链法：常用的冲突解决方法。数组的每个下标位置称为桶（Bucket）或者槽（Slot），每个桶（槽）对应一条链表，散列值相同的元素存储于相同槽位对应的链表中。

时间复杂度分析：

  • 插入：$O(1)$
  • 查找、删除
    • 平均情况：$O(1)$
    • 最坏情况（退化为链表）：$O(n)$
    • 改造成其他高效的动态数据结构（如红黑树）：$O(\log n)$

拉链法

将拉链法中的链表改造红黑树的另一个非常重要的原因：可以防止DDoS攻击
分布式拒绝服务攻击（Distributed Denial of Service，DDoS）：指处于不同位置的多个攻击者同时向一个或数个目标发动攻击，或者—个攻击者控制了位于不同位置的多台机器并利用这些机器对受害者同时实施攻击。由于攻击的发出点是分布在不同地方的，这类攻击称为分布式拒绝服务攻击，其中的攻击者可以有多个

2 List

2.1 ArrayList源码分析

常见属性

ArrayList常用属性

构造方法

ArrayList构造方法

新增元素和扩容操作

ArrayList新增元素和扩容操作

  • ArrayList底层是用动态的数组实现的
  • 初始容量为0，当第一次添加数据的时候才会初始化容量为10
  • 在进行扩容时，容量变成原来容量的1.5倍，每次扩容都需要拷贝数组
  • 在添加数据时
    • 确保数组已使用长度（size）加1之后足够存下下一个数据
    • 计算数组的容量，若当前数组已使用长度+1大于当前的数组长度，则调用grow()方法扩容（原来的1.5倍）
    • 确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。
    • 返回添加成功布尔值。

2.2 数组与List之间的转换

  • 数组转List：使用java.util.Arrays工具类的asList()静态方法
  • List转数组：使用List对象的toArray()方法。无参方法返回Object数组；传入初始化长度的数组对象，返回该对象数组

数组与List之间的转换

【问】转换后修改数据的后果：

  1. 用Arrays.asList()转List后，如果修改了数组内容，list受影响吗？
    【答】受影响。因为其底层使用Arrays类中的一个内部类ArrayList来构造集合，在该集合的构造器中，将传入的集合进行了包装而已，最终指向的都是同一个内存地址。
  2. List用toArray()转数组后，如果修改了List内容，数组受影响吗？
    【答】不受影响。调用了toArray后在底层进行了元素值的拷贝，因此即使list修改了以后，数组也不受影响。

转换后修改数据的后果

2.3 ArrayList与LinkedList的区别

  • 底层数据结构
    1. ArrayList是动态数组的数据结构实现
    2. LinkedList是双向链表的数据结构实现
  • 操作数据效率
    1. 随机存取：ArrayList为顺序存储，支持随机存取，即时间复杂度为 $O(1)$ ；LinkedList不支持随机存取
    2. 顺序查找：ArrayList与LinkedList均需遍历全表，时间复杂度均为 $O(n)$
    3. 插入、删除
      • ArrayList尾部增删的时间复杂度为 $O(1)$ ；其他部分增删需挪动元素，时间复杂度为 $O(n)$
      • LinkedList头尾结点增删的时间复杂度为 $O(1)$ ；其他均需遍历链表，时间复杂度为 $O(n)$
  • 内存空间占用
    1. ArrayList底层是数组，内存连续，节省内存
    2. LinkedList底层为双向链表，需要额外存储两个指针，更占内存
  • 线程安全
    1. ArrayList和LinkedList都不是线程安全的
    2. 若想保证线程安全，有两种方案：
      • 在方法内使用，局部变量是线程安全的
      • 使用线程安全的List（如下图所示）

使用线程安全的List

3 HashMap

3.1 实现原理

底层为哈希表，即 数组 + ( 链表 | 红黑树 )

  1. 当往HashMap中put元素时，利用hashCode()重新计算出当前对象元素的哈希值，即在数组中的下标
  2. 若出现哈希值相同，此时有两种情况
    • 若key相同，则覆盖原始值
    • 若key不同（出现冲突），则将值放入链表或红黑树中
  3. 获取时，直接找哈希值对应的下标，再进一步判断key是否相同，从而找到对应值

HashMap原理

在JDK1.7和JDK1.8中的区别

  • JDK1.8之前采用拉链法，即数组中每一格对应一条链表。若遇到哈希冲突，则将冲突的值加至链表中。
  • JDK1.8中，当链表的长度大于阈值（默认为8）且数组长度达到64时，将链表转换为红黑树，以减少搜索时间。扩容resize()时，若红黑树拆分成的树的结点数小于等于临界值6个，则退化成链表。

3.2 HashMap源码分析

常见属性

HashMap常见属性

构造函数

HashMap构造函数

3.2.1 put()方法的具体流程

添加数据流程图

put()方法的具体流程

  1. 判断键值对数组table是否为空或为null，否则执行resize()进行扩容（初始化）。
  2. 根据键计算哈希值得到数组索引。
  3. 判断table[i] == null，若条件成立，则直接新建、添加结点。
  4. 若上述条件不成立
    1. 判断table[i]的首个元素是否和键一样，若相同则直接覆盖值。
    2. 判断table[i]是否为treeNode（即是否是红黑树），若是，则直接在树中插入键值对。
    3. 遍历table[i]，在对应链表的尾部插入数据，并判断：当链表的长度大于8时，将链表转换为红黑树，在红黑树中执行插入操作。遍历过程中若发现键已存在则直接覆盖值。
  5. 插入成功后，判断实际存在的键值对数量size是否超过了最大容量threshold（数组长度*0.75，即填满75%），若超过则进行扩容。

3.2.2 扩容机制

扩容流程

扩容流程

  • 在添加元素或初始化时需要调用resize()方法进行扩容。第一次添加数据初始化数组长度为16，之后每次扩容均达到扩容阈值（数组长度*0.75）
  • 每次扩容时，均为将其容量翻倍
  • 扩容后会新创建一个数组，再把老数组中的数据挪到新数组中
    • 对于没有哈希冲突的结点，新数组中的索引为 e.hash & (newCap - 1)
    • 若为红黑树，则执行红黑树的结点插入操作
    • 若为链表，则需遍历链表。可能需要拆分链表：判断是否有 e.hash & oldCap == 0，即该元素要么停留在原始位置，要么移动到原始位置＋增加的数组大小

3.3 寻址算法

寻址算法

  • (h = key.hashCode()) ^ (h >>> 16)：扰动算法，使哈希值更加均匀，減少哈希冲突
  • (n - 1) & hash：得到数组中的索引，代替取模，性能更好，数组长度必须是2的n次幂

数组长度必须是2的n次幂的原因

  1. 计算索引时效率更高：2的n次幂可以使用位与运算代替取模
  2. 扩容重新计算索引效率时更高：满足 hash & oldCap == 0 的元素留在原来位置，否则新位置 = 旧位置+ oldCap

3.4 在JDK1.7中的多线程死循环问题

HashMap在JDK1.7中的数据结构为：数组+链表
在数组进行扩容时，链表使用头插法，有可能导致死循环

下图中变量e指向需要迁移的对象，变量next指向下一个需要迁移的对象，可见在数据迁移的过程中并没有新的对象产生，只是改变了对象的引用

在JDK1.7中的多线程死循环问题

【例】
线程1：读取到当前的hashmap数据，数据中一个链表在准备扩容时，线程2介入
线程2：也读取hashmap，直接进行扩容。因为是头插法，链表的顺序会颠倒（原来的顺序为AB，扩容后的顺序为BA）。线程2执行结束
线程1：继续执行时就会出现死循环问题——线程1先将A移入新的链表，再将B插入到链头，由于线程2的原因，B的next指向了A，所以B->A->B，形成循环。

在JDK1.8中将扩容算法进行了调整，链表改用尾插法，避免了上述的死循环问题。

发表评论