C语言哈希表详解

一、什么是哈希表

哈希表是一种根据关键码值(Key Value)直接进行访问的数据结构。通俗的说，哈希表就是把一个关键码值(Key Value)通过哈希函数转换为一个索引，该索引指向在表中对应的记录。哈希函数可以将任意长度的输入映射为较小的固定长度的输出。一般情况下，哈希表的查询和插入操作的时间复杂度为 O(1)，在某些特殊情况下，时间复杂度为 O(n)。

二、哈希表的实现

哈希表的实现主要包括哈希函数和哈希冲突处理两部分。

1. 哈希函数

哈希函数是将关键码值映射到哈希表中的位置的函数。

int hash_func(char *key)
{
    unsigned long hash = 5381;
    int c;
    while ((c = *key++))
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    return hash % HASH_SIZE;
}

hash_func() 函数采用了比较常用的“乘法散列法”，可以将字符串转换为哈希表中的位置。

2. 哈希冲突处理

哈希冲突指的是两个关键字经过哈希函数映射到了同一个位置的情况。

常见的哈希冲突处理方法有“链式解决法”和“开放定址法”。

链式解决法

链式解决法通过链表将哈希表中相同位置的多个元素串连在一起。

typedef struct NODE
{
    char *key;
    char *val;
    struct NODE *next;
} NODE;

NODE *hash_table[HASH_SIZE];

void put(char *key, char *val)
{
    int pos = hash_func(key);
    NODE *head = hash_table[pos];
    NODE *p = head;

    while (p)
    {
        if (strcmp(p->key, key) == 0)
        {
            p->val = val;
            return;
        }
        p = p->next;
    }

    NODE *new_node = (NODE*)malloc(sizeof(NODE));
    new_node->key = key;
    new_node->val = val;
    new_node->next = NULL;

    if (head == NULL)
        hash_table[pos] = new_node;
    else
    {
        p = head;
        while (p->next)
            p = p->next;
        p->next = new_node;
    }
}

char *get(char *key)
{
    int pos = hash_func(key);
    NODE *p = hash_table[pos];
    while (p)
    {
        if (strcmp(p->key, key) == 0)
            return p->val;
        p = p->next;
    }
    return NULL;
}

开放定址法

开放定址法是指当哈希冲突发生时，通过向前/后寻找空闲位置来解决冲突的方法。

char *hash_table[HASH_SIZE];

void put(char *key, char *val)
{
    int pos = hash_func(key);
    
    while (hash_table[pos] != NULL && strcmp(hash_table[pos], key) != 0)
    {
        pos = (pos + 1) % HASH_SIZE;
    }

    hash_table[pos] = val;
}

char *get(char *key)
{
    int pos = hash_func(key);
    
    while (hash_table[pos] != NULL && strcmp(hash_table[pos], key) != 0)
    {
        pos = (pos + 1) % HASH_SIZE;
    }

    return hash_table[pos];
}

三、哈希表的应用

哈希表广泛应用于数据存储、索引，如：数据库中的索引、编译器中的符号表、DNS解析中的缓存等。

四、总结

哈希表是一种基于哈希函数实现的数据结构，主要包括哈希函数和哈希冲突处理两部分，通过链式解决法和开放定址法来处理哈希冲突。哈希表具有查询和插入操作的时间复杂度为 O(1) 的优点，广泛应用于数据存储、索引等方面。