数据结构与算法5 — 哈希表

本文主要是介绍数据结构与算法5 — 哈希表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

尊重作者劳动成果，转载请注明出处，谢谢！

1. hashTable.h

#ifndef hashTable_H
#define hashTable_H

#include <stddef.h>
#include "hash.h"

//哈希表，采用数组加链表（拉链法）的实现方式
typedef struct
{
    HashNode **hashSet; //指针数组，对应每个链表的头指针
    size_t n;           //数组长度，即哈希表里的链表数
    size_t valueSize;   //值的大小（字节）
} HashTable;

#ifdef __cplusplus
extern "C"
{
#endif
    int hashTable_init(HashTable *table, size_t valueSize, size_t n);
    void hashTable_free(HashTable *table);
    void hashTable_clear(HashTable *table);
    int hashTable_insert(HashTable *table, const char *key, const void *value);
    int hashTable_remove(HashTable *table, const char *key);
    int hashTable_set(HashTable *table, const char *key, const void *value);
    void *hashTable_get(HashTable *table, const char *key, void *data);
#ifdef __cplusplus
}
#endif

#endif

2. hashTable.c

#include "hashTable.h"
#include <string.h>
#include <stdlib.h>

//初始化哈希表
int hashTable_init(HashTable *table, size_t valueSize, size_t n)
{
    if (table == NULL || n <= 0)
        return -1;

    memset(table, 0, sizeof(HashTable));
    table->hashSet = (HashNode **)malloc(n * sizeof(HashNode *)); //指针数组，注意元素大小为：sizeof(HashNode *)
    table->valueSize = valueSize;
    table->n = n;
    return 0;
}

//释放哈希表
void hashTable_free(HashTable *table)
{
    if (table == NULL)
        return;

    hashTable_clear(table);
    if (table->hashSet != NULL)
    {
        free(table->hashSet);
        table->hashSet = NULL;
    }
    table->n = 0;
    table->valueSize = 0;
}

//清空哈希表
void hashTable_clear(HashTable *table)
{
    if (table == NULL)
        return;

    size_t i;
    HashNode *node;
    for (i = 0; i < table->n; i++)
    {
        //从头到尾进行删除
        while (table->hashSet[i] != NULL)
        {
            node = table->hashSet[i];
            table->hashSet[i] = node->next;
            hash_freeNode(node); //释放节点内存
        }
    }
}

//插入数据，不管key值是否存在
int hashTable_insert(HashTable *table, const char *key, const void *value)
{
    if (table == NULL || key == NULL)
        return -1;

    HashNode *node = hash_createNode(key, value, table->valueSize);
    if (node == NULL)
        return -1;

    size_t index = hash_getcode(key, table->n); //计算key值对应的索引
    HashNode *header = table->hashSet[index];   //取到对应的链表头指针
    node->next = header;                        //头插法
    table->hashSet[index] = node;
    return 0;
}

//删除数据，重复的key值也将删除
int hashTable_remove(HashTable *table, const char *key)
{
    if (table == NULL || key == NULL)
        return -1;

    size_t index = hash_getcode(key, table->n);      //计算key值对应的索引
    HashNode **ptrHeader = &(table->hashSet[index]); //链表头指针的指针

    while (*ptrHeader != NULL)
    {
        if (strcmp((*ptrHeader)->key, key) == 0)
        {
            HashNode *node = *ptrHeader;     //被删除节点的指针
            *ptrHeader = (*ptrHeader)->next; //指向下一个指针，修改的是ptrHeader指针所指向的内容，这里需要好好理解
            hash_freeNode(node);             //释放被删除节点的内存
        }
        else
        {
            ptrHeader = &(*ptrHeader)->next; //下一个节点的指针
        }
    }

    return 0;
}

//修改或插入数据
int hashTable_set(HashTable *table, const char *key, const void *value)
{
    if (table == NULL || key == NULL)
        return -1;

    size_t index = hash_getcode(key, table->n); //计算key值对应的索引
    HashNode *header = table->hashSet[index];
    while (header != NULL)
    {
        //key值已经存在
        if (strcmp(header->key, key) == 0)
        {
            memcpy(header->value, value, table->valueSize);
            return 0;
        }

        header = header->next; //下一个节点的指针
    }

    //key值不存在，采用头插法插入数据
    HashNode *node = hash_createNode(key, value, table->valueSize);
    if (node == NULL)
        return -1;

    header = table->hashSet[index]; //取到对应的链表
    node->next = header;            //头插法
    table->hashSet[index] = node;
    return 0;
}

//查找数据
void *hashTable_get(HashTable *table, const char *key, void *data)
{
    if (table == NULL || key == NULL)
        return NULL;

    size_t index = hash_getcode(key, table->n); //计算key值对应的索引
    HashNode *header = table->hashSet[index];

    while (header != NULL)
    {
        if (strcmp(header->key, key) == 0)
        {
            if (data != NULL)
                memcpy(data, header->value, table->valueSize);

            return header->value;
        }

        header = header->next;
    }

    return NULL;
}

这篇关于数据结构与算法5 — 哈希表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！