查找

静态查找表

• 仅做查询/检索（统称查找）操作

静态查找算法比较

ASL：平均查找时间 = （查找成功平均时间+查找失败时间）/ 2

表结构：表内元素的结构，有序表则表示元素有序。

存储结构：表元素存储的结构，顺序存储表示元素地址有序相连，与链式存储相反。

• 二分/折半查找，只适用于顺序存储结构的有序表

动态查找表

• 除查找外，还做插入、删除操作
• 表结构在查找过程中动态生成

二叉排序树和平衡二叉树

二叉树

B树/B+树

上帝保佑不考🙏

哈希表（散列表）

散列即为哈希，只是两种不同的叫法。

哈希函数（散列函数）

哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

装填因子

装填因子=哈希表中当前元素个数/哈希表的总槽位数

如果装填因子为1，再执行插入时，则会产生错误（两个值相撞），称为哈希碰撞。

哈希碰撞

解决方法

一般哈希碰撞有两种解决方法， 拉链法和开放定址法。

• 拉链法

通过在每个哈希槽位使用一个链表（或其他动态数据结构）来存储发生冲突的元素，避免了开放定址法中需要探测其他槽位的问题。

没有槽位限制，可以动态扩展，即使装填因子>1，仍然可以工作。

需要额外存储空间（用于存储链表）

• 开放定址法

1. 线性探测法

   使用线性探测法，一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

2. 平方探测法

   与线性探测法不同，不是一步步往下走，而是按照1，4，9等平方序列往下走。

   避免了线性探测法可能发生的“一次聚集问题”，但是可能会遇到“二次聚集问题”。

   要求哈希表大小m是一个素数或2的n次方

• 双重散列法

双重散列法使用两个不同的哈希函数。在发生冲突时，使用第二个哈希函数计算探测步长，从而减少冲突概率。

有效避免“一次聚集“和“二次聚集”。

需要设计两个合适的哈希函数，每次探测都需要调用两个函数，计算开销较大。