散列表查找

散列技术

  散列技术的方法指的是不同于顺序查找、二分查找、二叉排序树及B-树上的查找。它不以关键字的比较为基本操作，采用直接寻址技术。在理想情况下，无须任何比较就可以找到待查关键字，查找的期望时间为O(1)。
  散列技术是记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key). 查找时,根据这个对应关系找到给定值 key的映射f(key). 若查找集合中存在这个记录,则必定在f(key)的位置上。

直接定址法

哈希函数取关键字自身。

数字分析法

分布均匀的，可作为散列地址

平方取中法

取关键字平方后的中间几位为哈希地址。

折叠法

将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。

除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即

设计哈希函数需要考虑的内容

1. 计算公式花费时间
2. 关键字长度
3. 散列表大小
4. 关键字分布情况
5. 记录查找概率

处理散列冲突

开放地址法

开放定址法就是⼀旦发生了冲突,就去寻找下一个空的散列地址.只有散列表⾜够⼤,空的散列地址总能找到,并将记录存⼊，也称为线性探测法。
其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。

再散列函数法

设计二种甚至多种哈希函数

指的是不同的散列函数

链地址法

将所有的关键字为同义词的记录存储在一个单链表中,我们称为这种同义词⼦表. 在散列表中只存储所有同义词⼦表的头指针(头地址)。

代码实现

#define SUCCESS 1
#define UNSUCCESS 0

//定义散列表长为数组的长度
#define HASHSIZE 12
#define NULLKEY -32768

typedef struct
{
    //数据元素存储基址，动态分配数组
    int *elem;
    //当前数据元素个数
    int count;
}HashTable;
int m=0; /* 散列表表长，全局变量 */

//1.初始化散列表
Status InitHashTable(HashTable *H)
{
    int i;
    
    //① 设置H.count初始值; 并且开辟m个空间
    m=HASHSIZE;
    H->count=m;
    H->elem=(int *)malloc(m*sizeof(int));
    
    //② 为H.elem[i] 动态数组中的数据置空(-32768)
    for(i=0;i<m;i++)
        H->elem[i]=NULLKEY;
    
    return OK;
}

//2. 散列函数
int Hash(int key)
{
    //除留余数法
    return key % m;
}

//3. 插入关键字进散列表
void InsertHash(HashTable *H,int key)
{
    
    
    //① 求散列地址
    int addr = Hash(key);
    
    //② 如果不为空，则冲突
    while (H->elem[addr] != NULLKEY)
    {
        //开放定址法的线性探测
        addr = (addr+1) % m;
    }
    
    //③ 直到有空位后插入关键字
    H->elem[addr] = key;
}

//4. 散列表查找关键字
Status SearchHash(HashTable H,int key,int *addr)
{
    //① 求散列地址
    *addr = Hash(key);
    
    //② 如果不为空，则冲突
    while(H.elem[*addr] != key)
    {
        //③ 开放定址法的线性探测
        *addr = (*addr+1) % m;
        
        //④H.elem[*addr] 等于初始值或者循环有回到了原点.则表示关键字不存在;
        if (H.elem[*addr] == NULLKEY || *addr == Hash(key))
            //则说明关键字不存在
            return UNSUCCESS;
    }
    
    return SUCCESS;
}