详解散列表算法与其相关的C语言实现

详解散列表算法与其相关的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，以此类推。

平方取中法

平方取中法是将数据的平方值的某一位作为散列地址。具体流程如下：

1. 将数据的平方值取出，比如 Apple 的平方值是 0x003d3b.
2. 取出平方值的中间值，比如 0xd3.
3. 将中间值对散列表的大小取余，得到散列地址。

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

总结

散列表是一种常见的数据结构，可以用于提高查询的效率。设计好的散列函数能够尽量避免冲突，但是冲突依然是不可避免的。我们可以通过链地址法或者开放地址法来解决冲突问题。