查找 | Andy‘s Blog

搜索是指从元素集合中找到某个特定元素的算法过程。搜索过程通常返回 True 或 False，分别表示元素是否存在。有时，可以修改搜索过程，使其返回目标元素的位置。不过，本节仅考虑元素是否存在。

二分查找

二分查找又称折半查找，它是一种效率较高的查找方法.

原理

从中间元素开始查找, 如果是立即不返回,

如果查找的元素比中间元素大, 则舍弃左边的序列, 在右边的序列中再次用中间元素查找

如果查找的元素比中间元素小, 则舍弃右边的序列, 在左边的序列中再次用中间元素查找

以此类推, 每次查找都压缩一半的查找范围, 直到找到对应值.

实现

二分查找有两种实现方式, 一种为函数递归版和非函数递归版

非递归实现

递归实现

分析

在进行二分搜索时，每一次比较都将待考虑的元素减半。那么，要检查完整个列表，二分查找算法最多要比较多少次呢？假设列表共有 n 个元素，第一次比较后剩下n/2个元素，第 2 次比较后剩下n/4个元素，接下来是n8，然后是16n，依此类推,那么在第i次比较后剩下n/(2**i)个元素.此时有n/(2**i) = 1.由此可得, i = logn.所以, 二分查找的时间复杂度为O(logn).

二分查找通常优于顺序查找，但当 n 较小时，排序引起的额外开销可能并不划算。实际上应该始终考虑，为了提高搜索效率，额外排序是否值得。如果排序一次后能够搜索多次，那么排序的开销不值一提。然而，对于大型列表而言，只排序一次也会有昂贵的计算成本，因此从头进行顺序查找可能是更好的选择.

散列表 (Hash Table)

散列表，又称哈希表，是一种常用于实现关联数组或映射的数据结构，它通过将键映射到值的方式，能够实现快速的数据检索，字典的存储结构也是通过哈希表来实现的。在本节，大样将深入讲解Python中的散列表，包括散列函数、冲突解决方法、散列表的实现和应用场景，并使用代码示例演示散列表的操作。

1、散列函数

散列函数将散列表中的元素与其所属位置对应起来。对散列表中的任一元素，散列函数返回一个0到m-1之间的整数（m为散列表长度）。给定一个元素集合，能将每个元素映射到不同的位置，这种散列函数称作完美散列函数。如果元素已知，并且集合不变，那么构建完美散列函数是可能的。不幸的是，给定任意一个元素集合，没有系统化方法来保证散列函数是完美的。

在这里，我们的目标是创建这样这样一个散列函数：冲突数最少，计算方便方便，元素均匀分布于散列表。

1.1 取余函数

取余函数是常见的散列函数之一，通过将元素除以表的长度，得到的余数作为散列值（h(item) = item%length）。计算出散列值后，即可将元素插入到对应的位置。例如将元素54、26、93、17、77和31构成的集合存储在长度为11的散列表中。

元素	散列值
54	10
26	4
93	5
17	6
77	0
31	9

对应的散列表如下：

元素在散列表中占用的多少可以用载荷因子来表示，记作，为元素个数与散列表长度的比值。上面例子中载荷因子为6/11。

冲突

在上面例子中，只有当每个元素的散列值不同，这个技巧才有用。例如，元素44它的散列值为0 (44%11==0)，而77的散列值也是0，此时散列函数会将这两个元素都将放入0索引位置，这种情况将被称为冲突，也叫碰撞。这种情况会带来问题，我们稍后讲解。

1.2 折叠法

先将元素切成等长的部分，然后将这些部分相加，最后利用取余函数得到散列值。例如元素是电话号码436-555-4601，将两个数字一组进行切分，得到43、65、55、46、01，然后数字相加得到210。假设散列表长度为11，接着用210除以11取余为1.则电话号码的散列值为1，映射到散列表为1的位置。

有些折叠法更为先进，在加总前每隔一个数反转一次。本例中，反转的结果为：43+56+55+64+01=219， 219%11=10

1.3 平方取中法

先将元素取平方，然后取中间的几位数字，最后利用取余函数得到散列值。

元素	平方	平方取中	散列值
54	2916	91	3
26	676	7	7
93	8649	64	9
17	289	8	8
77	5929	92	4
31	961	6	6

1.4 基于字符创建散列函数

如果要将字符串存储在散列表中，可以通过将各字符的Unicode编码值相加，并取余作为散列值。例如将字符串“cat”看作序数值序列，如下所示：

>>>ord(”C”) 99 >>>ord(”a”) 97 >>>ord(”t”) 116

可以将这些序数值想加，并采用取余法得到散列值。

为字符串构建简单的散列表函数

另外对于异序词（包含字符一样，顺序不同，如heart和earth为异序词），散列函数总是得到相同的散列值。为弥补这一点，可以用字符位置作为权重因子来构造散列函数。

你也许能想到多种计算散列值的其他方法。重要的是，散列函数一定要高效，以免它成为存储和搜索过程的负担。如果散列函数过于复杂，计算槽编号的工作量可能比在进行顺序搜索或二分搜索时的更大，这可不是散列的初衷。

2、处理冲突

当两个元素对应的的散列值相等时，即需要将两个元素放在散列表的同一个位置，这种情况称为冲突。此时必须通过一种系统化方法在散列表中放置第二个元素，这个过程称为处理冲突。前文说过，如果散列函数是完美的，冲突就永远不会发生。然而，这个前提往往不成立，因此处理冲突是散列计算的重点。

现在扩展表上例中的元素，得到新的整数集合（ 54, 26, 93, 17, 77, 31, 44, 55, 20）。看平方地址法和链接法是如何处理冲突的。

2.1 开放地址法

从起初的散列值开始，顺序遍历散列表，直到找到一个空位置，用于放置引起冲突的元素。

1)线性探测

采用线性探测的方法就是在散列表中逐个寻找下一个空位置，将冲突的元素放入其中，下图为整数集合（ 54, 26, 93, 17, 77, 31, 44, 55, 20）冲突处理结果。

线性探测的缺点是会使散列表中的元素出现聚集现象。如果一个位置发生太多冲突，则线性探测会填满附近的地址，而这会影响后续插入的元素。为了避免元素聚集，可以扩展线性探测，不再顺序查找而是跳过一些地址。下图为采用“加3”探测策略处理冲突后的元素分布情况。

再散列泛指在发生冲突后寻找另一个槽的过程。采用线性探测时，再散列函数是newhashvalue = rehash(oldhashvalue)，并且 rehash(pos) = (pos + 1)%sizeoftable。“加 3”探测策略的再散列函数可以定义为 rehash(pos) = (pos + 3)%sizeoftable。也就是说，可以将再散列函数定义为 rehash(pos) = (pos + skip)%sizeoftable。注意， “跨步”（ skip）的大小要能保证表中所有的槽最终都被访问到，否则就会浪费槽资源。要保证这一点，常常建议散列表的大小为素数，这就是本例选用 11 的原因。

2)平方探测

是线性探测的一个变体，其中跨步不是一个固定的值，而是一系列完全平方数。如果第一个散列值是h，后续依次为h+1、h+4、h+9、h+16。下图为采用平方探测处理的结果。

2.2 链接法

允许散列表的同一位置上存在多个元素，发生冲突时，元素仍然被插入到其散列值对应的位置。不过，随着同一位置上的元素越来越多，搜索变得越来越困难。链接法的优点是，平均算来，每个位置的元素不多，因此搜索可能效率更高效。

映射抽象数据类型的实现

字典是最有用的 Python 集合之一。字典是存储键–值对的数据类型。键用来查

找关联的值，这个概念常常被称作映射。在这里大样会模拟实现字典。