实现算法(查找)

查找的基本概念

概念

查找
查找表
静态查找表
关键字
平均查找长度

顺序查找和折半查找

顺序查找

优点: 对数据元素的存储没有要求.
缺点: 平均查找长度较长, 效率低.
有序时可以降低查找失败的平均查找长度.

折半查找（二分查找）

def binary_search(arr: list, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

判定树
优点: 速度快.
缺点: 要求线性表具有随机存储的特性, 仅适合顺序存储结构, 不适合于链式存储.

分块查找（索引顺序查找）

块内元素可以无序, 但块之间是有序的.
顺序查找或折半查找所在的块, 然后在块内顺序查找.
若有 n 个元素, 构造成索引顺序查找, 则根据均值不等式, 每块 sqrt(n)个元素最佳.
若块间使用折半查找, 则是分得越小越好.

散列表

散列表的概念

散列函数: 一个把査找表中的关键字映射成该关键字对应的地址的函数, 记为 Hash(key) = Addr
冲突: 散列函数可能会把两个或两个以上的不同关键字映射到同一地址, 需要尽量减少冲突; 另一方面, 冲突总是不可避免的, 需要好好设计处理冲突的方法.
同义词: 发生碰撞的不同关键字称为同义词.
散列表: 根据关键字而直接进行访问的数据结构.

散列函数的构造方法

散列函数的定义域必须包含全部需要存储的关键字,而值域的范围则依赖于散列表的大小或地址范围。
散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中,从而减少冲突的发生。
散列函数应尽量简单,能够在较短的时间内计算出任一关键字对应的散列地址。

直接定址法

直接取某个线性函数值为散列地址, 散列函数为:

H(key)=key 或 H(key)=a*key+b

适用: 关键字分布连续
优点: 计算简单, 不会产生冲突
缺点: 若关键字分布不均匀, 空位较多, 会造成存储空间的浪费

除留余数法

假定散列表长为 m, 取一个不大于 m 但最接近或等于 m 的质数 p, 利用以下公式把关键字转换为散列地址.

H(key) = key%p

关键: 选好 p, 使得每个关键字通过该函数转换后等概率地映射到散射空间上的任一地址 , 从而减少冲突的可能性.

数字分析法

设关键字是 r 进制数(如十进制数), 而 r 个数码在各位上出现的频率不一定相同, 可能在某些位上分布均匀一些, 每种数码出现的机会均等; 而在某些位上分布不均匀, 只有某几种数码经常出现, 此时应选取数码分布较为均匀的若干位作为散列地址。

适用: 已知的关键字集合, 若更换了关键字, 则需要重新构造新的散列函数。

平凡取中法

顾名思义, 这种方法取关键字的平方值的中间几位作为散列地址. 具体取多少位要视实际情况而定。

适用: 关键字的每位取值都不够均匀或均小于散列地址所需的位数.
优点: 散列地址与关键字的每位都有关系, 因此使得散列地址分布比较均匀.

处理冲突的方法

开放定址法

所谓开放定址法, 是指可存放新表项的空闲地址既向它的同义词表项开放, 又向它的非同义词表项开放. 其数学递推公式为:

Hi = (H(key)+di)%m

线性探测法
平凡探测法
再散列法
伪随机序列法

拉链法

显然, 对于不同的关键字可能会通过散列函数映射到同地址, 为了避免非同义词发生冲突, 可以把所有的同义词存储在一个线性链表中, 这个线性链表由其散列地址唯一标识。假设散列地址为的同义词链表的头指针存放在散列表的第 i 个单元中, 因而查找、插入和删除操作主要在同义词链中进行。拉链法适用于经常进行插入和删除的情况.

散列查找性能分析

检测査找表中地址为 Addr 的位置上是否有记录, 若无记录, 返回查找失败; 若有记录, 比较它与 key 的值, 若相等, 则返回查找成功标志, 否则执行步骤 2.
用给定的处理冲突方法计算“下一个散列地址”, 并把 Addr 置为此地址, 转入步骤 1.

虽然散列表在关键字与记录的存储位置之间建立了直接映像, 但由于“冲突”的产生, 使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此, 仍需要以平均查找长度作为衡量散列表的査找效率的度量.

散列表的査找效率取决于三个因素: 散列函数、处理冲突的方法和装填因子.

装填因子. 散列表的装填因子一般记为 z, 定义为一个表的装满程度

a = 表中记录数n/散列表长度m