哈希表

Hash

哈希表(Hash Table)又称散列表，是一种存储线性表的存储结构。

哈希表的基本思路：

   设要存储的对象个数为n，设置一个长度为m(m >= n)的连续存储单元，以线性表中的每一个对象的关键字ki(0~n-1)为自变量，通过一个称为哈希函数的函数h(ki)，把ki映射为内存单元的地址h(ki)，并把该对象存储在这个内存单元中。把如此构造的线性表存储结构称为哈希表。

哈希表构造的问题：

   对于两个关键字ki和kj，ki != kj（i != j）但是有h(ki) = h(kj)，把这种现象叫做哈希冲突。通常把这种具有不同的关键字却有相同哈希地址的对象叫做“同义词”，同义词的冲突很难避免。

哈希函数构造方法：

   1.直接定址法。

               h(k) = k + c(c >= 0),适用于关键字分布基本连续的情况。

   2.除留余数法。

               h(k) = k mod p(mod为求余运算，p <= m)，最常使用的。

哈希冲突解决方法：

   1.开放定址法

        开放定址法是一类以发生冲突的哈希地址为自变量，通过某种哈希冲突函数得到的

     一个新的空闲的哈希地址的方法。

     (1).线性探查法

               d0 = h(k);

               di = (di-1 + 1) mod m(1 <= i <= m)

     (2).平方探查法

                d0 = h(k);

               di = (d0 + i ^ 2) mod m(1 <= i <= m)

   2.拉链法

       拉链法是把所有的同义词用单链表链接起来的方法。     

基本操作实例：

/*
 *这个函数实现散列的基本操作,使用开放地址法解决哈希冲突
 *（Ｃ） 2010/9/21
 */

#include<stdio.h>

#define Maxsize 100
#define NULLKEY -1
#define DELKEY -2

typedef struct //定义哈希表结构

{
    int     key;
    int    count;
}HashTable;

int SearchHT(HashTable ha[], int p, int k)//在哈希表中查找

{
    int    i = 0, adr;
    adr = k % p;
    while(ha[adr].key != NULLKEY && ha[adr].key != k){
        i++;
        adr = (adr + 1) % p;
    }
    if(ha[adr].key == k)
        return adr;
    else
        return -1;
}

int DeleteHT(HashTable ha[], int p, int k, int number)//删除一个元素

{
    int    adr;
    adr = SearchHT(ha, p, k);
    if(adr != -1){
        ha[adr].key = DELKEY;
        number--;
        return 1;
    }
    else
        return 0;
}

void InsertHT(HashTable ha[], int k, int p)//元素插入

{
    int    i, adr;
    adr = k % p;
    if(ha[adr].key == NULLKEY || ha[adr].key == DELKEY){
        ha[adr].key = k;
        ha[adr].count = 1;
    }
    else{
        i = 1;
        do{
            adr = (adr + 1) % p;
            i++;
        }while(ha[adr].key != NULLKEY && ha[adr].key != DELKEY);
        ha[adr].key = k;
        ha[adr].count = i;
    }
}

void CreateHT(HashTable ha[], int x[], int n, int m, int p)//建立哈希表
{
    int    i;
    for(i = 0;i < m ;i++){
        ha[i].key = NULLKEY;
        ha[i].count = 0;
    }
    for(i = 0;i < n;i++)
        InsertHT(ha, x[i], p);
}

int main(void)
{
    int    i;
    HashTable ha[13];
    int HT[11] = {16, 74, 60, 43, 54, 90, 46, 31, 29, 88, 77};
    CreateHT(ha , HT , 11, 13, 13);//创建Hash表

    for(i = 0;i < 13; i++)
        printf("key:%d\tcount:%d\t\n", ha[i].key, ha[i].count);

    return 0;
}

运行结果：

key:77    count:2    
key:-1    count:0    
key:54    count:1    
key:16    count:1    
key:43    count:1    
key:31    count:1    
key:29    count:4    
key:46    count:1    
key:60    count:1    
key:74    count:1    
key:88    count:1    
key:-1    count:0    
key:90    count:1