Tag Archives: 查找

算法技术手册 – 查找 – 散列查找(Hash查找)

对于含有n个元素的集合C,我们先构造一个Hash函数,让n映射到b个桶内,当选择合理时,速度会很快,时间复杂度O(1)。

完美哈希函数:不会产生冲突,是存在的。

对于>=1个值映射到同一个桶的情况下,就会发生碰撞。处理方法:

  • 链表:每个桶拉一个链表,第一遍散列后,在链表中查找是否存在元素。
  • 开放定址:构造双变量散列函数h(u, j)。h(u, 0) = h(u),此时退化为原始散列函数。

开放定址,分两类:

算法技术手册 – 查找 – 二分查找

二分查找,要求集合是有序的,在这个条件基础上,它比顺序查找具有更好的性能。

如果使用伴随数组,只需要struct中有一个key是有序的就行。

需要指出的是,当数组放在磁盘上时,时间复杂度就不再是O(LogN),而取决于磁盘存取的开销。

源代码:
#include <stdio.h>

typedef int TYPE;

int search(TYPE* arr, int n, int t)
{
int low = 0;
int hi[……]

继续阅读