拉链法解决哈希冲突

拉链法解决哈希冲突

引用

CSDN

1.

https://m.blog.csdn.net/weixin_75188368/article/details/138259781

拉链法（也称为链地址法）是一种解决哈希冲突的经典方法。当多个元素映射到同一个哈希地址时，拉链法通过将这些元素链接成一个单链表来处理冲突。本文将详细介绍拉链法的基本思想，并通过具体的代码实现来展示其工作原理。

1. 基本思想

拉链法的基本思想是：将相同散列地址的记录链成一个单链表。假设我们有m个散列地址，就设置m个单链表。然后用一个数组将这m个单链表的表头指针存储起来，形成一个动态的结构。

例如，有一组关键字为{19,14,23,1,68,20,84,27,55,11,10,79}，散列函数为Hash(key)=key%13。通过这个函数，我们可以发现有些元素是同义词，比如14%13=1, 1%13=1, 27%13=1，因此14、1和27是同义词。

上图有一个缺点，我们最好能用头插法建立哈希表，头插法速度快，时间复杂度O(1)。最多有m个单链表，编号为0-m-1，用一个数组将m个单链表的表头指针存起来。

接下来，我们将依据散列函数来建立哈希表。主要步骤包括设计结构、建立哈希表和查找哈希表。

2. 代码实现

下面是使用C语言实现的拉链法哈希表：

// 定义哈希表节点结构
typedef struct Node {
    int key;
    struct Node* next;
} Node;

// 定义哈希表结构
typedef struct {
    Node* next;
} HashTable;

// 初始化哈希表
void InitHashTable(HashTable* ht, int m) {
    for (int i = 0; i < m; i++) {
        ht[i].next = NULL;
    }
}

// 散列函数
int H(int key) {
    return key % m;
}

// 在哈希表中查找key，找到返回节点地址，失败返回NULL
Node* Search(const HashTable* ht, int key) {
    int hi = H(key); // 计算key的哈希值
    for (Node* p = ht[hi].next; p != NULL; p = p->next) {
        if (p->key == key) {
            return p;
        }
    }
    return NULL;
}

// 将key插入到哈希表ht中，成功返回true，失败返回false
bool Insert(HashTable* ht, int key) {
    int hi = H(key);
    if (Search(ht, key) != NULL) { // key已经存在
        return false;
    }
    // 插入key
    Node* p = (Node*)malloc(sizeof(Node)); // 创建新节点
    assert(p != NULL);
    p->key = key;
    // 头插
    p->next = ht[hi].next;
    ht[hi].next = p;
    return true;
}

// 从头到尾输出ht的所有值
void Show(const HashTable* ht, int m) {
    for (int i = 0; i < m; i++) {
        printf("哈希值为%d的有:", i);
        for (Node* p = ht[i].next; p != NULL; p = p->next) { // 遍历当前哈希值的链表
            printf("%d   ", p->key);
        }
        printf("\n");
    }
}

int main() {
    const int m = 13;
    HashTable ht[m];
    InitHashTable(ht, m);
    int arr[16] = { 3, 5, 7, 1, 2, 9, 28, 25, 6, 11, 10, 15, 17, 23, 34, 19 };
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) { // 利用arr构造哈希表ht
        Insert(ht, arr[i]);
    }
    Show(ht, m);
    Node* p;
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) { // 查找所有的arr
        p = Search(ht, arr[i]);
        p == NULL ? printf("%d没有找到\n", arr[i]) : printf("%d找到了\n", arr[i]);
    }
    printf("\n");
    p = Search(ht, 100);
    p == NULL ? printf("%d没有找到\n", 100) : printf("%d找到了\n", 100);
    return 0;
}

这段代码展示了如何使用拉链法处理哈希冲突。通过定义哈希表节点和哈希表结构，实现了初始化、插入、查找和显示哈希表的功能。代码中使用了头插法来优化插入操作的效率。