查找算法简记

一、简单查找（顺序查找）

最基本的查找，相当于遍历，从头到尾一个一个找。

二、二分查找

1、简述
二分查找的输入是一个有序的元素列表。
如果要查找的元素包含在列表中，二分查找返回其位置；
否则返回null。

2、特点
对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。
在 N 个键的有序数组中进行二分查找最多需要（ lgN+1）次比较（无论是否成功）。
向大小为 N 的有序数组中插入一个新的元素在最坏情况下需要访问∼ 2N 次数组，因此向一个空符号表中插入 N 个元素在最坏情况下需要访问∼ N2 次数组。

三、符号表（字典）

1、简述
符号表是一种存储键值对的数据结构，支持两种操作：
插入（put），即将一组新的键值 对存入表中；
查找（get），即根据给定的键得到相应的值。

2、操作与结果
一般来说，在符号表中查找一个键可能得到两种结果。
如果含有该键的结点存在于表中，我们的查找就命中了，然后返回相应的值。
否则查找未命中（并返回 null）

3、目的
符号表最主要的目的就是将一个键和一个值联系起来。
用户能够将一个键值对插入符号表，并在之后能够从符号表的所有键值对中按照键直接找到相对应的值

4、规则
每个键只对应着一个值（表中不允许存在重复的键）；
当用例代码向表中存入的键值对和表中已有的键（及关联的值）冲突时，新的值会替代旧的值
键不能为空， 不允许有空值

四、二叉树

二叉树的内容非常多，先简单记录一些基本概念

1、二叉搜索树
二叉搜索树就是使用每个结点含有两个链接（链表中每个结点只含有一个链接）的二叉查找树来高效地实现符号表。
在二叉查找树中，每个结点还包含了一个键和一个值，键之间也有顺序之分以支持高效的查找。
二叉搜索树是一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。

2、平衡搜索树
理想情况下我们希望能够保持二分查找树的平衡性，这可以稳定提升查找的效率，处于这个目的，二叉树概念下衍生出了2-3树，并进而衍生出了红黑树。

3、2-3树
我们将一棵标准的二叉查找树中的结点称为 2- 结点（含有一个键和两条链接），而现在我们引入 3- 结点，它含有两个键和三条链接。 2- 结点和 3- 结点中的每条链接都对应着其中保存的键所分割产生的一个区间
一棵 2-3 查找树或为一棵空树，或由以下结点组成：
（1） 2- 结点，含有一个键（及其对应的值）和两条链接，左链接指向的 2-3 树中的键都小于该结点，右链接指向的 2-3 树中的键都大于该结点。
（2） 3- 结点，含有两个键（及其对应的值）和三条链接，左链接指向的 2-3 树中的键都小于该结点，中链接指向的 2-3 树中的键都位于该结点的两个键之间，右链接指向的 2-3树中的键都大于该结点。

4、红黑树
红黑二叉查找树背后的基本思想是用标准的二叉查找树（完全由 2- 结点构成）和一些额外的信息（替换３- 结点）来表示 2-3树。我们将树中的链接分为两种类型： 
红链接将两个 2- 结点连接起来构成一个 3- 结点，
黑链接是 2-3 树中的普通链接。
可以理解为将 3- 结点表示为由一条左斜的红色链接（两个 2-结点其中之一是另一个的左子结点）相连的两个 2- 结点

5、二叉树的基本查找操作
在二叉查找树中查找一个键的递归算法：
如果树是空的，则查找未命中；
如果被查找的键和根结点的键相等，查找命中，
否则我们就（递归地）在适当的子树中继续查找。
如果被查找的键较小就选择左子树，较大则选择右子树
 

五、散列表（hashtable 哈希表）

1、概念
散列表可以认为是普通数组概念的推广， 是实现字典操作的一种有效数据结构， 也被称为散列映射、映射、字典和关联数组，是一种包含额外逻辑的数据结构

2、散列函数
散列函数的计算过程会将键转化为数组的索引。
如果我们有一个能够保存M个键值对的数组，那么我们就需要一个能够将任意键转化为该数组范围内的索引（ [0,M-1] 范围内的整数） 的散列函数。
散列函数和键的类型有关。
严格地说， 对于每种类型的键都我们都需要一个与之对应的散列函数。
散列最主要的目的在于均匀地将键散布开来，因此在计算散列后键的顺序信息就丢失了。
散列函数是构造散列表的关键，一般来说，散列函数应该有以下特点：
（1）一致性 同样的输入返回的结果是一致的，同样的，不同的输入返回的结果一般也不同
（2）有效性 散列函数只返回有效结果

3、查找操作
使用散列的查找算法分为两步。
第一步是用散列函数将被查找的键转化为数组的一个索引。
理想情况下，不同的键都能转化为不同的索引值。
非理想情况，需要处理两个或者多个键都会散列到相同的索引值的情况。
散列查找的第二步就是处理这种碰撞冲突的过程。
有两种常用的解决碰撞的方法： 拉链法和线性探测法。

4、拉链法
将大小为 M 的数组中的每个元素指向一条链表，链表中的每个结点都存储了散列值为该元素的索引的键值对。
因为发生冲突的元素都被存储在链表中，这种方法被称为拉链法。

5、线性探测法
实现散列表的另一种方式就是用大小为 M 的数组保存 N 个键值对，其中 M>N。依靠数组中的空位解决碰撞冲突。
这种统称为开放地址散列表。
开放地址散列表中最简单的方法叫做线性探测法
当碰撞发生时（一个键的散列值已经被另一个不同的键占用），我们直接检查散列表中的下一个位置（将索引值加 1）。
这样的线性探测可能会产生三种结果
（1） 命中，该位置的键和被查找的键相同；
（2） 未命中，键为空（该位置没有键）；
（3） 继续查找，该位置的键和被查找的键不同。
我们用散列函数找到键在数组中的索引，检查其中的键和被查找的键是否相同。
如果不同则继续查找（将索引增大，到达数组结尾时折回数组的开头），直到找到该键或者遇到一个空元素。