算法笔记汇总精简版下载_算法与数据结构笔记

【01-概述】

10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树； 10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态 规划、字符串匹配算法。

【复杂度分析】 一、什么是复杂度分析？ 1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。 2.因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。 3.分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。 4.复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。

二、为什么要进行复杂度分析？ 1.和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。 2.掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。

三、如何进行复杂度分析？ 1.大O表示法 (1）来源 算法的执行时间与每行代码的执行次数成正比，用T(n) = O(f(n))表示，其中T(n)表示算法执 行总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。 (2）特点 以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所 以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析 时忽略这些项。 2.复杂度分析法则 1）单段代码看高频：比如循环。 2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。 3）嵌套代码求乘积：比如递归、多重循环等 4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

四、常用的复杂度级别？ 多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括: O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）、O(n^3)（立方阶） 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括: O(2^n)（指数阶）、O(n!)（阶乘阶）

五、复杂度分析的4个概念 1.最坏情况时间复杂度：代码在最理想情况下执行的时间复杂度。 2.最好情况时间复杂度：代码在最坏情况下执行的时间复杂度。 3.平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。 4.均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基 本上均摊结果就等于低级别复杂度。

六、为什么要引入这4个概念？ 1.同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入这4个概念。 2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。

七、如何分析平均、均摊时间复杂度？ 1.平均时间复杂度 代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。 2.均摊时间复杂度 两个条件满足时使用：1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别 复杂度；2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

【02-数组和链表】

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。 数组、链表、队列、栈等都是线性表结构。 与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

1.线性表 线性表就是数据排成像一条线一样的结构。常见的线性表结构：数组，链表、队列、栈等。

2. 连续的内存空间和相同类型的数据 优点：两限制使得具有随机访问的特性 缺点：删除，插入数据效率低（为何数组插入和删除低效？） 【插入】 若有一元素想往int[n]的第k个位置插入数据，需要在k-n的位置往后移。 最好情况时间复杂度 O(1)，最坏情况复杂度为O(n)，平均负责度为O(n) 如果数组中的数据不是有序的，也就是无规律的情况下，可以直接把第k个位置上的数据移到 最后，然后将插入的数据直接放在第k个位置上。 这样时间复杂度就将为 O(1)了。 【删除】 与插入类似，为了保持内存的连续性。 最好情况时间复杂度 O(1)，最坏情况复杂度为O(n)，平均复杂度为O(n) 提高效率：将多次删除操作中集中在一起执行，可以先记录已经删除的数据，但是不进行数据迁移，而仅仅是记录，当发现没有更多空间存储时，再执行真正的删除操作。 这也是 JVM标记清除垃圾回收算法的核心思想。

用数组还是容器？ 数组先指定了空间大小，容器如ArrayList可以动态扩容。 1.希望存储基本类型数据，可以用数组 2.事先知道数据大小，并且操作简单，可以用数组 3.直观表示多维，可以用数组 4.业务开发，使用容器足够，开发框架，追求性能，首先数组。

为什么数组要从 0 开始编号？ 由于数组是通过寻址公式，计算出该元素存储的内存地址：a[i]_address = base_address + i * data_type_size 如果数组是从 1 开始计数，那么就会变成：a[i]_address = base_address + （i-1）* data_type_size 对于CPU来说，多了一次减法的指令。当然，还有一定的历史原因。

缓存 是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。 缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。 常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。

缓存实际上就是利用了空间换时间的设计思想。 对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化； 而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。

如何用链表来实现 LRU 缓存淘汰策略呢？ 三种最常见的链表结构，它们分别是：单链表、双向链表、循环链表、双向循环链表。 1.单链表 (1）每个节点只包含一个指针，即后继指针。 (2）单链表有两个特殊的节点，即首节点和尾节点。为什么特殊？用首节点地址表示整条链表，尾节点的后继指针指向空地址null。 (3）性能特点：插入和删除节点的时间复杂度为O（1），查找的时间复杂度为O(n)。 2.循环链表 (1）除了尾节点的后继指针指向首节点的地址外均与单链表一致。 (2）适用于存储有循环特点的数据，比如约瑟夫问题。 3.双向链表 (1）节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针prev）和下一个节点地址（后继指针next）。 (2）首节点的前驱指针prev和尾节点的后继指针均指向空地址。

与数组一样，链表也支持数据的查找、插入和删除操作。 数组和链表是两种截然不同的内存组织方式。正是因为内存存储的区别，它们插入、删除、随机访问操作的时间复杂度正好相反。

选择数组还是链表？ 1.插入、删除和随机访问的时间复杂度 数组：插入、删除的时间复杂度是O(n)，随机访问的时间复杂度是O(1)。 链表：插入、删除的时间复杂度是O(1)，随机访问的时间复杂端是O(n)。 2.数组缺点 (1）若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。 (2）大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。 3.链表缺点 (1）内存空间消耗更大，因为需要额外的空间存储指针信息。 (2）对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC（自动垃圾回收器）操作。 4.如何选择？ 数组简单易用，在实现上使用连续的内存空间，可以借助CPU的缓冲机制预读数组中的数据，所以访问效率更高，而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法预读。如果代码对内存的使用非常苛刻，那数组就更适合。

1.对于指针（或者引用）的理解： 将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

2.我们插入结点时，一定要注意操作的顺序；删除链表结点时，也一定要记得手动释放内存空间，否则，也会出现内存泄漏的问题。

3. 利用哨兵简化难度 链表的插入、删除操作，需要对插入第一个结点和删除最后一个节点做特殊处理。利用哨兵对象可以不用边界判断，链表的哨兵对象是只存指针不存数据的头结点。

4. 重点留意边界条件处理 操作链表时要考虑链表为空、一个结点、两个结点、头结点、尾结点的情况。学习数据结构和算法主要是掌握一系列思想，能在其它的编码中也养成考虑边界的习惯。

经常用来检查链表代码是否正确的边界条件有这样几个： 如果链表为空时，代码是否能正常工作？ 如果链表只包含一个结点时，代码是否能正常工作？ 如果链表只包含两个结点时，代码是否能正常工作？ 代码逻辑在处理头结点和尾结点的时候，是否能正常工作

经典链表操作案例： * 单链表反转 * 链表中环的检测 * 两个有序的链表合并 * 删除链表倒数第 n 个结点 * 求链表的中间结点

【03-栈&队列&递归】

【栈】 后进先出，先进后出，这就是典型的“栈”结构。 任何数据结构都是对特定应用场景的抽象，数组和链表虽然使用起来更加灵活，但却暴露了几乎所有的操作，难免会引发错误操作的风险。 当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。 栈主要包含两个操作，入栈和出栈。 实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。 对于出栈操作来说，我们不会涉及内存的重新申请和数据的搬移，所以出栈的时间复杂度仍然是O(1)。但是，对于入栈操作来说，情况就不一样了。当栈中有空闲空间时，入栈操作的时间复杂度为 O(1)。但当空间不够时，就需要重新申请内存和数据搬移，所以时间复杂度就变成了O(n)。

【队列】 先进者先出，这就是典型的“队列”。 最基本的两个操作：入队enqueue()，放一个数据到队列尾部；出队dequeue()，从队列头部取一个元素。队列可以用数组或者链表实现，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。 队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。 在数组实现队列的时候，会有数据搬移操作，要想解决数据搬移的问题，我们就需要像环一样的循环队列。 阻塞队列就是在队列为空的时候，从队头取数据会被阻塞，因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后在返回。 在多线程的情况下，会有多个线程同时操作队列，这时就会存在线程安全问题。能够有效解决线程安全问题的队列就称为并发队列。 基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。 而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就相对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资源、发挥最大性能。 实际上，对于大部分资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。

【递归】 递归需要满足的三个条件： 1. 一个问题的解可以分解为几个子问题的解 2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样 3. 存在递归终止条件 写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。递归代码虽然简洁高效，但是，递归代码也有很多弊端。比如，堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等，所以，在编写递归代码的时候，一定要控制好这些副作用。

递归的优缺点？ 1.优点：代码的表达力很强，写起来简洁。 2.缺点：空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。

递归常见问题及解决方案 1.警惕堆栈溢出：可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出。 2.警惕重复计算：通过某种数据结构来保存已经求解过的值，从而避免重复计算。

【04-排序】

几种最经典、最常用的排序方法：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。

对于排序算法执行效率的分析，我们一般会从这几个方面来衡量： 1. 最好情况、最坏情况、平均情况时间复杂度 2. 时间复杂度的系数、常数 、低阶 3. 比较次数和交换（或移动）次数

排序算法的稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

【冒泡排序（Bubble Sort）】 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。 如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

* Q:第一，冒泡排序是原地排序算法吗？ A:冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为O(1)，是一个原地排序算法。 * Q:第二，冒泡排序是稳定的排序算法吗？ A:在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。 * Q:第三，冒泡排序的时间复杂度是多少？ 最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n²)。

【插入排序（Insertion Sort）】 我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。 插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。 重复这个过程，直到未排序区间中元素为空，算法结束。

* 空间复杂度：插入排序是原地排序算法。 * 时间复杂度：1. 最好情况：O(n)。2. 最坏情况：O(n^2)。3. 平均情况：O(n^2) * 稳定性：插入排序是稳定的排序算法。

【选择排序（Selection Sort）】 选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

* 选择排序空间复杂度为 O(1)，是一种原地排序算法。 * 选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为O(n²)。 * 选择排序是一种不稳定的排序算法。

冒泡排序和插入排序的时间复杂度都是 O(n²)，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢？ 从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3 个赋值操作，而插入排序只需要 1 个。

如何在 O(n) 的时间复杂度内查找一个无序数组中的第 K 大元素？需要用到两种时间复杂度为 O(nlogn) 的排序算法：归并排序和快速排序。这两种排序算法适合大规模的数据排序。

【归并排序（Merge Sort）】 如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

归并排序使用的就是分治思想。分治算法一般都是用递归来实现的。（分治是一种解决问题的处理思想，递归是一种编程技巧）

* 归并排序是一个稳定的排序算法。 * 归并排序的时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。 * 但是，归并排序不是原地排序算法，归并排序的空间复杂度是 O(n)。（因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间）

【快速排序（Quicksort）】 快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。 我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot放到中间。 经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。 根据分治、递归的处理思想，我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到r 之间的数据，直到区间缩小为 1，就说明所有的数据都有序了。

* 快排是一种原地、不稳定的排序算法。 * 快排的时间复杂度也是 O(nlogn)

归并排序和快速排序是两种稍微复杂的排序算法，它们用的都是分治的思想，代码都通过递归来实现，过程非常相似。 归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法，这也使它存在致命的缺点，即归并排序不是原地排序算法，空间复杂度比较高，是 O(n)。正因为此，它也没有快排应用广泛。 快速排序算法虽然最坏情况下的时间复杂度是 O(n )，但是平均情况下时间复杂度都是O(nlogn)。 不仅如此，快速排序算法时间复杂度退化到 O(n ) 的概率非常小，我们可以通过合理地选择 pivot 来避免这种情况。

三种时间复杂度是 O(n) 的排序算法：桶排序、计数排序、基数排序。因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序（Linear sort）。

【桶排序（Bucket sort）】 将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

桶排序对要排序数据的要求是非常苛刻的。首先，要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。

桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

【计数排序（Counting sort）】—— 其实是桶排序的一种特殊情况 当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间

计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

问题：如何根据年龄给100万用户数据排序？ 我们假设年龄的范围最小 1 岁，最大不超过 120 岁。我们可以遍历这 100 万用户，根据年龄将其划分到这 120个桶里，然后依次顺序遍历这 120 个桶中的元素。这样就得到了按照年龄排序的 100 万用户数据。

【基数排序（Radix sort）】 假设有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序，你有什么比较快速的排序方法呢？ 有这样的规律：假设要比较两个手机号码 a，b 的大小，如果在前面几位中，a手机号码已经比 b 手机号码大了，那后面的几位就不用看了。

基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

如何实现一个通用的、高性能的排序函数？ 快速排序比较适合来实现排序函数，如何优化快速排序？最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。为了提高排序算法的性能，要尽可能地让每次分区都比较平均。 * 1. 三数取中法 ①从区间的首、中、尾分别取一个数，然后比较大小，取中间值作为分区点。 ②如果要排序的数组比较大，那“三数取中”可能就不够用了，可能要“5数取中”或者“10数取中”。 * 2.随机法：每次从要排序的区间中，随机选择一个元素作为分区点。 * 3.警惕快排的递归发生堆栈溢出，有2种解决方法，如下： ①限制递归深度，一旦递归超过了设置的阈值就停止递归。 ②在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈过程，这样就没有系统栈大小的限制。

通用排序函数实现技巧 1.数据量不大时，可以采取用时间换空间的思路 2.数据量大时，优化快排分区点的选择 3.防止堆栈溢出，可以选择在堆上手动模拟调用栈解决 4.在排序区间中，当元素个数小于某个常数是，可以考虑使用O(n^2)级别的插入排序 5.用哨兵简化代码，每次排序都减少一次判断，尽可能把性能优化到极致

【05-查找&跳表&散列表】

【二分查找】 二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。 二分查找是一种非常高效的查找算法，时间复杂度是 O(logn)。O(logn) 这种对数时间复杂度，是一种极其高效的时间复杂度，有的时候甚至比时间复杂度是常量级O(1) 的算法还要高效。二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。

使用循环和递归都可以实现二分查找。

二分查找应用场景的局限性： * 二分查找依赖的是顺序表结构，简单点说就是数组。（链表不可以） * 二分查找针对的是有序数据。（如果数据没有序，我们需要先排序。） * 数据量太大不适合二分查找。

四种常见的二分查找变形问题 1.查找第一个值等于给定值的元素 2.查找最后一个值等于给定值的元素 3.查找第一个大于等于给定值的元素 4.查找最后一个小于等于给定值的元素

适用性分析 1.凡事能用二分查找解决的，绝大部分我们更倾向于用散列表或者二叉查找树，即便二分查找在内存上更节省，但是毕竟内存如此紧缺的情况并不多。 2.求“值等于给定值”的二分查找确实不怎么用到，二分查找更适合用在”近似“查找问题上。比如上面讲几种变体。

【跳表】 跳表是一种动态数据结构，可以支持快速的插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树（Red-black tree）。Redis 中的有序集合（Sorted Set）就是用跳表来实现的。 链表加多级索引的结构，就是跳表。

在一个单链表中查询某个数据的时间复杂度是 O(n)。那在一个具有多级索引的跳表中查询任意数据的时间复杂度是 O(logn)。这 个查找的时间复杂度跟二分查找是一样的。换句话说，我们其实是基于单链表实现了二分查找。（这种查询效率的提升，前提是建立了很多级索引，也就是空间换时间的设计思路。）

跳表的空间复杂度是O(n)。也就是说，如果将包含 n 个结点的单链表构造成跳表，我们需要额外再用接近 n 个结点的存储空间。

在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。

跳表这个动态数据结构，不仅支持查找操作，还支持动态的插入、删除操作，而且插入、删除操作的时间复杂度也是 O(logn)。

作为一种动态数据结构，我们需要某种手段来维护索引与原始链表大小之间的平衡，也就是说，如果链表中结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入、删除操作性能下降。

跳表是通过随机函数来维护“平衡性”，当我们往跳表中插入数据的时候，我们可以选择同时将这个数据插入到部分索引层中。

为什么 Redis 要用跳表来实现有序集合，而不是红黑树？ Redis 中的有序集合支持的核心操作主要有下面这几个： * 插入一个数据； * 删除一个数据； * 查找一个数据； * 按照区间查找数据（比如查找值在 [100, 356] 之间的数据）； * 迭代输出有序序列。 对于按照区间查找数据这个操作，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做非常高效。

【散列表】 用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

散列函数，可以把它定义成hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。 散列函数设计的基本要求： 1. 散列函数计算得到的散列值是一个非负整数； 2. 如果 key1 = key2，那 hash(key1) == hash(key2)； 3. 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

散列冲突 再好的散列函数也无法避免散列冲突。常用的散列冲突解决方法有两类，开放寻址法（open addressing）和链表法（chaining）。

开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。三种探测方法是：线性探测（Linear Probing）、二次探测（Quadratic probing）、双重散列（Double hashing）。

【06-哈希】

哈希算法的定义：将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。常见的例如：MD5、SHA。

设计一个优秀的哈希算法需要满足的几点要求： * 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）； * 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同； * 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小； * 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

哈希算法的七个常见应用： * 安全加密：MD5、SHA、DES、AES。很难根据哈希值反向推导出原始数据；散列冲突的概率要很小（因为无法做到零冲突）。 * 唯一标识：哈希算法可以对大数据做信息摘要，通过一个较短的二进制编码来表示很大的数据。 （1）海量的图库中，搜索一张图是否存在 * 数据校验：校验数据的完整性和正确性。 * 散列函数：对哈希算法的要求非常特别，更加看重的是散列的平均性和哈希算法的执行效率。 * 负载均衡：利用哈希算法替代映射表，可以实现一个会话粘滞的负载均衡策略。 （1）在同一个客户端上，在一次会话中的所有请求都路由到同一个服务器上。 * 数据分片：通过哈希算法对处理的海量数据进行分片，多机分布式处理，可以突破单机资源的限制。 （1）如何统计“搜索关键词”出现的次数？ （2）如何快速判断图片是否在图库中？ * 分布式存储：利用一致性哈希算法，可以解决缓存等分布式系统的扩容、缩容导致数据大量搬移的难题。 （1）如何决定将哪个数据放到哪个机器上？ （2）一致性哈希算法

【07-二叉树】

之前说的栈和队列都是线性表结构，树是非线性表结构。

关于树的常用概念：根节点、叶子节点、父节点、子节点、兄弟节点，还有节点的高度、深度、层数，以及树的高度。

最常用的树就是二叉树（Binary Tree）。二叉树的每个节点最多有两个子节点，分别是左子节点和右子节点。 二叉树中，有两种比较特殊的树，分别是满二叉树和完全二叉树。满二叉树又是完全二叉树的一种特殊情况。

二叉树的两种存储方式： (1）用链式存储： * 每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。 * 我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。 * 这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。

（2）用数组顺序存储： * 如果节点 X 存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子节点，下标为 2 * i + 1 的位置存储的就是右子节点。 * 反过来，下标为 i/2 的位置存储就是它的父节点。 * 通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。 * 数组顺序存储的方式比较适合 完全二叉树，其他类型的二叉树用数组存储会比较浪费存储空间。

如果某棵二叉树是一棵完全二叉树，那用数组存储是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。（这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。）堆 就是一种完全二叉树，最常用的存储方式就是数组。

【二叉树的遍历】 二叉树里非常重要的操作就是前序遍历、中序遍历、后序遍历，用递归代码来实现遍历的时间复杂度是 O(n)。其中，前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。 （1）前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。 * preOrder(r) = print r->preOrder(r->left)->preOrder(r->right) （2）中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。 * inOrder(r) = inOrder(r->left)->print r->inOrder(r->right) （3）后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。 * postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

【二叉查找树（Binary Search Tree）】 二叉查找树是为了实现快速查找而生的，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

1. 二叉查找树的查找操作 先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。（感觉有点像 二分查找）

2. 二叉查找树的插入操作 二叉查找树的插入过程有点类似查找操作。新插入的数据一般都是在叶子节点上，所以我们只需要从根节点开始，依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

3. 二叉查找树的删除操作 针对要删除节点的子节点个数的不同，需要分三种情况来处理： * 如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。 * 如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。 * 如果要删除的节点有两个子节点，需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。

4. 二叉查找树的其他操作 二叉查找树中还可以支持快速地查找最大节点和最小节点、前驱节点和后继节点。 二叉查找树还有一个重要的特性，就是中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。因此，二叉查找树也叫作二叉排序树。

支持重复数据的二叉查找树：如果存储的两个对象键值相同，有两种解决方法。 * 第一种方法：二叉查找树中每一个节点不仅会存储一个数据，因此我们通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。 * 第二种方法：每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。对于删除操作，我们也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。

二叉查找树的时间复杂度分析： 完全二叉树（或满二叉树），不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是 O(height)。二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度是O(logn)。

* 有了高效的散列表（时间复杂度是 O(1)），为什么还需要二叉查找树？ 1. 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。 2. 散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在O(logn)。 3. 笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。 4. 散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。 5. 为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。 综合这几点，平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/167925.html原文链接：https://javaforall.cn