数据结构

数据结构是计算机底层存储、组织数据的方式

为了更加方便的管理和使用数据，结合具体的业务场景

  • 每种数据结构长什么样子
  • 怎么添加数据
  • 怎么删除数据

常见数据结构：

  1. 栈
  2. 队列
  3. 数组
  4. 链表
  5. 二叉树
  6. 二叉查找树
  7. 平衡二叉树
  8. 红黑树

1.栈

  • 先进后出，后进先出

    1
    2
    可以理解为打枪
    吃东西吐出来🤮

  • 数据进栈/压栈

    1
    栈顶/栈底

  • 弹栈/出栈

1
main方法最后出栈

2.队列

  • 先进先出，后进后出

    1
    2
    3
    4
    前端/后端 两端都是开口的

    可以理解为排队买票
    吃东西拉出来💩

  • 数据从后端进入队列模型：入队列

  • 数据从前端离开队列模型：出队列

3.数组

  • 查询快，增删慢的模型

  • 查询速度快：通过地址值和索引定位，查询任意数据耗时相同（元素在内存中是连续存储的）

  • 删除效率低：将原始数据删除，同时后面每个数据前移

  • 添加效率低：添加位置后的每个数据后移，再添加元素

4.链表

  • 链表中的结点是独立的对象，在内存中是不连续的，每个结点包含数据值和下一个结点的地址值

  • 结点的存储位置（地址）

  • 结点的数据：结点的真实数据值+下一个数据的地址值

    1
    2
    3
    下面数字是下一个结点的地址 字母是真实数据 ^是空地址

    head 11 -----> A 37 -----> C 96 ------> D ^

  • 链表中元素是游离的，查询慢，无论查询哪个数据都要从头开始找，但首尾操作快

  • 链表增删快

    1
    只需要修改指定位置的地址值

  • 单向链表

    1
    值 下一个结点地址 ------> 值 下一个结点地址 ------> 值 下一个结点地址

  • 双向链表：提高了查询的效率

    1
    ------> ^ 值 下一个结点地址 ------> 前一个结点地址 值 下一个结点地址 ------> 前一个结点地址 值 下一个结点地址 ------> 前一个结点地址 值 下一个结点地址 ------>

5.二叉树

存入数据是没有规则的

  • 父节点
  • 右子节点
  • 左子节点
  • 度：每一个节点的子节点数量称之为度
  • 节点: 在树结构中,每一个元素称之为节点
  • 树高：树的总层数
  • 根节点：最顶层的节点
  • 根节点的左子树
  • 根节点的右子树

6.二叉查找树

==二叉查找树的特点==

  • 二叉查找树,又称二叉排序树或者二叉搜索树
  • 每一个节点上最多有两个子节点
  • 左子树上所有节点的值都小于根节点的值
  • 右子树上所有节点的值都大于根节点的值

==二叉查找树结构图==

02_二叉查找树结构图

==二叉查找树添加节点规则==

  • 小的存左边
  • 大的存右边
  • 一样的不存

04_二叉查找树添加节点规则

==查找规则==

查找5在7的左子树在4的右子树

==遍历规则==

前中后都看当前的Node获取顺序

  • 前序遍历

    1
    从根节点开始，然后按照当前节点，左子节点，右子节点的顺序遍历

  • 中序遍历

    1
    从最左边的子节点开始，然后按照左子节点，当前节点，右子节点的顺序遍历

  • 后序遍历

    1
    从最左边的子节点开始，然后按照左子节点，右子节点，当前节点的顺序遍历

  • 层序遍历

    1
    一层一层的去遍历，从左往右

==二叉查找树的弊端==

高低腿 即 左右长度差距太大 比如 左子树 只有一个数据 右子树 100条数据

7.平衡二叉树

计院研究生考题

规则：任意节点左右子树高度差不超过1

机制：旋转机制

==旋转机制==

  • 规则1：左旋
  • 规则2：右旋
  • 触发时机：当添加一个节点之后，该树不再是一颗平衡二叉树

==左旋==

  • 确认支点：从添加的节点开始，不断往父节点找不平衡的节点

  • 步骤：

    1. 例一

      1
      2
      3
      1. 以不平衡的点作为支点
      2. 把支点左旋降级，变成左子节点
      3. 晋升原来的右子节点
      左旋01 左旋02

    2. 例二

      image-20240412102716236 image-20240412103008152

==右旋==

在右侧添加节点的时候破坏了平衡规则

就是将根节点的左侧往右拉,左子节点变成了新的父节点,并把多余的右子节点出让,给已经降级根节点当左子节点

  1. 例一

    image-20240412103458576 image-20240412103752061

  2. 例二

    image-20240412103930055

    image-20240412104038165

==平衡二叉树旋转的四种情况==

  • 左左

    • 左左: 当根节点左子树的左子树有节点插入,导致二叉树不平衡

    • 如何旋转: 一次整体右旋

      08_平衡二叉树左左

  • 左右

    • 左右: 当根节点左子树的右子树有节点插入,导致二叉树不平衡

    • 如何旋转: 先局部左旋，然后整体右旋

      image-20240412105129036 image-20240412105235742

      image-20240412105315428

  • 右右

    • 右右: 当根节点右子树的右子树有节点插入,导致二叉树不平衡

    • 如何旋转: 一次整体左旋

      10_平衡二叉树右右

  • 右左

    • 右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡

    • 如何旋转: 先局部右旋，然后整体左旋

      image-20240412105925350

image-20240412110004652

image-20240412110030777

8.红黑树

增删改查性能都很好

==起源==

  • 红黑树是一种自平衡的二叉查找树
  • 平衡二叉B树
  • 红黑树的每一个节点上都有存储位表示节点的颜色
  • 每一个节点可以是红或者黑；红黑树不是高度平衡的，它的平衡是通过“红黑规则”进行实现的

==红黑规则==

  1. 每一个节点或是红色的,或者是黑色的

  2. 根节点必须是黑色

  3. 如果一个节点没有子节点或者父节点,则该节点相应的指针属性值为Nil,这些Nil视为叶节点,每个叶节点(Nil)是黑色的

  4. 如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连 的情况)

  5. 对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点

    1
    2
    3
    4
    5
    后代：该节点下面所有的节点
    后代叶节点：所有的Nil   （读音-> 泥欧）
    简单路径：顺着大道走不返回走

    比如从17开始往后代子节点的简单路径上每个路径都有两个黑

    12_红黑树结构图

==添加规则==

默认颜色：添加节点默认是红色（效率高）

13_红黑树添加节点颜色

红黑树添加节点后如何保持红黑规则

  • 根节点位置
    • 直接变为黑色
  • 非根节点位置
    • 父节点为黑色
      • 不需要任何操作,默认红色即可
    • 父节点为红色
      • 叔叔节点为红色
        1. 将"父节点"设为黑色,将"叔叔节点"设为黑色
        2. 将"祖父节点"设为红色
        3. 如果"祖父节点"为根节点,则将根节点再次变成黑色
        4. 如果"祖父节点"为非根节点,则将祖父设置为当前节点再进行判断
      • 叔叔节点为黑色当前节点是父的左孩子
        1. 将"父节点"设为黑色
        2. 将"祖父节点"设为红色
        3. 以"祖父节点"为支点进行右旋转 （旋转的时候不需要考虑叶子节点）
      • 叔叔节点为黑丝当前节点是父节点的右孩子
        1. 把父作为当前节点进行左旋
        2. 再进行判断

image-20240412154737779

image-20240412154915630

9.哈希表

  • JDK8之前: 数组+链表
  • JDK8开始: 数组+链表+红黑树
1
2
就按照我自己理解为什么Java中Hash表为什么没有重复的数据：
··如果Hash中存入的是自定义对象必须重写hashCode、equals方法，不计算地址值，而计算属性值

==哈希值==

对象的整数表现形式

img

哈希值（Hash Value），也称为散列值或哈希码（Hash Code），是一个数据对象的唯一标识符，它是由哈希函数通过对数据对象进行计算而得到的。哈希值通常是一个固定大小的整数，这个整数在哈希表中用于确定数据对象的存储位置。

哈希函数的设计目标是将输入数据（通常是字符串或对象）转换为一个散列值，这个值应该具有以下特性：

  1. 唯一性：理想情况下，每个不同的输入数据应该产生一个不同的哈希值。然而，在实际应用中，可能会出现不同的输入数据产生相同哈希值的情况，这称为“哈希冲突”。
  2. 快速计算：哈希函数应该能够快速地计算出输入数据的哈希值。
  3. 分布均匀：哈希函数应该能够将输入数据均匀地映射到哈希值的整个范围内，以减少哈希冲突的可能性。

哈希值在计算机科学中有多种用途，包括：

  • 数据检索：在哈希表中，哈希值用于快速定位数据对象。
  • 数据完整性验证：哈希值可以用来验证数据是否在传输或存储过程中被篡改。
  • 加密：在加密算法中，哈希函数用于生成消息摘要或密钥。

需要注意的是，哈希值并不总是全局唯一的。在某些情况下，不同的输入数据可能会产生相同的哈希值，这种现象称为**“哈希碰撞”**。为了处理这种碰撞，哈希表通常采用某种冲突解决策略，如链地址法（Chaining）或开放寻址法（Open Addressing）。

在Java中，几乎所有的对象都有一个hashCode方法，该方法返回对象的哈希码值。这个值是由对象的内部状态（如字段值）计算得到的，并且通常与对象的内存地址无关。hashCode方法在Object类中被定义，并在需要时被其他类重写。正确实现hashCode方法对于确保散列数据结构（如HashSet、HashMap等）的正确行为至关重要。

==哈希表的数据结构==

哈希表（Hash Table）是一种高效的数据结构，它通过使用哈希函数将键（Key）映射到表中的位置来存储数据。这种结构也被称为散列表，它能够提供快速的数据访问速度。以下是哈希表的主要组成部分和工作原理：

==主要组成部分==

  1. 哈希函数（Hash Function）：
    哈希函数是一个将输入（通常是字符串）转换为表中索引的函数。理想情况下，哈希函数应该将键均匀地分布在整个表中，以避免聚集（多个键映射到同一位置）。

  2. 数组（Array）：
    哈希表通常使用一个数组来存储数据。数组的每个位置称为一个“桶”（Bucket），它可以存储一个或多个键值对。

  3. 键值对（Key-Value Pairs）：
    数据以键值对的形式存储在哈希表中，其中键是唯一的标识符，值是与键相关联的数据。

==工作原理==

  1. 插入（Insertion）：
    当你向哈希表中插入一个键值对时，哈希函数计算键的哈希值，然后使用这个哈希值来确定应该将键值对存储在数组的哪个位置（桶）。

  2. 查找（Lookup）：
    查找操作与插入类似。首先使用哈希函数计算键的哈希值，然后在对应的桶中查找键值对。如果桶中有多个键值对，就需要遍历这些键值对来找到匹配的键。

  3. 删除（Deletion）：
    删除操作首先需要找到要删除的键值对，这通常通过查找操作完成。一旦找到，就可以直接从桶中删除该键值对。

==处理冲突==

在哈希表中，可能会出现两个或多个不同的键映射到同一桶的情况，这称为“哈希冲突”（Hash Collision）。有几种常见的方法来处理哈希冲突：

  1. 链地址法（Chaining）：
    在每个桶中使用链表来存储多个键值对。当发生冲突时，键值对被添加到链表的末尾。

  2. 开放寻址法（Open Addressing）：
    当插入时遇到冲突，开放寻址法会寻找表中的另一个空桶来存储键值对。这可能涉及到线性探测、二次探测或双重哈希等策略。

  3. 再哈希（Rehashing）：
    当哈希表变得过于拥挤时，可以通过创建一个更大的新哈希表并将所有现有键值对重新插入来减少冲突的机会。

==优点==

  • 快速访问：哈希表提供了快速的数据访问，理想情况下，插入和查找操作的时间复杂度为 O(1)。

==缺点==

  • 哈希冲突：需要有效的策略来处理哈希冲突。
  • 空间浪费：为了减少冲突并保持高效的操作，哈希表通常需要额外的空间来存储空桶或解决冲突的数据结构。
  • 键的分布：哈希表的性能依赖于键的分布和哈希函数的质量。

==Java为String提供的hashCode方法会导致哈希碰撞==

在Java中，hashCode方法是用来计算对象哈希码的。字符串的哈希码是基于字符串的字符序列通过某种算法计算得到的。Java为String类提供了hashCode方法的默认实现，该实现遵循以下规则：

  1. 字符串""（空字符串）的哈希码是0。
  2. 对于非空字符串s，其哈希码计算公式为：
    1
    s[0] * 31^(n - 1) + s[1] * 31^(n - 2) + ... + s[n - 1] * 31
    其中，s[i]是字符串中第i个字符的整数ASCII值，n是字符串的长度，^表示乘方。

现在，让我们应用这个规则来计算给定字符串的哈希码：

  • 对于字符串"abc"，其哈希码计算如下：

    1
    2
    3
    4
    'a' * 31^2 + 'b' * 31^1 + 'c' * 31^0
    97 * 961 + 98 * 31 + 99 * 1
    = 93,059 + 3,098 + 99
    = 96,256

    因此，"abc".hashCode()的结果是96,256。

  • 对于字符串"acD"，其哈希码计算如下：

    1
    2
    3
    4
    'a' * 31^1 + 'c' * 31^0
    97 * 31 + 99 * 1
    = 2,997 + 99
    = 3,096

    但是，这里有一个错误。实际上，字符串"acD"的哈希码计算应该是：

    1
    2
    3
    4
    'a' * 31^2 + 'c' * 31^1 + 'D' * 31^0
    97 * 961 + 99 * 31 + 68 * 1
    = 93,059 + 3,089 + 68
    = 96,216

    因此，"acD".hashCode()的结果是96,216。

从上面的计算可以看出，"abc"和"acD"的哈希码是不同的。如果你在Java程序中运行这两个hashCode调用，你会得到两个不同的整数值。

如果你发现两个不同的字符串有相同的哈希码，那只是偶然的哈希冲突。由于哈希码是一个有限的整数，而字符串的可能组合是无限的，所以不同的输入可能会产生相同的哈希码。这是哈希函数的一个固有特性，并且在设计哈希表时需要考虑这种可能性。在Java中，字符串的哈希码通常是唯一的，但不是绝对的，因此哈希表可能会遇到冲突。