c语言哈希函数

哈希编码是一种将任意长度的输入数据映射到固定长度输出数据的函数，在C语言中，我们可以使用哈希表来实现哈希编码，哈希表是一种数据结构，它允许我们在常数时间内插入、删除和查找元素，哈希表的实现依赖于哈希函数，它将键（key）映射到一个唯一的索引，该索引用于存储或检索与键关联的值（value）。

以下是如何在C语言中使用哈希编码的详细步骤：

1、包含头文件

我们需要包含一些头文件，以便使用哈希表相关的函数和数据结构。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

2、定义哈希函数

接下来，我们需要定义一个哈希函数，它将字符串键映射到一个整数索引，这里我们使用简单的求余法作为哈希函数。

unsigned int hash_function(const char *key) {
    unsigned int hash = 0;
    while (*key) {
        hash = (hash * 31 + *key) % HASH_TABLE_SIZE;
        key++;
    }
    return hash;
}

HASH_TABLE_SIZE是哈希表的大小，通常选择素数以减少冲突。

3、创建哈希表

我们需要创建一个哈希表来存储键值对，这里我们使用链地址法来解决冲突。

typedef struct Node {
    const char *key;
    int value;
    struct Node *next;
} Node;
Node *create_hash_table() {
    Node *table = (Node *)malloc(sizeof(Node) * HASH_TABLE_SIZE);
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        table[i].next = NULL;
    }
    return table;
}

4、插入元素

向哈希表中插入元素时，我们需要计算键的哈希值，然后将元素插入到对应的链表中，如果链表中已存在相同的键，则更新其值。

void insert(Node *table, const char *key, int value) {
    unsigned int index = hash_function(key);
    Node *node = &table[index];
    while (node>next != NULL && strcmp(node>next>key, key) != 0) {
        node = node>next;
    }
    if (node>next == NULL) { // 如果链表中不存在相同的键，则添加新节点
        node>next = (Node *)malloc(sizeof(Node));
        node>next>key = strdup(key);
        node>next>value = value;
        node>next>next = NULL;
    } else { // 如果链表中已存在相同的键，则更新其值
        node>next>value = value;
    }
}

5、查找元素

从哈希表中查找元素时，我们同样需要计算键的哈希值，然后在对应的链表中查找是否存在相同的键，如果找到相同的键，则返回其值；否则返回1。

int find(Node *table, const char *key) {
    unsigned int index = hash_function(key);
    Node *node = &table[index];
    while (node>next != NULL && strcmp(node>next>key, key) != 0) {
        node = node>next;
    }
    if (node>next == NULL) { // 如果链表中不存在相同的键，则返回1
        return 1;
    } else { // 如果链表中已存在相同的键，则返回其值
        return node>next>value;
    }
}

6、删除元素和释放内存

从哈希表中删除元素时，我们需要计算键的哈希值，然后在对应的链表中查找是否存在相同的键，如果找到相同的键，则删除该节点并释放其内存；否则不做任何操作，释放哈希表所占用的内存。

void delete(Node **table, const char *key) {
    unsigned int index = hash_function(key);
    Node *node = &(*table)[index];
    while (node>next != NULL && strcmp(node>next>key, key) != 0) {
        node = node>next;
    }
    if (node>next == NULL) { // 如果链表中不存在相同的键，则不做任何操作
        return;
    } else { // 如果链表中已存在相同的键，则删除该节点并释放其内存，然后更新前一个节点的指针为NULL
        Node *temp = node>next;
        node>next = node>next>next;
        free(temp>key); // 释放键所占用的内存（使用strdup分配的内存）
        free(temp); // 释放节点所占用的内存（使用malloc分配的内存）
    }
}