检索算法和技术的本质回顾

目录

一、数据结构和存储特点对检索效率的重大影响总结

二、数组和链表的线性结构检索

（一）基本分析

（二）使用二分查找提升数组检索效率

（三）灵活改造链表提升检索效率

问题背景

解决方案

歌曲块链表的设计

基本设计

检索操作

具体代码实现验证

三、树和跳表非线性结构检索

（一）基本分析

树（通常是平衡二叉搜索树）

跳表

总结

（二）树结构如何进行二分查找

理论基础

代码验证

（三）二叉检索树的检索空间平衡方案

平衡二叉搜索树（AVL树）

红黑树

伸展树

平衡方案说明

（四）跳表如何进行二分查找

基本思想回顾

重新回忆下删除和插入操作

简单代码展示

四、哈希检索

（一）基本的常识分析

基本原理

特点和优点

注意事项和限制

（二）扩展知识分析

Java 8后的HashMap优化：链表转换为红黑树+红黑树退化为链表

链表转换为红黑树

红黑树退化为链表

（三）哈希表缺点分析

（四）哈希函数的应用举例

五、状态检索

（一）基本说明

常见应用场景和简单实现

（二）位图（Bitmap）和布隆过滤器（Bloom Filter）

位图（Bitmap）

布隆过滤器（Bloom Filter）

选择位图或布隆过滤器

（三）扩展：布隆过滤器误判率举例分析

六、倒排索引

（一）正排索引理解

（二）倒排索引理解

（三）如何创建倒排索索引举例

（四）查询倒排索索引举例分析

---

检索的核心思路，其实就是通过合理组织数据，尽可能地快速减少查询范围。也就是说到更多的检索算法和技术，其实它们的本质都是通过灵活应用各种数据结构的特点来组织数据，从而达到快速减少查询范围的目的。

以下主要内容主要针对其涉及的基本技术进行回顾总结。

一、数据结构和存储特点对检索效率的重大影响总结

检索是一种从存储数据的地方高效地获取所需信息的技术。检索效率与数据存储方式之间存在紧密联系，而研究不同数据结构的存储特点对检索效率的影响非常重要。

1. 数据结构选择：不同的数据结构适用于不同的数据存储和检索需求。例如，哈希表适用于快速查找，但不适合范围查询。树结构（如二叉树或B树）适用于范围查询，但可能不如哈希表在单一查找上效率高。因此，了解不同数据结构的特点以及何时使用它们是至关重要的。

2. 索引结构：在数据库和搜索引擎中，索引结构用于加速数据的检索。不同的索引结构，如倒排索引、B树索引、散列索引等，适用于不同类型的查询和数据。选择正确的索引结构可以显著提高检索效率。

3. 数据编码和压缩：数据在存储时可以采用不同的编码和压缩技术。这些技术可以减少存储空间，并在一定程度上影响检索速度。了解如何选择和应用数据编码和压缩技术对于优化存储和检索效率至关重要。

4. 分布式存储：在大规模系统中，数据通常分布在多个节点上。了解分布式存储的原理以及如何有效地检索分布式数据对于构建高性能系统非常重要。

总之，数据结构和存储特点对检索效率产生重大影响，因此，深入了解这些概念和技术对于设计和优化存储和检索系统至关重要。在不同的应用场景中，选择合适的数据结构和存储方式可以显著提高系统的性能和效率。

二、数组和链表的线性结构检索

（一）基本分析

数组和链表是两种不同的线性数据结构，它们的检索效率在某些方面有所不同，取决于具体的操作和使用情境。

数组的检索效率：

• 随机访问效率高：数组在内存中是连续存储的，这使得随机访问数组中的元素非常高效。只需知道索引即可直接访问该位置的元素，时间复杂度为O(1)。
• 插入和删除效率低：如果要在数组中插入或删除元素，通常需要将后续元素移动以保持连续性。这样的操作平均时间复杂度为O(n)，其中n是数组中的元素数量。

链表的检索效率：

• 随机访问效率低：链表的元素不是连续存储的，因此要访问链表中的某个元素，必须从头节点或其他已知位置开始遍历链表。因此，随机访问的平均时间复杂度为O(n)，其中n是链表的长度。
• 插入和删除效率高：链表在插入和删除元素时通常非常高效。只需修改节点的指针，而不需要移动元素。这些操作的平均时间复杂度为O(1)，前提是可以直接访问要插入或删除的节点。

也就是说，如果需要频繁进行随机访问操作，数组通常更有效率。但如果需要频繁进行插入和删除操作，并且对访问效率要求不那么高，链表可能更合适。

在实际应用中，通常会根据具体的操作需求来选择适当的数据结构，或者在需要时考虑使用更高级的数据结构来平衡这些操作的性能。例如，平衡二叉搜索树可以提供较好的插入、删除和查找效率。

（二）使用二分查找提升数组检索效率

二分查找是一种高效的搜索算法，特别适用于已排序的数组。它的基本思想是不断将待查找区间缩小为原来的一半，直到找到目标值或确定目标值不存在为止。下面是一般的二分查找的代码实现及说明：

package org.zyf.javabasic.test.search;

/**
 * @program: zyfboot-javabasic
 * @description: 一般的二分查找的代码实现
 * @author: zhangyanfeng
 * @create: 2024-04-14 11:52
 **/
public class BinarySearchTest {
    // 二分查找函数
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        // 当左边界小于等于右边界时继续查找
        while (left <= right) {
            // 计算中间位置
            int mid = left + (right - left) / 2;

            // 如果目标值等于中间值，则返回中间索引
            if (arr[mid] == target) {
                return mid;
            }

            // 如果目标值小于中间值，则在左半边继续查找
            else if (arr[mid] > target) {
                right = mid - 1;
            }

            // 如果目标值大于中间值，则在右半边继续查找
            else {
                left = mid + 1;
            }
        }

        // 若未找到目标值，则返回 -1 表示不存在
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;
        int index = binarySearch(arr, target);
        if (index != -1) {
            System.out.println("目标值 " + target + " 在数组中的索引为：" + index);
        } else {
            System.out.println("目标值 " + target + " 不存在于数组中。");
        }
    }
}

这个 binarySearch 函数接受一个已排序的整数数组 arr 和一个目标值 target，返回目标值在数组中的索引，如果目标值不存在则返回 -1。

该算法的时间复杂度为 O(log n)，其中 n 是数组的长度。相比于简单的线性搜索，二分查找在大型有序数组中的查找效率更高。

（三）灵活改造链表提升检索效率

学习链表是学习如何组织“非连续存储空间”的数据结构。

用简单的改造例子展示如何根据实际需求来设计链表的变种，以提升检索效率。

问题背景

假设您需要设计一个音乐播放列表（或歌曲库），用户可以随机访问歌曲，但您希望尽量减少内存占用。

解决方案

• 传统链表：传统的单向链表需要为每首歌曲分配一个节点，这会浪费大量内存，因为每个节点还需要存储指向下一个节点的指针。
• 改进方案：为了减少内存占用并提高检索效率，可以设计一个变种链表，其中每个节点不仅存储歌曲信息，还存储一定数量的歌曲。这种变种链表可以称为“歌曲块链表”（Song Block Linked List）。

歌曲块链表的设计

基本设计

• 每个节点包含一个小数组（或列表），其中存储一定数量的歌曲。数组的大小可以根据实际需求调整，以权衡内存占用和检索效率。
• 每个节点还包含指向下一个节点的指针，以便可以遍历整个歌曲块链表。

检索操作

• 当用户要随机访问某首歌曲时，首先确定它在哪个节点的小数组中。可以使用二分查找等方法快速定位。
• 一旦找到所在的节点，就可以在节点内的小数组中进行线性搜索，以查找目标歌曲。

这种歌曲块链表的设计允许充分利用链表的非连续存储空间特点，减少了内存占用，同时仍然可以实现较快的歌曲检索操作。这个例子展示了如何根据实际需求，结合链表的核心思想，设计出适用的数据结构，以提高检索效率和节省内存。

具体代码实现验证

我们简单写一下代码验证一下吧，首先定义歌曲块节点如下：

package org.zyf.javabasic.test.search;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: zyfboot-javabasic
 * @description: 歌曲块节点
 * @author: zhangyanfeng
 * @create: 2024-04-14 11:56
 **/
public class SongBlockNode {
    private List<String> songs;  // 存储歌曲的小数组
    private SongBlockNode next;  // 指向下一个节点的指针

    // 构造函数
    public SongBlockNode() {
        this.songs = new ArrayList<>();
        this.next = null;
    }

    // 添加歌曲到当前节点的小数组中
    public void addSong(String song) {
        songs.add(song);
    }

    // 获取当前节点的小数组
    public List<String> getSongs() {
        return songs;
    }

    // 获取下一个节点
    public SongBlockNode getNext() {
        return next;
    }

    // 设置下一个节点
    public void setNext(SongBlockNode next) {
        this.next = next;
    }
}

然后实现对应的歌曲块链表如下：

package org.zyf.javabasic.test.search;

import java.util.List;

/**
 * @program: zyfboot-javabasic
 * @description: 歌曲块链表
 * @author: zhangyanfeng
 * @create: 2024-04-14 11:56
 **/
public class SongBlockLinkedList {
    private SongBlockNode head;  // 头节点

    // 构造函数
    public SongBlockLinkedList() {
        head = null;
    }

    // 在链表尾部添加一个节点
    public void addNode(SongBlockNode newNode) {
        if (head == null) {
            head = newNode;
        } else {
            SongBlockNode current = head;
            while (current.getNext() != null) {
                current = current.getNext();
            }
            current.setNext(newNode);
        }
    }

    // 二分查找指定歌曲，返回所在节点的索引
    public int binarySearchSong(String song) {
        SongBlockNode current = head;
        int index = 0;

        // 遍历链表
        while (current != null) {
            List<String> songs = current.getSongs();
            if (songs.contains(song)) {
                return index + songs.indexOf(song);
            }
            current = current.getNext();
            index += songs.size();
        }

        // 歌曲不存在于链表中
        return -1;
    }
}

快速验证代码测试代码如下：

package org.zyf.javabasic.test.search;

/**
 * @program: zyfboot-javabasic
 * @description: 简单验证
 * @author: zhangyanfeng
 * @create: 2024-04-14 11:57
 **/
public class SongBlockListTest {
    public static void main(String[] args) {
        // 创建歌曲块链表
        SongBlockLinkedList songList = new SongBlockLinkedList();

        // 添加节点
        SongBlockNode node1 = new SongBlockNode();
        node1.addSong("Song1");
        node1.addSong("Song2");
        songList.addNode(node1);

        SongBlockNode node2 = new SongBlockNode();
        node2.addSong("Song3");
        node2.addSong("Song4");
        songList.addNode(node2);

        // 查找歌曲
        String targetSong = "Song3";
        int index = songList.binarySearchSong(targetSong);
        if (index != -1) {
            System.out.println("歌曲 " + targetSong + " 的索引为: " + index);
        } else {
            System.out.println("歌曲 " + targetSong + " 不存在于歌曲库中。");
        }
    }
}

运行验证成功，基本输出如下，符合预期。

三、树和跳表非线性结构检索

（一）基本分析

树和跳表都是非线性数据结构，它们在检索方面具有一定的优势，但在不同情况下可能更适用。以下是对树和跳表在非线性结构检索中的分析：

树（通常是平衡二叉搜索树）

优点	适用场景
高效的检索：平衡二叉搜索树（如 AVL 树或红黑树）在数据频繁变化时能够保持树的平衡，因此具有高效的检索性能。平均检索时间复杂度为 O(log n)。	适用于需要频繁的插入、删除和检索操作的情况，例如数据库索引和有序集合。
插入和删除：平衡树对插入和删除操作也有较高的效率。	对数据的要求较高，需要保持数据的有序性时，平衡树是一个好选择。

跳表

优点	适用场景
高效的检索：跳表是一种数据结构，它通过多层索引实现高效的跳跃式检索。平均检索时间复杂度为 O(log n)，类似于平衡树。	适用于需要高效检索操作，但对插入和删除操作的性能要求相对较低的场景。
简单实现：相对于平衡树，跳表的实现相对简单，并且不需要自动平衡。	可用于实现有序集合、高性能的跳跃表索引等。

总结

• 树和跳表都是非线性数据结构，用于高效检索。它们在平均检索时间复杂度上具有相似的性能。
• 树适用于需要频繁插入、删除和检索的场景，以及对数据的有序性要求较高的情况。
• 跳表适用于需要高效检索操作，但对插入和删除操作的性能要求相对较低的情况。跳表的实现较为简单。

在实际应用中，选择树还是跳表取决于具体的需求和性能要求。如果插入和删除操作频繁，而且需要保持数据有序性，那么平衡树可能更适合。如果主要关注高效的检索操作，并且可以容忍较低的插入和删除性能，那么跳表可能是更好的选择。

（二）树结构如何进行二分查找

理论基础

树结构（特别是二叉树）是通过二分查找的方式来进行检索操作的。二分查找是一种高效的查找算法，它适用于有序数据集合，例如有序的树结构。

二叉树数据结构中每个节点最多有两个子节点，通常分为左子树和右子树。树中的节点按照某种特定的顺序排列，例如，左子树的节点值小于父节点，右子树的节点值大于父节点（或相反，具体取决于树的性质）。

二分查找：

• 二分查找是一种分而治之的策略，它从树的根节点开始，逐步地将搜索范围减半，直到找到目标元素或确定它不存在。
• 从根节点开始，比较目标元素与当前节点的值。
• 如果目标元素小于当前节点的值，继续在左子树中查找，因为左子树的值都小于当前节点。
• 如果目标元素大于当前节点的值，继续在右子树中查找，因为右子树的值都大于当前节点。
• 重复这个过程，直到找到目标元素或达到叶子节点，如果仍然没有找到，就说明目标元素不存在于树中。

时间复杂度：

• 二分查找在平衡二叉树（例如AVL树）中的时间复杂度为O(log n)，其中n是树中节点的数量。这是一种非常高效的检索算法。

总之，树结构通过利用二分查找的方式，将数据按有序的方式组织，以便高效地进行检索操作。在有序的二叉树中，通过比较目标值和当前节点的值，可以确定搜索方向，并且在每一步中将搜索范围减半，从而实现了快速的查找。这使得二叉树成为一种非常有用的数据结构，用于实现高效的查找和排序操作。

代码验证

package org.zyf.javabasic.test.search;

import org.zyf.javabasic.letcode.tree.base.TreeNode;

/**
 * @program: zyfboot-javabasic
 * @description: 用于表示二叉搜索树（BST）及其基本操作，包括插入和查找
 * @author: zhangyanfeng
 * @create: 2024-04-14 12:16
 **/
public class BinarySearchTree {
    TreeNode root;

    // 构造函数
    public BinarySearchTree() {
        root = null;
    }

    // 插入节点
    public void insert(int val) {
        root = insertNode(root, val);
    }

    // 辅助函数：插入节点
    private TreeNode insertNode(TreeNode node, int val) {
        if (node == null) {
            return new TreeNode(val);
        }

        if (val < node.val) {
            node.left = insertNode(node.left, val);
        } else if (val > node.val) {
            node.right = insertNode(node.right, val);
        }

        return node;
    }

    // 查找节点
    public boolean search(int val) {
        return searchNode(root, val);
    }

    // 辅助函数：查找节点
    private boolean searchNode(TreeNode node, int val) {
        if (node == null) {
            return false;
        }

        if (val == node.val) {
            return true;
        } else if (val < node.val) {
            return searchNode(node.left, val);
        } else {
            return searchNode(node.right, val);
        }
    }

    public static void main(String[] args) {
        // 创建一个二叉搜索树
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(10);
        bst.insert(5);
        bst.insert(15);
        bst.insert(3);
        bst.insert(7);
        bst.insert(12);
        bst.insert(20);

        // 查找节点
        int target = 7;
        if (bst.search(target)) {
            System.out.println("节点 " + target + " 存在于二叉搜索树中。");
        } else {
            System.out.println("节点 " + target + " 不存在于二叉搜索树中。");
        }
    }
}

（三）二叉检索树的检索空间平衡方案

二叉搜索树（Binary Search Tree，BST）的检索性能在很大程度上取决于树的平衡性。如果树的平衡性较好，检索操作的平均时间复杂度将保持在O(log n)级别。然而，如果BST不平衡，最坏情况下，检索操作可能需要O(n)的时间，这会显著降低其性能。

为了保持BST的平衡性，可以采用以下平衡方案：

平衡二叉搜索树（AVL树）

• AVL树是一种自平衡的BST，它通过在每次插入或删除节点后执行旋转操作来保持平衡。
• 每个节点都有一个平衡因子，表示其左子树的高度和右子树的高度之差。在插入或删除操作后，平衡因子会被更新，并且根据平衡因子的值，执行单旋转或双旋转来恢复平衡。
• AVL树的平均检索时间复杂度为O(log n)，适用于频繁插入和删除操作的场景。

现在代码练习一下吧，基本实现如下：

package org.zyf.javabasic.test.search;

/**
 * @program: zyfboot-javabasic
 * @description: 表示 AVL 树（平衡二叉搜索树）及其基本操作，包括插入、删除和查找
 * @author: zhangyanfeng
 * @create: 2024-04-14 12:22
 **/
public class AVLTree {
    TreeNode root;

    // 获取节点高度
    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return node.height;
    }

    // 更新节点高度
    private void updateHeight(TreeNode node) {
        node.height = 1 + Math.max(height(node.left), height(node.right));
    }

    // 获取平衡因子
    private int getBalance(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return height(node.left) - height(node.right);
    }

    // 右旋转
    private TreeNode rightRotate(TreeNode y) {
        TreeNode x = y.left;
        TreeNode T2 = x.right;

        // 执行旋转
        x.right = y;
        y.left = T2;

        // 更新节点高度
        updateHeight(y);
        updateHeight(x);

        return x;
    }

    // 左旋转
    private TreeNode leftRotate(TreeNode x) {
        TreeNode y = x.right;
        TreeNode T2 = y.left;

        // 执行旋转
        y.left = x;
        x.right = T2;

        // 更新节点高度
        updateHeight(x);
        updateHeight(y);

        return y;
    }

    // 插入节点
    public TreeNode insert(TreeNode node, int val) {
        if (node == null) {
            return new TreeNode(val);
        }

        if (val < node.val) {
            node.left = insert(node.left, val);
        } else if (val > node.val) {
            node.right = insert(node.right, val);
        } else {
            return node; // 重复值不插入
        }

        // 更新节点高度
        updateHeight(node);

        // 获取平衡因子
        int balance = getBalance(node);

        // 左旋转
        if (balance > 1 && val < node.left.val) {
            return rightRotate(node);
        }

        // 右旋转
        if (balance < -1 && val > node.right.val) {
            return leftRotate(node);
        }

        // 左右旋转
        if (balance > 1 && val > node.left.val) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // 右左旋转
        if (balance < -1 && val < node.right.val) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    // 中序遍历打印树
    public void inOrderTraversal(TreeNode node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.print(node.val + " ");
            inOrderTraversal(node.right);
        }
    }

    // 查找节点
    public boolean search(TreeNode node, int val) {
        if (node == null) {
            return false;
        }

        if (val == node.val) {
            return true;
        } else if (val < node.val) {
            return search(node.left, val);
        } else {
            return search(node.right, val);
        }
    }

    // AVL 树节点
    class TreeNode {
        int val;
        int height;
        TreeNode left;
        TreeNode right;

        // 构造函数
        public TreeNode(int val) {
            this.val = val;
            this.height = 1; // 初始高度为 1
            left = null;
            right = null;
        }
    }

    public static void main(String[] args) {
        AVLTree avlTree = new AVLTree();

        // 插入节点
        avlTree.root = avlTree.insert(avlTree.root, 10);
        avlTree.root = avlTree.insert(avlTree.root, 20);
        avlTree.root = avlTree.insert(avlTree.root, 30);
        avlTree.root = avlTree.insert(avlTree.root, 40);
        avlTree.root = avlTree.insert(avlTree.root, 50);
        avlTree.root = avlTree.insert(avlTree.root, 25);

        // 中序遍历打印树
        System.out.println("AVL 树中序遍历结果：");
        avlTree.inOrderTraversal(avlTree.root);

        // 查找节点
        int target = 30;
        if (avlTree.search(avlTree.root, target)) {
            System.out.println("\n节点 " + target + " 存在于 AVL 树中。");
        } else {
            System.out.println("\n节点 " + target + " 不存在于 AVL 树中。");
        }
    }
}

红黑树

• 红黑树是另一种自平衡的BST，它通过着色节点并遵循一组规则来保持平衡。
• 红黑树的平衡性通过节点的颜色和特定的规则来维护。这些规则包括节点的颜色不能相邻，以及从任何节点到其每个叶子的路径包含相同数量的黑色节点。
• 红黑树的平均检索时间复杂度为O(log n)，并且相对于AVL树，它的插入和删除操作可能稍微高效一些。

同样的，现在代码练习一下吧，基本实现如下（这也是一般我们面试时候常考的加分项）：

package org.zyf.javabasic.test.search;

/**
 * @program: zyfboot-javabasic
 * @description: 用于表示红黑树及其基本操作，包括插入、删除和查找
 * @author: zhangyanfeng
 * @create: 2024-04-14 12:28
 **/
public class RedBlackTree {

    private TreeNode root;
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    // 获取节点的颜色
    private boolean color(TreeNode node) {
        return node == null ? BLACK : node.isRed;
    }

    // 左旋转
    private TreeNode leftRotate(TreeNode x) {
        TreeNode y = x.right;
        x.right = y.left;
        if (y.left != null) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
        return y;
    }

    // 右旋转
    private TreeNode rightRotate(TreeNode y) {
        TreeNode x = y.left;
        y.left = x.right;
        if (x.right != null) {
            x.right.parent = y;
        }
        x.parent = y.parent;
        if (y.parent == null) {
            root = x;
        } else if (y == y.parent.right) {
            y.parent.right = x;
        } else {
            y.parent.left = x;
        }
        x.right = y;
        y.parent = x;
        return x;
    }

    // 插入节点
    public void insert(int val) {
        TreeNode newNode = new TreeNode(val);
        root = insertNode(root, newNode);
        newNode.isRed = RED; // 新插入的节点为红色
        fixInsertViolation(newNode);
    }

    // 辅助函数：插入节点
    private TreeNode insertNode(TreeNode root, TreeNode newNode) {
        if (root == null) {
            return newNode;
        }

        if (newNode.val < root.val) {
            root.left = insertNode(root.left, newNode);
            root.left.parent = root;
        } else if (newNode.val > root.val) {
            root.right = insertNode(root.right, newNode);
            root.right.parent = root;
        }

        return root;
    }

    // 插入修复违反红黑树性质的情况
    private void fixInsertViolation(TreeNode node) {
        while (node != root && color(node.parent) == RED) {
            if (node.parent == node.parent.parent.left) {
                TreeNode uncle = node.parent.parent.right;
                if (color(uncle) == RED) {
                    // Case 1: 叔叔节点是红色
                    node.parent.isRed = BLACK;
                    uncle.isRed = BLACK;
                    node.parent.parent.isRed = RED;
                    node = node.parent.parent;
                } else {
                    if (node == node.parent.right) {
                        // Case 2: 叔叔节点是黑色，且当前节点是右子节点
                        node = node.parent;
                        leftRotate(node);
                    }
                    // Case 3: 叔叔节点是黑色，且当前节点是左子节点
                    node.parent.isRed = BLACK;
                    node.parent.parent.isRed = RED;
                    rightRotate(node.parent.parent);
                }
            } else {
                TreeNode uncle = node.parent.parent.left;
                if (color(uncle) == RED) {
                    // Case 1: 叔叔节点是红色
                    node.parent.isRed = BLACK;
                    uncle.isRed = BLACK;
                    node.parent.parent.isRed = RED;
                    node = node.parent.parent;
                } else {
                    if (node == node.parent.left) {
                        // Case 2: 叔叔节点是黑色，且当前节点是左子节点
                        node = node.parent;
                        rightRotate(node);
                    }
                    // Case 3: 叔叔节点是黑色，且当前节点是右子节点
                    node.parent.isRed = BLACK;
                    node.parent.parent.isRed = RED;
                    leftRotate(node.parent.parent);
                }
            }
        }
        root.isRed = BLACK;
    }

    // 中序遍历打印树
    public void inOrderTraversal(TreeNode node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.print(node.val + " ");
            inOrderTraversal(node.right);
        }
    }

    // 查找节点
    public boolean search(int val) {
        return searchNode(root, val);
    }

    // 辅助函数：查找节点
    private boolean searchNode(TreeNode node, int val) {
        if (node == null) {
            return false;
        }

        if (val == node.val) {
            return true;
        } else if (val < node.val) {
            return searchNode(node.left, val);
        } else {
            return searchNode(node.right, val);
        }
    }


    // 红黑树节点
    class TreeNode {
        int val;
        boolean isRed; // true 表示红色，false 表示黑色
        TreeNode left;
        TreeNode right;
        TreeNode parent;

        // 构造函数
        public TreeNode(int val) {
            this.val = val;
            this.isRed = true; // 新插入的节点默认为红色
            left = null;
            right = null;
            parent = null;
        }
    }

    public static void main(String[] args) {
        RedBlackTree rbTree = new RedBlackTree();

        // 插入节点
        rbTree.insert(10);
        rbTree.insert(20);
        rbTree.insert(30);
        rbTree.insert(40);
        rbTree.insert(50);
        rbTree.insert(25);

        // 中序遍历打印树
        System.out.println("红黑树中序遍历结果：");
        rbTree.inOrderTraversal(rbTree.root);

        // 查找节点
        int target = 30;
        if (rbTree.search(target)) {
            System.out.println("\n节点 " + target + " 存在于红黑树中。");
        } else {
            System.out.println("\n节点 " + target + " 不存在于红黑树中。");
        }
    }
}

伸展树

• 伸展树是一种自适应的BST，它在每次检索操作后，通过旋转操作将最近访问的节点移到根节点的位置。这有助于提高最近访问的节点的检索速度。
• 伸展树的平均检索时间复杂度为O(log n)，但它可能在插入和删除操作上具有一些性能开销。

同样的，现在代码练习一下吧，基本实现如下：

package org.zyf.javabasic.test.search;

import org.zyf.javabasic.letcode.tree.base.TreeNode;

/**
 * @program: zyfboot-javabasic
 * @description: 用于表示伸展树（Splay Tree）及其基本操作，包括插入、删除和查找
 * @author: zhangyanfeng
 * @create: 2024-04-14 12:31
 **/
public class SplayTree {
    private TreeNode root;

    // 旋转：左旋
    private TreeNode leftRotate(TreeNode x) {
        TreeNode y = x.right;
        x.right = y.left;
        y.left = x;
        return y;
    }

    // 旋转：右旋
    private TreeNode rightRotate(TreeNode y) {
        TreeNode x = y.left;
        y.left = x.right;
        x.right = y;
        return x;
    }

    // 伸展：将节点 x 伸展到根节点
    private TreeNode splay(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }

        if (val < root.val) {
            // 待查找的值在左子树中
            if (root.left == null) {
                return root;
            }
            // Zig-Zig (left left)
            if (val < root.left.val) {
                root.left.left = splay(root.left.left, val);
                root = rightRotate(root);
            }
            // Zig-Zag (left right)
            else if (val > root.left.val) {
                root.left.right = splay(root.left.right, val);
                if (root.left.right != null) {
                    root.left = leftRotate(root.left);
                }
            }
            if (root.left != null) {
                root = rightRotate(root);
            }
            return (root.left == null) ? root : rightRotate(root);
        } else {
            // 待查找的值在右子树中
            if (root.right == null) {
                return root;
            }
            // Zag-Zag (right right)
            if (val > root.right.val) {
                root.right.right = splay(root.right.right, val);
                root = leftRotate(root);
            }
            // Zag-Zig (right left)
            else if (val < root.right.val) {
                root.right.left = splay(root.right.left, val);
                if (root.right.left != null) {
                    root.right = rightRotate(root.right);
                }
            }
            if (root.right != null) {
                root = leftRotate(root);
            }
            return (root.right == null) ? root : leftRotate(root);
        }
    }

    // 插入节点
    public TreeNode insert(int val) {
        root = insertNode(root, val);
        root = splay(root, val);
        return root;
    }

    // 辅助函数：插入节点
    private TreeNode insertNode(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (val < root.val) {
            root.left = insertNode(root.left, val);
        } else if (val > root.val) {
            root.right = insertNode(root.right, val);
        }
        return root;
    }

    // 查找节点
    public boolean search(int val) {
        root = splay(root, val);
        return root != null && root.val == val;
    }

    public static void main(String[] args) {
        SplayTree splayTree = new SplayTree();

        // 插入节点
        splayTree.insert(10);
        splayTree.insert(20);
        splayTree.insert(30);
        splayTree.insert(40);
        splayTree.insert(50);

        // 查找节点
        int target = 30;
        if (splayTree.search(target)) {
            System.out.println("节点 " + target + " 存在于伸展树中。");
        } else {
            System.out.println("节点 " + target + " 不存在于伸展树中。");
        }
    }
}

平衡方案说明

选择适当的平衡方案取决于您的具体需求和性能要求。AVL树和红黑树通常用于需要强制平衡性的场景，而伸展树则适用于需要优化最近访问的节点的检索操作的场景。不同的平衡方案可能具有不同的权衡点，因此在选择时需要考虑您的应用程序的特定需求。

（四）跳表如何进行二分查找

跳表（Skip List）是一种数据结构，它是在有序元素集合上执行高效查找、插入和删除操作的一种方式。

基本思想回顾

跳表的二分查找基于多级索引的思想：

• 跳表包含多个级别（层），每个级别都是一个有序链表，其中包含部分原始数据元素。底层链表包含所有元素，而上层链表则包含底层链表中的一部分元素。
• 每个级别的链表都是有序的，这意味着在每个级别上都可以执行二分查找。

查找操作

• 跳表的查找操作从顶层链表的头部开始，逐级向下移动。在每个级别上，它比较当前节点的值与目标值。
• 如果当前节点的值小于目标值，它会继续向右移动，直到找到一个大于等于目标值的节点。
• 如果当前节点的值大于目标值，它会向下移动到下一个级别，然后继续查找。

优势

• 跳表中的多级索引允许快速地跳过一些元素，从而将搜索范围缩小到一个较小的区域，类似于二分查找。
• 跳表的平均检索时间复杂度是O(log n)，其中n是元素的数量。这使得它在某些情况下比传统链表更高效。

总之，跳表通过多级索引的方式，将数据组织成多个有序链表，从而实现了高效的查找操作，类似于二分查找的思想。跳表的平均检索时间复杂度是O(log n)，这使得它在某些情况下是一种高效的数据结构，特别是当需要在有序元素集合上执行频繁的查找操作时。跳表还相对容易实现，并且不需要像平衡树那样复杂的平衡算法，因此它在实际应用中具有一定的优势。

重新回忆下删除和插入操作

跳表的插入和删除操作相对复杂一些，因为它们不仅需要在底层链表上执行插入和删除，还需要维护多级索引的平衡性。

插入操作

1. 首先，要插入一个新元素，需要找到插入位置。从顶层链表的头部开始，逐级向下移动，直到找到需要插入的位置。

2. 在找到插入位置后，执行插入操作。这涉及到将新元素插入到底层链表中的适当位置。

3. 接下来，需要考虑维护多级索引的平衡性。为了保持平衡，可以采取以下步骤：

   a.随机决定新元素是否要升级到较高级别的索引。这可以通过投掷硬币或其他随机方法来完成。如果决定升级，将新元素添加到上一级索引中，并重复此步骤，直到不再升级为止。b.在每个级别上，确保在插入位置的左边和右边都有足够多的元素，以便索引仍然有效。如果某个级别的链表太短，可以在该级别上进行拆分，将新元素添加到合适的位置，然后重新建立索引。

4. 完成插入操作后，跳表的结构应该仍然是有序的，并且多级索引应该保持平衡。

删除操作

1. 删除操作也需要首先找到要删除的元素所在的位置。从顶层链表的头部开始，逐级向下移动，直到找到要删除的元素。

2. 在找到要删除的位置后，执行删除操作。这涉及到从底层链表中删除元素，并且可能需要合并或删除相关的索引。

3. 同样需要维护多级索引的平衡性。为了保持平衡，可以采取以下步骤：

   在每个级别上，检查是否需要删除级别上的某些元素，以维持索引的平衡。如果某个级别的链表太短，可以将其删除或与下一个级别合并。

4. 完成删除操作后，跳表的结构应该仍然是有序的，并且多级索引应该保持平衡。

需要注意的是，插入和删除操作的实现可能会涉及到一些细节，例如如何处理重复元素或如何处理插入位置和删除位置的边界情况。维护跳表的平衡性也需要仔细考虑，以确保操作的高效性和正确性。不过总体来说，跳表的插入和删除操作可以通过谨慎地执行上述步骤来实现。

简单代码展示

回到基本实现上，先进行以上的基本理解，然后我们简单实现一版代码如下：

package org.zyf.javabasic.test.search;

import java.util.Random;

/**
 * @program: zyfboot-javabasic
 * @description: 用于表示跳表（Skip List）及其基本操作，包括插入、删除和查找
 * @author: zhangyanfeng
 * @create: 2024-04-14 12:43
 **/
public class SkipList {

    private static final int MAX_LEVEL = 16; // 最大级别
    private int level; // 当前最大级别
    private SkipListNode head; // 头节点
    private Random rand; // 用于生成随机级别的随机数

    // 构造函数
    public SkipList() {
        this.level = 0;
        this.head = new SkipListNode(Integer.MIN_VALUE, MAX_LEVEL);
        this.rand = new Random();
    }

    // 生成随机级别
    private int randomLevel() {
        int level = 0;
        while (rand.nextDouble() < 0.5 && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }

    // 插入节点
    public void insert(int val) {
        int newLevel = randomLevel();
        SkipListNode newNode = new SkipListNode(val, newLevel);
        SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode current = head;

        // 从*别开始查找插入位置
        for (int i = level; i >= 0; i--) {
            while (current.next[i] != null && current.next[i].val < val) {
                current = current.next[i];
            }
            update[i] = current;
        }

        // 更新最大级别
        if (newLevel > level) {
            for (int i = level + 1; i <= newLevel; i++) {
                update[i] = head;
            }
            level = newLevel;
        }

        // 插入节点
        for (int i = 0; i <= newLevel; i++) {
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
    }

    // 删除节点
    public void delete(int val) {
        SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode current = head;

        // 查找待删除节点位置
        for (int i = level; i >= 0; i--) {
            while (current.next[i] != null && current.next[i].val < val) {
                current = current.next[i];
            }
            update[i] = current;
        }

        // 删除节点
        if (current.next[0] != null && current.next[0].val == val) {
            SkipListNode deletedNode = current.next[0];
            for (int i = 0; i <= level; i++) {
                if (update[i].next[i] == deletedNode) {
                    update[i].next[i] = deletedNode.next[i];
                }
            }
            // 更新最大级别
            while (level > 0 && head.next[level] == null) {
                level--;
            }
        }
    }

    // 查找节点
    public boolean search(int val) {
        SkipListNode current = head;
        for (int i = level; i >= 0; i--) {
            while (current.next[i] != null && current.next[i].val < val) {
                current = current.next[i];
            }
        }
        current = current.next[0];
        return current != null && current.val == val;
    }

    class SkipListNode {
        int val;
        SkipListNode[] next;

        // 构造函数
        public SkipListNode(int val, int level) {
            this.val = val;
            this.next = new SkipListNode[level + 1];
        }
    }

    public static void main(String[] args) {
        SkipList skipList = new SkipList();

        // 插入节点
        skipList.insert(10);
        skipList.insert(20);
        skipList.insert(30);
        skipList.insert(40);
        skipList.insert(50);

        // 查找节点
        int target = 30;
        if (skipList.search(target)) {
            System.out.println("节点 " + target + " 存在于跳表中。");
        } else {
            System.out.println("节点 " + target + " 不存在于跳表中。");
        }

        // 删除节点
        skipList.delete(30);
        System.out.println("节点 " + target + "在跳表中删除节点后：");
        if (skipList.search(target)) {
            System.out.println("节点 " + target + " 存在于跳表中。");
        } else {
            System.out.println("节点 " + target + " 不存在于跳表中。");
        }
    }
}

四、哈希检索

哈希检索（Hash-Based Retrieval）是一种高效的数据检索方法，基于哈希函数将关键字映射到特定的数据存储位置。哈希检索通常能够在平均情况下实现O(1)级别的检索效率，使得它成为处理大规模数据集的一种重要技术。

（一）基本的常识分析

基本原理

1. 哈希函数：哈希检索的核心是哈希函数。哈希函数是一个将输入数据（例如关键字）映射到一个固定大小的哈希码或哈希值的函数。这个哈希码通常用作数据的索引。

2. 哈希表：哈希表是存储数据的数据结构，通常由一个数组构成，每个数组元素称为桶（bucket）。哈希函数将关键字映射到数组的索引位置，从而确定数据应该存储在哪个桶中。

3. 解决哈希冲突：由于哈希函数的映射可能导致不同的关键字映射到相同的索引位置，这种情况称为哈希冲突。哈希表需要一种方法来解决冲突，通常有两种主要方法：

• 链地址法：每个桶中存储一个链表或其他数据结构，用于存储具有相同哈希码的关键字的数据。当发生冲突时，新数据将附加到相应的链表上。
• 开放寻址法：在发生冲突时，尝试在哈希表中的其他位置寻找可用的桶，直到找到一个可用的位置为止。

特点和优点

1. 高效的检索：在平均情况下，哈希检索可以实现O(1)级别的检索效率，因为哈希函数直接将关键字映射到数据的存储位置，无需遍历整个数据集。

2. 适用于大规模数据集：哈希检索适用于大规模数据集，因为它的检索时间不会随着数据规模的增加而线性增长。

3. 快速插入和删除：哈希表通常支持快速的插入和删除操作，因为它们只需要计算哈希码并将数据存储在特定位置。

注意事项和限制

1. 哈希函数设计：设计一个好的哈希函数非常重要，它应该能够将不同的关键字均匀地映射到哈希表的不同位置，以减少冲突。

2. 哈希冲突处理：需要合适的冲突处理策略，例如链地址法或开放寻址法，以确保数据的正确存储和检索。

3. 空间要求：哈希表通常需要额外的内存来存储桶和哈希码，因此可能需要更多的内存空间。

4. 不适用于范围查询：哈希检索通常不适用于范围查询，因为它无法轻松找到一个范围内的数据，而需要遍历整个哈希表。

总之，哈希检索是一种高效的数据检索方法，特别适用于需要快速查找单个关键字的场景，如查找具有唯一标识符的数据。但需要注意哈希函数的设计和冲突处理以确保正确性和性能。

（二）扩展知识分析

Java 8后的HashMap优化：链表转换为红黑树+红黑树退化为链表

在Java 8之后，Java中的HashMap实现经历了重大改进，包括在链表长度达到一定阈值时将其转换为红黑树，以及在红黑树节点数量降低到一定阈值时将其退化为链表。这个改进主要涉及两个方面：性能和平衡。

链表转换为红黑树

当HashMap的链表长度达到一定的阈值（默认为8）时，Java 8引入了树化（Treeify）机制，将链表转换为红黑树。这是为了解决在极端情况下，链表可能变得非常长，导致查找、插入和删除的性能下降。树化的过程包括以下步骤：

1. 当链表长度达到阈值时，将链表转换为一个红黑树。
2. 如果哈希表的大小小于64，则会在树化之前扩大哈希表的容量，以确保树化后的负载因子在0.75以下。
3. 树化后，HashMap会使用红黑树的查找算法，将查找、插入和删除操作的性能从O(n)提高到O(log n)。

红黑树退化为链表

为了保持性能和平衡，当红黑树中的节点数量降低到一定阈值（默认为6）时，Java 8引入了退化（Untreeify）机制，将红黑树退化为链表。退化的过程包括以下步骤：

1. 当红黑树中的节点数量降低到阈值以下时，将红黑树还原为链表。
2. 如果哈希表的大小小于64，则会在退化之前缩小哈希表的容量，以确保负载因子保持在0.75以下。
3. 退化后，HashMap会使用链表的查找算法，将查找、插入和删除操作的性能回归到O(n)级别。

这种树化和退化机制的引入，使得Java中的HashMap在不同负载情况下能够保持较好的性能。在大多数情况下，HashMap能够提供O(1)级别的查找、插入和删除操作，但在极端情况下，它会自动调整数据结构以维持性能。这使得HashMap成为了一个高性能的数据结构，适用于各种应用场景。

（三）哈希表缺点分析

1. 冲突处理：冲突是指两个或多个不同的键被哈希函数映射到了相同的存储位置，这可能会导致性能下降。虽然哈希表有解决冲突的方法，如链地址法或开放寻址法，但在极端情况下，冲突仍然可能发生。

2. 不支持有序存储：哈希表中的数据是无序的，如果需要对数据进行有序访问或范围查询，哈希表不是最佳选择。有序数组或二叉搜索树等数据结构更适合这些需求。

3. 不适用于小规模数据集：对于小规模的数据集，哈希表可能因为内存占用较高而不划算。哈希表需要预留一定数量的空间来保持性能，对于小数据集来说，可能会浪费大量的内存。

4. 哈希函数设计：设计一个好的哈希函数对于哈希表的性能至关重要。一个不好的哈希函数可能导致冲突更频繁，从而降低性能。

5. 内存占用：为了保持性能，哈希表通常需要具有一定的冗余空间。这意味着在存储相对稀疏的数据时，哈希表可能占用较多的内存。

6. 不适用于高并发写入场景：在高并发写入场景下，多个线程可能同时尝试修改哈希表，需要采用并发控制机制来保护数据结构的一致性，这会增加复杂性。

总的来说，哈希表在大多数情况下都是高效的数据结构，但它不是适用于所有场景的通用解决方案。在选择数据结构时，需要综合考虑应用的