详解散列表算法与其相关的C语言实现攻略
什么是散列表
散列表是一种常见数据结构,也被称作哈希表。它的主要思想是将一个查询的值经过散列函数的处理,然后存储到一个数组中的指定位置。这样,下一次查询这个值时,就可以通过散列函数,直接找到它所对应的位置,从而提升了查询的效率。
散列函数的设计
散列函数的设计是散列表中的重要环节。下面以一个简单的例子,说明散列函数的设计过程。
假设有如下五个数据:
Apple
Banana
Cherry
Durian
Eggplant
我们想要将这些数据存入散列表中。首先我们需要确定散列函数。散列函数通常是将一个键值(这里就是我们的数据)映射到一个存储位置。常见的散列函数设计有以下几种:
直接定址法
直接定址法是将数据的关键字作为散列表的下标。例如,我们可以将 Apple
存入散列表的第 0 个位置,将 Banana
存入散列表的第 1 个位置,以此类推。
int hash_table[5];
hash_table[0] = Apple;
hash_table[1] = Banana;
hash_table[2] = Cherry;
hash_table[3] = Durian;
hash_table[4] = Eggplant;
但是,这种方法有时会导致下标冲突,比如两个数据的关键字相同,也有可能会浪费大量的存储空间。
数字分析法
数字分析法是根据数据中的数字特征来生成散列地址。对于每个数据,我们可以根据它的一些数字特征,生成一个散列地址。
例如,我们可以根据字符串中的 ASCII 码值,来计算它的散列地址。代码如下:
int hash(char* key) {
int sum = 0;
for (int i = 0; i < strlen(key); i++) {
sum += key[i];
}
return sum % 5; // 5 是散列表的大小
}
那么,Apple
的散列地址是 3,Banana
的散列地址是 2,以此类推。
平方取中法
平方取中法是将数据的平方值的某一位作为散列地址。具体流程如下:
- 将数据的平方值取出,比如
Apple
的平方值是0x003d3b
. - 取出平方值的中间值,比如
0xd3
. - 将中间值对散列表的大小取余,得到散列地址。
int hash(char* key) {
int square = pow(atoi(key), 2);
int mid = (square & 0xf0) >> 4;
return mid % 5; // 5 是散列表的大小
}
散列冲突的解决
虽然散列函数的设计可以尽量避免散列冲突,但是这种冲突依然是不可避免的。所以,我们还需要一种方法来解决这个问题。下面介绍两种常见的散列冲突解决方法。
链地址法
链地址法是将冲突的数据存放在同一个链表中。例如,如果 Apple
和 Banana
的散列地址相同,那么我们可以将它们都放在散列表第 2 个位置的链表中。
typedef struct HashNode {
char* key;
int value;
struct HashNode* next;
} HashNode;
HashNode* hash_table[5];
void put(char* key, int value) {
int index = hash(key);
HashNode* node = malloc(sizeof(HashNode));
node->key = key;
node->value = value;
node->next = hash_table[index];
hash_table[index] = node;
}
int get(char* key) {
int index = hash(key);
HashNode* curr = hash_table[index];
while (curr != NULL) {
if (strcmp(curr->key, key) == 0) {
return curr->value;
}
curr = curr->next;
}
return -1;
}
开放地址法
开放地址法是将冲突的数据放在其他未被占用的位置。有几种开放地址法的实现方式,下面介绍其中的线性探测法。
线性探测法是从发生冲突的散列表位置开始,逐个往后查找,直到找到一个空闲的散列表位置为止。
char* hash_table[5];
void put(char* key) {
int index = hash(key);
for (int i = 0; i < 5; i++) {
int j = (index + i) % 5;
if (hash_table[j] == NULL) {
hash_table[j] = key;
return;
}
}
}
int get(char* key) {
int index = hash(key);
for (int i = 0; i < 5; i++) {
int j = (index + i) % 5;
if (hash_table[j] == NULL) {
return -1;
} else if (strcmp(hash_table[j], key) == 0) {
return j;
}
}
return -1;
}
总结
散列表是一种常见的数据结构,可以用于提高查询的效率。设计好的散列函数能够尽量避免冲突,但是冲突依然是不可避免的。我们可以通过链地址法或者开放地址法来解决冲突问题。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:详解散列表算法与其相关的C语言实现 - Python技术站