深入解析数据结构：哈希表（HashTable）的应用与优化

 散列表&＃xff08;Hash table&＃xff0c;也叫哈希表&＃xff09;是一种查找算法&＃xff0c;与链表、树等算法不同的是&＃xff0c;散列表算法在查找时不需要进行一系列和关键字&＃xff08;关键字是数据元素中某个数据项的值&＃xff0c;用以标识一个数据元素&＃xff09;的比较操作。

    散列表算法希望能尽量做到不经过任何比较&＃xff0c;通过一次存取就能得到所查找的数据元素&＃xff0c;因而必须要在数据元素的存储位置和它的关键字&＃xff08;可用key表示&＃xff09;之间建立一个确定的对应关系&＃xff0c;使每个关键字和散列表中一个唯一的存储位置相对应。因此在查找时&＃xff0c;只要根据这个对应关系找到给定关键字在散列表中的位置即可。这种对应关系被称为散列函数(可用h(key)表示)。

    根据设定的散列函数h(key)和处理冲突的方法将一组关键字key映像到一个有限的连续的地址区间上&＃xff0c;并以关键字在地址区间中的像作为数据元素在表中的存储位置&＃xff0c;这种表便被称为散列表&＃xff0c;这一映像过程称为散列&＃xff0c;所得存储位置称为散列地址。

    关键字、散列函数以及散列表的关系如下图所示&＃xff1a;

    1、散列函数

    散列函数是从关键字到地址区间的映像。

    好的散列函数能够使得关键字经过散列后得到一个随机的地址&＃xff0c;以便使一组关键字的散列地址均匀地分布在整个地址区间中&＃xff0c;从而减少冲突。

    常用的构造散列函数的方法有&＃xff1a;

    &＃xff08;1&＃xff09;、直接定址法

    取关键字或关键字的某个线性函数值为散列地址&＃xff0c;即&＃xff1a;

    h(key) &＃61; key   或 h(key) &＃61; a * key &＃43; b

    其中a和b为常数。

    &＃xff08;2&＃xff09;、数字分析法

    &＃xff08;3&＃xff09;、平方取值法

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

    &＃xff08;4&＃xff09;、折叠法

    将关键字分割成位数相同的几部分&＃xff08;最后一部分的位数可以不同&＃xff09;&＃xff0c;然后取这几部分的叠加和&＃xff08;舍去进位&＃xff09;作为散列地址。

    &＃xff08;5&＃xff09;、除留余数法

    取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址&＃xff0c;即&＃xff1a;

    h(key) &＃61; key MOD p    p ≤ m

    &＃xff08;6&＃xff09;、随机数法

    选择一个随机函数&＃xff0c;取关键字的随机函数值为它的散列地址&＃xff0c;即&＃xff1a;

    h(key) &＃61; random(key)

    其中random为随机函数。

    2、处理冲突

    对不同的关键字可能得到同一散列地址&＃xff0c;即key1 ≠ key2&＃xff0c;而h(key1)&＃61; h(key2)&＃xff0c;这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称作同义词。

    在一般情况下&＃xff0c;散列函数是一个压缩映像&＃xff0c;这就不可避免地会产生冲突&＃xff0c;因此&＃xff0c;在创建散列表时不仅要设定一个好的散列函数&＃xff0c;而且还要设定一种处理冲突的方法。

    常用的处理冲突的方法有&＃xff1a;

    &＃xff08;1&＃xff09;、开放定址法

    h_i &＃61;(h(key) &＃43; d_i) MOD m     i &＃61;1,2,…,k(k ≤ m-1)

    其中&＃xff0c;h(key)为散列函数&＃xff0c;m为散列表表长&＃xff0c;d_i为增量序列&＃xff0c;可有下列三种取法&＃xff1a;

    1)、d_i &＃61; 1,2,3,…,m-1&＃xff0c;称线性探测再散列&＃xff1b;

    2&＃xff09;、d_i &＃61; 1²,-1²,2²,-2²,3²,…,±k² (k ≤m/2)&＃xff0c;称二次探测再散列&＃xff1b;

    3&＃xff09;、d_i &＃61; 伪随机数序列&＃xff0c;称伪随机探测再散列。

    &＃xff08;2&＃xff09;、再散列法

    h_i &＃61; rh_i(key)   i &＃61; 1,2,…,k

    rh_i均是不同的散列函数。

    &＃xff08;3&＃xff09;、链地址法

    将所有关键字为同义词的数据元素存储在同一线性链表中。假设某散列函数产生的散列地址在区间[0,m-1]上&＃xff0c;则设立一个指针型向量void *vec[m],其每个分量的初始状态都是空指针。凡散列地址为i的数据元素都插入到头指针为vec[i]的链表中。在链表中的插入位置可以在表头或表尾&＃xff0c;也可以在表的中间&＃xff0c;以保持同义词在同一线性链表中按关键字有序排列。

    &＃xff08;4&＃xff09;、建立一个公共溢出区

    例子以除留余数法和链地址法构造散列表&＃xff0c;共用代码如下&＃xff1a;

#include
#include #define LEN 13struct hash_node {int count;struct hash_node *next;
};static int hash(int num)
{return num % LEN;
}static void collision(struct hash_node *vec[], int elem, struct hash_node *new)
{if (vec[elem] &＃61;&＃61; NULL)vec[elem] &＃61; new;else{new -> next &＃61; vec[elem];vec[elem] &＃61; new;}
}static void ord_num_print(int i)
{if (i &＃61;&＃61; 1)printf("the 1st element: ");else if (i &＃61;&＃61; 2)printf("the 2nd element: ");else if (i &＃61;&＃61; 3)printf("the 3rd element: ");else printf("the %dth element: ", i);
}static void print_hash(struct hash_node *vec[])
{int i;struct hash_node *tmp;for (i &＃61; 0; i count);}while ((tmp &＃61; tmp->next) && tmp !&＃61; NULL);printf("\n");}
}static void create_hash(struct hash_node *vec[], int num)
{FILE *fp;int i, tmp, arr[num];struct hash_node *p;fp &＃61; fopen("./hash", "r");for (i &＃61; 0; i count &＃61; arr[i];p -> next &＃61; NULL;tmp &＃61; hash(arr[i]);collision(vec, tmp, p);}
}

 其中&＃xff0c;hash是散列函数&＃xff0c;collision函数用于处理冲突。

    create_hash函数通过读取./hash文件中的num个关键字来构建一个散列表。例子中hash文件的内容如下&＃xff1a; 

19 14 23 01 68 20 84 27 55 11 10 79

 

    3、元素插入 

void insert_hash_node(struct hash_node *vec[], int data)
{ int tmp; struct hash_node *p &＃61; malloc(sizeof(struct hash_node)); p -> count &＃61; data; p -> next &＃61; NULL; tmp &＃61; hash(data); collision(vec, tmp, p);
}

    4、元素删除 

void delete_hash_node(struct hash_node *vec[], int data)
{ int elem; struct hash_node *p, *tmp; elem &＃61; hash(data); if (vec[elem] &＃61;&＃61; NULL) { fprintf(stderr, "vec[%d] is NULL\n", elem); exit(-2); } else { tmp &＃61; vec[elem]; while (tmp -> count !&＃61; data) { if (tmp -> next &＃61;&＃61; NULL) { fprintf(stderr, "not found %d\n", data); exit(-3); } p &＃61; tmp; tmp &＃61; tmp -> next; } p -> next &＃61; tmp -> next; free(tmp); }
}

    在main函数中&＃xff0c;通过三步来验证上述所列的各种函数&＃xff0c;第一步调用create_hash函数创建一个具有12个关键字的散列表&＃xff08;见下图&＃xff09;&＃xff0c;第二步插入关键字29&＃xff0c;第三步删除关键字1。 

int main(int argc, char *argv[])
{ int i, num; struct hash_node *vec[LEN]; /* num, the number of integers in the ./hash file */ if (argc <2) { fprintf(stderr, "Usage: %s num\n", argv[0]); exit(-1); } for (i &＃61; 0; i }

    执行和输出结果&＃xff1a; 

$ ./hash_list 12

the first times
the 1st element: NULL
the 2nd element: 79 27 1 14
the 3rd element: NULL
the 4th element: 55 68
the 5th element: NULL
the 6th element: NULL
the 7th element: 84 19
the 8th element: 20
the 9th element: NULL
the 10th element: NULL
the 11th element: 10 23
the 12th element: 11
the 13th element: NULLthe second times
the 1st element: NULL
the 2nd element: 79 27 1 14
the 3rd element: NULL
the 4th element: 29 55 68
the 5th element: NULL
the 6th element: NULL
the 7th element: 84 19
the 8th element: 20
the 9th element: NULL
the 10th element: NULL
the 11th element: 10 23
the 12th element: 11
the 13th element: NULLthe third times
the 1st element: NULL
the 2nd element: 79 27 14
the 3rd element: NULL
the 4th element: 29 55 68
the 5th element: NULL
the 6th element: NULL
the 7th element: 84 19
the 8th element: 20
the 9th element: NULL
the 10th element: NULL
the 11th element: 10 23
the 12th element: 11
the 13th element: NULL