读书笔记_算法第四版（一）
算法第四版（谢路云译）
官方网站：http://algs4.cs.princeton.edu/home/包含了部分源代码以及部分课后习题解答
个人练习代码：https://github.com/morefans/AlgorithmsFourthEdition
第1章 基础
1.1 基础编程模型
Java程序的核心架构；基础数据类型及其表达方式；指令；简明表示方法；数组结构；静态操作流程；应用程序接口（API）；文本字段（字符串）；输入输出管理流程（I/O处理）；折半查找算法
l 以下为“答疑”和“练习”中的知识点：
l Math.abs(-2147483648)返回-2147483648（整数溢出）。
1.2 数据抽象
采用抽象数据类型进行操作；展示一些典型的 abstract data type 例证；开发具体实现细节；探讨其他相关 abstract data type 的具体构建方法；详细规划各类别数据存储与操作的方案
l 以下为“答疑”和“练习”中的知识点：
1.3 背包、队列和栈
多种基础数据类型都与对象集合之间存在一定关联关系。具体而言，在这些数据类型中存有共同特征即其值即为一组特定的对象所构成的整体，并且各种操作均围绕着对这些对象进行增删以及相应的查询操作展开分析研究。其中典型的例子包括背包模型、队列结构以及栈型组织等，在这些常见模型中它们之间的区别主要体现在操作对象的顺序上有所不同。
在本系统中使用了泛型与迭代机制，并要求Iterable接口必须实现publicIterator
public class Bag
public class Queue
public class Stack
原始数据类型则通过Java的自动装箱机制将boolean值及其基本数值类型如byte值等转换为对应的Boolean对象及相应的BasicType对象，并随后利用自动拆箱机制将这些对象恢复为原始类型的数据值。
背包：是一种专为不支持删除操作设计的集合结构，在该结构中专门用于收集元素并按任意顺序获取这些收集到的元素。
先进先出队列（FIFO）：一种遵循先进先出原则的集合类型，在使用时会同时按照元素加入的顺序进行存储与取出操作，并且在入队与出队操作中均遵循同一顺序。
l 后进先出（LIFO）：一种基于先进后出策略的数据结构类型
首先构建固定容量的String栈FixedCapacityStackOfStrings类，并仅支持String类型的元素以及固定容量；随后通过泛型机制扩展FixedCapacityStack类；接着增加resize(int capacity)方法，并相应地优化push和pop方法以确保不会溢出，并使使用率达到至少四分之一；最后支持Iterable接口完成ResizingArrayStack类的开发
对象脱离：Java垃圾回收机制负责清除所有无法被其他对象访问的对象内存区域。若某个无需被其他对象调用的对象依然保有一个外部引用，则该对象被称为游离对象。为了避免出现此类情况，请确保相关对象的引用域为空或将其删除以消除潜在风险
该任务要求对输入文本进行同义改写以降低重复率，请确保仅改变表达方式而不改变原意
示例
需要改写的文本内容
该任务要求对输入文本进行同义改写以降低重复率，请确保仅改变表达方式而不改变原意
需要改写的文本内容
l 链表队列的实现，背包就是去掉pop()的Stack。
自行实现循环队列：包括固定容量的FixedCapacityQueue类和可动态调整容量的同时支持迭代遍历的ResizingArrayQueue类
除了动态规划问题中的背包问题以及先进先出的队列和后进先出的栈结构之外
l 以下为“答疑”和“练习”中的知识点：
为什么Java不允许泛型数组：围绕这一问题的讨论仍在进行中，对于新手来说，请先熟悉共变数组（covariant arrays）和类型擦除（type erasure）的概念。
Java class中的嵌套类Node在javac环境下进行编译后会生成一个名为Stack$Node.class的文件。
l Java数组支持foreach遍历（for(inti : int[] array)）。
l 应尽量避免使用大接口（具有诸多功能以提高适应性），因为这可能导致低效，并且可能导致意外情况出现；其实这是一种冗余设计
可以用该Stack类实现十进制转二进制的功能（习题1.3.5）。通过结合该Stack与Queue可实现队列的逆序操作（习题1.3.6）。可将中缀表达式转换为后缀表达式（习题1.3.10）。建议您自行完成相关链表练习以巩固知识。此外还有专门的双向队列练习涉及两种不同的实现方式：双向链表实现与动态数组实现。
1.4 算法分析
科学方法：通过细致地观察真实世界的特性，并通常辅以精确测量来获取信息；基于观察到的数据构建理论模型；通过理论模型推算未来时间的发展趋势；持续进行观测，并对预测结果的准确性进行验证；不断重复上述过程直至预测结果与实际观测数据保持一致。
一个程序运行所需的总时间主要取决于两个方面：每次运行每个指令所需的时间（受计算机、Java编译器以及操作系统的共同影响），以及每个指令出现的次数（由程序逻辑以及输入数据决定）。将这两个因素相乘，并将所有指令的成本进行累加即可得出总的运行时间
l 时间复杂度（程序运行时间的增长数量级）和空间复杂度。
l 理解问题规模的上界和时间复杂度的下界。
l 注意事项：较大的常数值、非决定性的内循环、指令所需的时间、系统相关因素、无须轻重之分、对输入高度依赖以及涉及多个问题参数
Java对象必须包含24 字节数组头；而像 int 数组这样的类型则需要 20 + (8 \times N) 字节数组空间（其中当 N 为奇数时还需添加填充数据），double 数组则需要 16 + (16 \times N) 字节数组空间。因此 String 对象总共占用 16 + (3 \times 5) + 8 \times (5 - 1) = 79 字节数组空间；此外还需 56 字节数组空间来存储可变长度的字符数据。
l 以下为“答疑”和“练习”中的知识点：
l 双调查找是一种基于加减运算的二分查找算法（即斐波那契查找法）。抛硬币决策法通常用于解决"扔一个鸡蛋"或"扔两个鸡蛋"的问题以确定最优策略。使用两个栈结构可以模拟队列功能（共有三种不同的方法）。一个队列结构可模拟栈的操作；而使用两个队列结构也可以模拟栈的功能；最后一个问题在于判断当前状态是"热"态还是"冷"态。
1.5 案例研究：union-find算法
动态连通性，union-find算法，三种实现。
1、 用集合来保存，标识为某一个触点，即quick-find算法。
用森林来保存每一个触点id[i]指向自己或者其所属连通分量中的另一个触点，则该触点即为根触点。该方法对应的是 quick-union数据结构，在每次合并操作中，并没有固定的选择策略；然而，在实际应用中，并不能确保相比 quick-find 算法具有更快的性能。
为了存储并优化了快速联合算法（加权版本），该方法记录各棵树中的节点数量，并通过将较小规模的树合并到较大规模的树中来实现操作时间维持在对数时间内。
4、经过路径压缩优化后的加权Quick-Union算法被认为是目前最有效的解决方案；然而，并非所有操作都可以在恒定时间内完成。
第2章 排序
2.1 初级排序算法
排序算法主要可分为两种类型：一种是不需额外内存即可完成排序操作的原地排序算法（其核心在于利用数据结构中的栈等有限资源完成排列组合），另一种则需预先分配足够的临时存储空间以复制完整数据副本从而实现更复杂的运算需求。
l 选择排序：挑选出当前最小元素并放置到当前位置，在第k轮筛选时确定第k小元素的位置。约需N²/2次比较操作及进行N次交换操作，在时间复杂度上表现最差为O(n²)，且运行时间不受输入数据顺序影响。数据移动次数达到理论最低值。
插入排序是一种方法，在这种情况下左边已经排好序。具体来说，在每一步中我们依次将新元素加入到已有序的一端进行对比，并将该新元素与其前面的所有元素进行逐一比较以确定其正确位置。
在平均情况下约需N^{\wedge} 2 / 4次比较操作以及同样次数的交换操作。
而最坏情况下约需N^{\wedge} 2 / 2 次的计算量。
最优情况下仅需 O(N) 的时间复杂度。
对于部分有序的数据序列而言，
其运行效率往往超越本章介绍的所有算法，
尤其当逆序程度较小时，
这种算法的优势更加明显。
希尔排序基于插入排序原理，在步长h的基础上依次对相隔h个位置上的元素执行直接插入排序，并逐步缩减步长至1。其高效性源自平衡子数组规模与有序程度之间的关系。适用于处理较大规模的数据集，并且其时间复杂度低于n²的数量级，在O(n^1.5)数量级内表现良好。值得注意的是，在实际应用中有时会被认为是不错的选择（尤其是在处理中等规模的数据时），因为它代码简洁且占用内存少。不过需要注意的是，在后续章节我们将探讨更为高效的方法——它们虽然在速度上可能快出2倍（甚至更多），但实现起来较为复杂
l 以加快速度有效应对那些现有方法难以处理的问题是研究算法设计与性能优化的核心关注点之一。
l 以下为“答疑”和“练习”中的知识点：
当所有主键相同时，在基于插槽的插入序列中实现的数据交换次数明显少于直接实现的选择序列中的交换次数；而对于逆序排列的数据集而言，在选择性排列中采用选择法进行速度反而快于采用插槽法；此外，在数据元素仅取三种离散值时，在随机性排列的情况下采用插槽法进行的时间复杂度仍保持平方级别；出队列式地对数据进行有序排列的过程通常遵循以下步骤：首先根据设定条件筛选出当前最小（或最大）值，并将其移动至适当的位置；重复此过程直至所有数据均被有序放置完毕。
2.2 归并排序
采用归并排序的方法将数组分成两半分别进行排序，并将结果有序地合并起来。这种分治策略使得排序过程更加高效有序。
基于自顶向下的归并策略，在排序过程中会按照从较大的块开始逐步细分的顺序进行操作。该方法通过递归方法实现，并且实际上最终的归并过程总是始于两个元素。在比较次数方面介于0.5 N lg N至 N lg N次之间，在实际操作中最大访问次数为6 N lg N次。
自底向上的归并：从二元扩展至多元，并通过迭代过程完成合并操作。所需比较次数在0.5N lg N至N lg N之间，并且最大访问次数为6 × N lg N次。
归并排序表明，在具备采用其中一种方法来解决一个问题能力时，请考虑尝试另一种方法。
没有一种基于比较的方法能够确保对长度为N的数组进行排序所需使用的最少比较次数少于lg(N!)到NlgN次。（借用二叉决策树理论可以证明这一结论）
l 以下为“答疑”和“练习”中的知识点：
所有元素一致时归并排序的计算时间是线性的；当多个值重复出现时其时间复杂度仍维持在O(n log n)水平
归并排序的三种改进措施：第一种改进措施是通过采用插入排序算法来加速处理小型数据块；第二种改进措施是通过比较中间元素及其后一个元素来判断数组是否已排好序；第三种改进措施是通过在相邻位置交换参数来避免不必要的数据拷贝。
链表排序（选择排序，插入排序，冒泡排序，所有排序）。
合并有序序列，并从下往上构建有序队列的归 merge 排序；自然归 merge 排序（即自适应归 merge 排序），通过已有有序区域进行处理。
打乱链表的过程通常涉及随机选择节点以避免O(n²)的时间消耗。另一种方法是使用数组来临时存储节点进行重新排列。本题要求算法的时间复杂度为O(n log n)，空间复杂度为O(log n)。最初尝试的是递归方法，但发现这种方法仅实现了局部顺序的调整，并未达到理想效果。因此需要寻找新的解决方案，在此过程中参考了Quora上的讨论以及StackOverflow上的技术见解。由于迭代方法在确定左右链表大小时较为繁琐，在此采用递归策略并取得了不错的效果。
非直接排序算法用于实现归并排序过程，在此过程中不会修改原始数组，并生成一个int[] perm数组。其中每个元素perm[i]表示第i小元素的位置关系。其本质上是将perm数组进行归并排序，在排序过程中，在每次比较时会从array（原始数组）和perm（生成排列）中取出相应的元素来进行比较。
trivariate mergesort divides the array into three intervals instead of two segments for merging. While this approach introduces a few more comparisons, the fundamental principle remains largely the same. The time complexity is still O(n log n).
2.3 快速排序
可能被广泛应用于各种排序场景中的一种算法。其主要原因在于实现上非常简单，并且能够适应不同类型的输入数据，并在实际应用中的效率通常显著高于其他方法。此外该算法采用了原地排列的方式运行并且其时间复杂度为O(n log n)
快速排序作为一种基于分支的排序算法，在处理输入时会将其划分为两个子数组，并对这两部分分别进行独立的排序。切分（partition）位置由输入数据决定
快速排序通常情况下消耗~2NlnN次比较（并额外进行约1/6次交换），其最坏情况下可能达到大约N²/2次比较。然而，在预先对数组进行随机化处理后，则可避免这种极端情况的发生。
快速排序改进措施包括：较小规模的数据采用直接插入法更为高效。在进行三项比较时选择中间值作为划分基准以提高稳定性。适用于数据重复较多的情况则使用三项切分法具体来说就是将数据划分为大于中间值的部分、等于中间值的部分以及小于中间值的部分。当处理仅包含有限种不同主键的随机排列数值序列时算法的时间复杂度达到最低水平约为(2 ln 2) NH 次比较操作其中H为由主键值出现频率定义的香农信息量
l 以下为“答疑”和“练习”中的知识点：
l 将数组平分希望提高性能，用现有算法，是做不到的。
将已知只有两种主键值得数组排序。
非递归的快速排序，借助栈，存取每个要进行切分的子数组首尾位置。
快速三向切分是一种高效算法，在将重复元素放置于子数组两端后能够达成信息量最优的排序
2.4 优先队列
在编程中，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况下，默认情况
l 优先队列的关键几个典型应用场景涵盖模拟系统、任务调度以及数值计算等。
l 优先队列初级实现：采用无序数组的方式（惰性策略），采用有序数组的方式（积极策略），以及使用链表（可选）。这些要么是插入或删除操作的时间复杂度均为O(n)，要么则时间复杂度均为O(logn)。
l 堆（二叉堆）：本质上就是一棵二叉树，在编程实现时通常使用数组存储节点。其中第1个位置不被使用（索引从1开始），节点k的左子节点为2k而右子节点为2k+1；其父节点的位置为⌊k/2⌋向下取整。插入操作的具体步骤如下：将新数据添加至数组末尾并增加堆大小；随后让该新元素上浮至合适的位置以维持堆的性质。删除最大值的操作流程是：移除当前队列头部的最大值，并将队列末尾的有效数据移动至头部位置；接着减少堆大小并让该元素下沉至正确位置以保持堆结构的有效性。
对于一个基于堆实现的优先队列来说，在处理最多包含N个元素的情况下进行插入操作所需的时间复杂度仅为O(log N + 1)级别，在每次删除最大值的操作中所需的时间复杂度也不超过O(2 log N)级别
l 索引优先队列：仅对索引进行优先队列排序。
l 堆排序：将所有元素依次加入一个用于快速找到最小值的优先队列中；接着反复执行删除最小值的操作直至全部取出。构建堆所需的时间主要体现在比较次数上（少于2N次）以及交换操作（少于N次）。
l 首先进行下潜操作后再进行上浮操作（move down, move up）：大多数在下潜阶段重新插入堆中的元素会被直接放置到底层。 Floyd于1964年观察发现 我们实际上可以通过省略检查元素是否已到达其正确位置的过程来节省时间 在下潜过程中会一直提升较大的子节点直至抵达底层 然后会将这些元素逐步推至上层直到找到合适的位置 这种方法几乎可以将比较次数减少一半 但在某些情况下可能会占用额外的空间 因此只有当比较操作的成本较高时才具有实际应用价值 例如在对字符串或其他键值较长的数据进行排序时 就会体现出这一优势
堆排序在数据结构与算法领域的重要性不言而喻,它是唯一能够在最优时间和空间资源条件下完成排序任务的方法,即使是在最坏情况下也能保证约2NlgN次的关键字比较以及恒定数量的额外存储空间需求。这种高效性使得它特别适合应用于资源受限的情境,例如嵌入式系统或低成本移动设备等环境。然而,在现代复杂的应用系统中,堆排序的应用却相对较少,其主要原因在于其对缓存机制缺乏有效利用,并且与邻近元素之间的比较次数相对较少,因此在这种场景下会导致较高的缓存缺失频率,远高于那些主要基于邻近元素比较的操作（如快速排序、归并排序以及希尔排序等）。另一方面,基于堆结构实现的优先队列正在变得越来越不可或缺,因为它们能够在处理插入操作与删除最大值操作交织在一起的动力学场景时提供对数级别的时间复杂度保障。
l 以下为“答疑”和“练习”中的知识点：
采用通用类型的Item是由于delMax()函数的作用避免了将返回值显式地转换为特定类型的原因。例如String。
在堆结构中不采用第0号索引位置的原因在于这使得计算过程略显简便。此外，在某些特定的应用场景中，使用第0号元素的值作为哨兵节点具有显著的优势。
可以用优先队列实现栈、队列、随机队列等数据结构。
2.5 应用
对所有可实现Comparable接口的数据类型进行排序：这些数据类型包括事务、指针排序以及不可变键（如String、Integer、Double和File对象）。这种方法采用低成本交换策略，并支持多种排序算法。多键数组可以通过Comparator定义其顺序关系；此外还有一种方法是通过Comparator来实现优先队列的功能。需要注意的是，在这种情况下保持稳定性的前提下（即能够保留重复元素在原有相对位置上的特性），算法才能正常运行。
采用Comparator接口替代Comparable接口有助于将数据类型定义与如何比较的对象加以区分。
选择哪种Sorting算法：这取决于具体的应用场景及实现细节。通常情况下，在大多数编程环境中，默认都会选择一个高效的Sorting方案来满足需求。对于标准库中的Sorting函数而言，默认采用QuickSort作为一种高效的方法来处理数据量较大的情况。QuickSort以其平均时间复杂度最低的特点，在通用Sorting问题中占据主导地位。然而，在某些特殊场景下（例如对稳定性的要求较高），可能会优先考虑MergeSort或InsertionSort等方法。需要注意的是，在某些特殊情况下（如需完成非In-place操作），QuickSort并不适用）。
在Sorting稳定性方面需要注意的是：Stable版本的InsertionSort与MergeSort在实际应用中更为常见。当处理大量数据时（例如大数据集），MergeSort因其稳定的特性成为一种可靠的选择。然而，在大多数编程环境中，默认提供的Sorting函数往往默认采用的是QuickSort这一高效且通用的方法来处理数据量较大的情况。（需要注意的是，在某些特殊情况下（如需完成非In-place操作），QuickSort并不适用）。
归约：开发一种算法用于辅助解决其他问题。中位数属于顺序统计学范畴，在O(n)时间内确定第k大的元素；通常而言基于切分选择法的时间复杂度为线性级别。
l 排序应用一览：商业计算领域, 信息检索技术, 运筹优化理论, 基于事件驱动的仿真模型, 数值分析方法, 组合优化策略。A*算法
l 以下为“答疑”和“练习”中的知识点：
l
第3章 查找
3.1 符号表
l 符号表最主要的目的就是将一个键和一个值联系起来。
l 每一个键只能对应一个唯一的值。（表中不允许出现重复的任意两个不同的键指向同一个位置）。
当插入一个新的键-值对时，在表中如果已经存在相同的键，则会用新输入的该数值覆盖掉原有的数值。
所有所有的关键变量与数据字段都不能为空（null），即它们必须赋有有效的非空的实际有意义的实际可用的真实存在的非零数值或者有意义的具体实体对象引用等合法数据类型标识符或者实体对象引用等合法标识符
l 有序符号表，键为Comparable对象。
在有序列表中进行二分查找时，在一个包含N个键的有序数组中最多需要log₂(N)+1次比较操作。
l 以下为“答疑”和“练习”中的知识点：
l
3.2 二叉查找树
二叉查找树BST是一种二叉树，在每一个节点上都会存储一个可比较类型的键（以及与之相关的附加信息）。对于这棵树上的每一个节点来说，在它左边的所有节点都将具有较小的关键码值，在右边的所有节点都将具有较大的关键码值。
该方法涉及一系列关键操作：look-up, insertion, recursive 和 non-recursive methods, maximum key identification 和 minimum key identification, ceiling function 和 floor function, selection operation, ranking algorithm, deletion of maximum key 和 deletion of minimum key, deletion operation, 以及 range query support.
在基于包含N个随机键的二叉查找树中,其插入操作及查找命中与未命中的平均比较次数均为~2\ln N（约为1.39\lg N）。这意味着,在使用该数据结构进行随机键搜索时,其成本比采用二分法高出约39\%.
l 以下为“答疑”和“练习”中的知识点：
l 二叉树相关检查, 有序性的验证, 等价键的验证, 非递归实现的keys函数, 层次遍历操作（借助队列实现）。
3.3 平衡查找树
我们称其中一棵典型的二叉查找树结构中的节点为2-节点（每个节点包含一个键以及两个子节点），而3-节点则包含两个键以及三个子节点）。
二叉查找树的一种变体（2-3查找树）为空或由二节点和三节点构成。在完美平衡的二叉查找树中，所有缺失分支至根节点的距离应保持一致。
l搜索操作包括以下步骤：首先在二元节点中进行查找；其次在仅包含一个三元节点的树中执行新增键操作；随后将新增键操作扩展到那些其父节点为二元节点的三元树；接着处理那些其父节点同样为三元结构的情况；最后执行根节点分离操作以保持局部平衡性
l 在一棵大小为N的2-3树中，查找和插入操作访问的结点必然不超过lgN个。
红黑二叉查找树是一种基于标准二叉查找树（全部由双节点组成）的方法来表示2-3查找树。其中链接分为两种类型：一种是红链接将两个双节点连接形成三节点；另一种是黑色边作为2-3树中的常规连接方式。
红黑树的关键性质如下：基于红黑树实现的所有符号表都满足操作时间对数级别的要求（除范围查找外的情况，其所需额外空间与其返回键数呈正比关系）。一棵大小为N的红黑树其高度最多不超过2乘以log N。具有大小为N的红黑树中根节点至任一节点的平均深度约为1.001乘以log N。在所有空指针路径上黑色节点的数量保持一致。
l 平衡树是从根开始逐步扩展的，在每一次扩展过程中都会导致根节点发生分裂并且维持整体结构的均衡状态。每一次这样的分裂操作之后，整个树的高度都会增加一层。
由downward path的算法可采用递归或迭代方式处理,而upward path的算法则普遍采用将node=operate(node);作为基础的方案.
由downward path的算法可采用递归或迭代方式处理,而upward path的算法则普遍采用将node=operate(node);作为基础的方案.
左删除算法：该算法旨在确保当前节点并非2-节点。通过将另一子树中的某些节点进行旋转以提供临时空间，在完成删除操作后进行必要的平衡调整。
l 以下为“答疑”和“练习”中的知识点：
仅限于红色左链接存在的场景下实现代码编写能够大幅降低可能出现的问题数量
如果依次将键按升序顺序插入到红黑树中，则其高度持续上升；当依次将键按降序顺序插入到红黑树中时，则其高度先稳步增加一段时间后骤减再逐步恢复这一循环过程。
其中涉及的时间复杂度为O(\log n)。
l
3.4 散列表
哈希表的查找机制：首先通过散列函数将被搜索的关键字映射到数组中的一个索引位置；其次就是解决冲突问题的具体方法（包括拉链法和线性探测法）。
哈希表的查找机制：首先通过散列函数将被搜索的关键字映射到数组中的一个索引位置；其次就是解决冲突问题的具体方法（包括拉链法和线性探测法）。
l 哈希函数与数据类型的属性相关联，在每种数据类型属性下都需要相应的哈希函数实现匹配功能。以社会保险制度为例，在不同保险产品中使用的哈希算法各不相同。
整数散列的主要方法是除留取余法。当键是一个位于0到1之间的浮点数值时,可以通过将其乘以M并进行四舍五入处理后得到一个范围在0至M-1之间的索引值,但这种方法会使得较高位数字对结果的影响更为显著。为了改进这一问题,修正的方法是将键转换为二进制表示后再应用除留取余法。同样地,在Java中使用的hashCode函数也能够处理字符串以及组合键的情况。
l 均匀散列假设：我们的哈希函数具备将所有键均等且独立地分配到0至M-1区间的能力。在一个包含M条链表和N个键的哈希表中（基于均匀散列假设成立的条件），任何一条链表中的键的数量均位于(N/M)常数倍范围内的概率无限趋近于1
l 拉链机制：被用来将每个元素连接到一条对应的链表中；其中每条链表中的节点都存储了对应键值对的信息。
开放地址散列表是一种通过数组空置位置来处理散列表冲突的技术方案。线性探测法作为一种开放地址散列表的具体实现方法，在发生碰撞（即某个键的哈希值已被其他不同键占用时），则依次检查下一个存储位置（即当前索引加1的位置）。通过动态调整数组大小维持负载因子在1/8至1/2区间内，并避免因负载因子达到1而陷入无限探测状态。
散列表的负载因子：α=N/M（其中N代表键的数量而M代表散列表的大小）。在拉链法中，α通常表示每条链表的平均长度，并且这个值一般会大于1；而在线性探测散列表中，则将α定义为已占用存储空间的比例，并且其最大值不会超过1。
Knuth's derivation in 1962 states that in a linear probing hash table with size M and N = αM keys, under the assumption of uniform distribution, when α is approximately 1/2, the number of probes required for a successful search is approximately 3/2, and for an unsuccessful search, it is approximately 5/2.
哈希表并非万能灵药：每一种类型的键都需要搭配一个高质量的散列函数；其性能表现依赖于散列函数的质量；而这种函数的计算可能会较为复杂且开销较大；此外它也无法有效地处理基于顺序的操作
l 以下为“答疑”和“练习”中的知识点：
l 完美散列函数：散列函数得到的每个索引都不相同即没有碰撞。
3.5 应用
l 我应该使用符号表的哪种实现：对于常见的应用程序来说，在散列表和二叉查找树之间做出选择是一个合理的选择方案。相较于二叉查找树而言，在代码复杂度上具有优势的是散列表，并且其平均时间复杂度接近常数级（只要键的数据类型是标准类型的或是能够被我们高效处理并满足均匀性假设）。然而在抽象结构上更为简单的则是二叉查找树本身；其中红黑树作为一种平衡二叉搜索树不仅能够保证最坏情况下的性能表现（即操作的时间复杂度），还支持更多的操作功能（如排序、排名、选择及范围查询等）。基于实践经验而言，在缺乏特殊需求的情况下，默认推荐使用散列表；但在需要考虑其他因素时，则可能需要权衡选择红黑树或其他替代方案。值得注意的是当处理较长的键值时，则建议考虑其他数据结构；此外还需要注意原始数据类型替代Key类型的潜在效益；同时重复键的处理策略也应予以关注；此外Java标准库中的相关实现也值得参考比较
集合实例包括过滤器和白名单与黑名单；涉及的领域有电话黄页、字典、基因组学、编译器、文件系统以及DNS；涵盖的领域包括商业交易、网络搜索以及电影与演员相关的内容；反向索引应用涵盖互联网电影数据库、图书索引以及文件搜索技术。
l 稀疏向量：google的PageRank算法。
未完待续