散列表查找

散列技术是记录存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key).查找时,根据这个对应关系找到给定值key的映射f(key),若查找集合中存在这个记录,则必定在f(key)的位置上.

• 适合简单，均匀的数据
• 不适合大范围查找

直接定值法

根据一定的线性公式对要存储的数据进行映射,比如映射关系:f(k) = a*key + b(a、b为常数)

数字分析法

对于一组数字,选择不易重复的数字作为散列的地址,如手机号的后四位

平方取中法

对于一组数字平方后取所得数据的中间几位数字作为散列地址

折叠法

将关键字从左到右分割成为数相等几部分,然后将这几部分叠加求和,并按散列表长取后几位作为散列地址

折叠法

除留余数法

将要存储的数字除以一个数,求得余数即为散列地址,公式为:f(key) = key mod p (p<=m)
容易导致散列冲突(散列是一种哈希)

随机数法

f(key) = random(key)

处理散列冲突方法

开放定址法

就是一旦发生了冲突,就去寻找下一个空的散列地址,只有散列表足够大,空的散列地址总能找到,并将记录存入

开放定址法公式

公式并非唯一,这里只是一种思路！

再散列函数

再散列函数

当一个函数的结果地址冲突时,使用另一个函数来求地址

链地址法

公共溢出法

如果散列表分部不均匀,会浪费空间资源

代码实现

int main(int argc, const char * argv[]) {
    int arr[HASHSIZE]={12,67,56,16,25,37,22,29,15,47,48,34};
    int i,p,key,result;
    HashTable H;
    
    //1.初始化散列表
    InitHashTable(&H);
    
    //2.向散列表中插入数据
    for(i=0;i<m;i++)
        InsertHash(&H,arr[i]);
    
    //3.在散列表查找key=39
    key=39;
    result=SearchHash(H,key,&p);
    if (result)
        printf("查找 %d 的地址为：%d \n",key,p);
    else
        printf("查找 %d 失败。\n",key);
    
    //4.将数组中的key,打印出所有在散列表的存储地址
    for(i=0;i<m;i++)
    {
        key=arr[i];
        SearchHash(H,key,&p);
        printf("查找 %d 的地址为：%d \n",key,p);
    }

    return 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;
}