C/C++编程：C实现hashtable

电玩女神 2022-12-26 09:13 171阅读 0赞

# 过程 #

## 初始化一个哈希表 ##

*  申请空间
 *  初始化hash表的属性

#include <errno.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <stddef.h>
    
    
    /* hash table结构体： 用于描述整个hash表的属性 */
    struct DEBUG_HTABLE {
        
        int     size;			/* hash表的空间大小*/
        int     init_size;		/* 初始化hash表的空间大小 */
        int     used;			/*已经使用的hash表个数 */
        DEBUG_HTABLE_INFO **data;		/* entries array, auto-resized */
        DEBUG_HASH_FN  hash_fn;		/* hash function */
    };
    
    
    
    /* 哈希表中每一个哈希项的存储信息类型：用于描述hash表最小空间里面存储的东西的属性 ； 这是一个链表，用来解决hash冲突问题*/
    typedef struct DEBUG_HTABLE_INFO {
        
        char   *key;			/* key */
        char   *value;			/* value */
        struct DEBUG_HTABLE_INFO *next;	/* 下一个entry的地址 */
        struct DEBUG_HTABLE_INFO *prev;	/* 上一个entry的地址  */
    } DEBUG_HTABLE_INFO;
    
    /**
     * 哈希函数类型定义
     * @param buffer 需要被哈希的字符串
     * @param len s 的长度
     */
    typedef unsigned (*DEBUG_HASH_FN)(const void *buffer, size_t len);
    
    
    
    /* debug_htable_size -分配并初始化一个hash table */
    static int debug_htable_size(DEBUG_HTABLE *table, unsigned size){
        
        
    }
    
    /* __def_hash_fn - hash a string */
    static unsigned __def_hash_fn(const void *buffer, size_t len){
        
        
    }
    
    
    /* debug_htable_create - 创建并初始化一个hash表*/
    DEBUG_HTABLE *debug_htable_create(int size){
        
        DEBUG_HTABLE *table;
        int	ret;
        
        table = (DEBUG_HTABLE *) calloc(1, sizeof(DEBUG_HTABLE));
        if(table == NULL)
            return (NULL);
        
        
        table->init_size = size;
        
        ret = debug_htable_size(table, size < 13 ? 13 : size);
        if(ret < 0) {
        
            free(table);
            return(NULL);
        }
    
        table->hash_fn = __def_hash_fn;
        
        return (table);
    }
    
    
    
    int main(){
        
    
    
    }

（1） 分配并初始化一个hash表

/* debug_htable_size -分配并初始化一个hash table */
    static int debug_htable_size(DEBUG_HTABLE *table, unsigned size){
        
        DEBUG_HTABLE_INFO **h;
    
        // HashTable会尽量使用素数、奇数作为容量的大小。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀
        size |= 1;   // 找出与size最近的素数
    
        // 使用malloc分配的内存空间在虚拟地址空间上是连续的
        table->data = h = (DEBUG_HTABLE_INFO **) malloc(size * sizeof(DEBUG_HTABLE_INFO *));
        if(table->data == NULL)
            return(-1);
    
        table->size = size;
        table->used = 0;
    
    
        while (size-- > 0)
            *h++ = 0;
    
    
        return(0);
    }

内存变化如下所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]

另外一种写法：

/* debug_htable_size -分配并初始化一个hash table */
    static int debug_htable_size(DEBUG_HTABLE *table, unsigned size){
        
        size |= 1;   // 找出与size最近的素数
    
        
        table->data  = (DEBUG_HTABLE_INFO **) calloc(size , sizeof(DEBUG_HTABLE_INFO *));
        if(table->data == NULL)
            return(-1);
    
        table->size = size;
        table->used = 0;
        
        return(0);
    }

（2） hash函数实现

static unsigned __def_hash_fn(const void *buffer, size_t len)
    {
        
        unsigned long h = 0;
        unsigned long g;
        const unsigned char* s = (const unsigned char *) buffer;
    
        /*
         * From the "Dragon" book by Aho, Sethi and Ullman.
         */
        while (len-- > 0) {
        
            h = (h << 4) + *s++;
            if ((g = (h & 0xf0000000)) != 0) {
        
                h ^= (g >> 24);
                h ^= g;
            }
        }
    
        return (unsigned) h;
    }

散列查找，主要是将key进行hash计算得出一个大整数，然后与数组长度进行取余，这样一个比较大的域空间就只会映射到数组的下标范围，利用数组索引块的特征，用空间换时间的思路，使得查找的速度快于线性查找， hash函数的作用就是根据key求出对应值

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3]

## 往hash表中添加新的项 ##

我们知道，我们这里使用了一个连续的内存空间（相当于数组，下面简称数组）来存储项，如果我们想要往hash表中添加数据：

*  第一步，求出应该存放位置的索引
 *  第二步，往索引位置插入条目

那么问题来了，当“第一步，求出应该存放位置的索引”，求出来的索引超出范围了怎么办？

*  解决：数组自增长

当“第二步，往索引位置插入条目”， 这个索引已经有了项（**hash冲突**）怎么办？

*  我们定义了，在数组中的每一项都是一个链表  
    ![在这里插入图片描述][20201204105306479.png]  
    也就是说，我们的hash table长这个样

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4]

如果链表里面已经有了这个key（**hash冲突**）怎么办？两种方法：

*  发现key相同就直接退出，相当于插入了
 *  发现key相同，用新的value代替原来老的value，然后退出

这里我们采用第一种解决方案

/* debug_htable_grow - extend existing table */
    static int debug_htable_grow(DEBUG_HTABLE *table){
        
        int ret;
    
        return ret;
    }
    static void debug_htable_link(DEBUG_HTABLE *_table, DEBUG_HTABLE_INFO * _element, unsigned _n){
        
        
    }
    /* debug_htable_enter - enter (key, value) pair */
    #define	STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0))
    DEBUG_HTABLE_INFO *debug_htable_enter(DEBUG_HTABLE *table, const char *key, char *value){
        
        unsigned           n;
        DEBUG_HTABLE_INFO  *ht;
        int                ret;
    
        // 空间自增长
        if (table->used >= table->size) {
        
            ret = debug_htable_grow(table);
            if(ret < 0) {
        
                return(NULL);
            }
        }
    
        // 1. 根据key获取hash值
        n = table->hash_fn(key, strlen(key));
        
        // 2. 根据hash值映射到哈希数组: 拿到哈希值之后，我们要将这个值映射到数组的某一个空间，也就是进行数组寻址。如果数组的长度为len，那么index = xxhash(key) % len。
        // 2.1 数组寻址
        n = n % table->size;
    
        // 2.1 链表寻址: 是否hash冲突， 如果存在就是当前key已经插入了，如果不存在，当ht移动到这个链表的最末尾的那个内存
        for(ht = table->data[n]; ht; ht = ht->next){
        
            if (STREQ(key, ht->key)){
        
                return (ht);
            }
        }
    
        //3. 将value插入到数组位置
        //3.1 申请空间(并且将这个空间原来存放的空间清空)用来存储项
        ht = (DEBUG_HTABLE   _INFO *) malloc(sizeof(DEBUG_HTABLE_INFO));  // ht原来存储着null，现在存储一个新分配的地址（如果分配不成功就直接返回，如果成功就存储项）
        if (ht == NULL) {
        
            return(NULL);
        }
    
        ht->key = strdup(key); //将key拷贝的申请空间的key处 (如果key为null会出现严重的段错误)
        if (ht->key == NULL) {
        
            free(ht);   // 将原来申请的空间释放掉
            return(NULL);
        }
    
        ht->value = value;
    
        //3.2 开始插入
        debug_htable_link(table, ht, n);
        return ht;
    }

（1）我们先来看怎么插入：假设当前已经知道了应该插入的索引n，申请的项空间已经准备好了，而且没有hash冲突问题（链表头插）

static void debug_htable_link(DEBUG_HTABLE *_table, DEBUG_HTABLE_INFO * _element, unsigned _n){
        
        DEBUG_HTABLE_INFO **_h = _table->data + _n;
        _element->prev = 0;
    
        if ((_element->next = *_h) != 0){
        
            (*_h)->prev = _element;
        }
        *_h = _element;
        _table->used++;
    }

*  如果索引n处指向的空间为null时，也就是说，当前  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 5]  
    插入过程如下  
    ![在这里插入图片描述][20201204133330707.png]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 6]
 *  索引n处执行的空间不为null。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 9]  
另外一种写法

#define debug_htable_link(_table, _element, _n) { \
    	DEBUG_HTABLE_INFO **_h = _table->data + _n; \
    	_element->prev = 0; \
    	if ((_element->next = *_h) != 0) \
    		(*_h)->prev = _element; \
    	*_h = _element; \
    	_table->used++; \
    }

(2) 解决空间不足的问题，三步

*  第一步：申请原来2倍大的空间
 *  第二步：将原来空间的值重新映射到新的空间
 *  第三步：将原来空间释放掉

// 空间增长
    static int debug_htable_grow(DEBUG_HTABLE *table){
        
        int ret;
        unsigned old_size = table->size;
        DEBUG_HTABLE_INFO **h0 = table->data;
        DEBUG_HTABLE_INFO *ht;
        DEBUG_HTABLE_INFO *next;
        unsigned n;
        DEBUG_HTABLE_INFO **old_entries = h0;
        
        // 第一步：申请原来2倍大的空间
        ret = debug_htable_size(table, 2 * old_size);
        if (ret < 0)
            return(-1);
    
        //第二步：将原来空间的值重新映射到新的空间
        while (old_size-- > 0) {
        
            for (ht = *h0++; ht; ht = next) {
        
                next = ht->next;
                n = table->hash_fn(ht->key, strlen(ht->key)) % table->size;
                debug_htable_link(table, ht, n);
            }
        }
        
        // 第三步：将原来空间释放掉
        free(old_entries);
        
        return ret;
    }

## 根据key哈希查找 ##

往hash表中插入元素之后，就可以直接根据key算出索引位置，然后查找出当初插入的索引值了。

*  第一步：根据哈希函数算出key对应的索引n（n % size不可能超出索引）
 *  第二步：循环n地址的链表，比对key，如果找到了就返回相应value；如果没有找到就返回null

#define	STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0))
    // 查找对应的value
    char *debug_htable_find(DEBUG_HTABLE *table, const char *key){
        
        DEBUG_HTABLE_INFO *ht;
        unsigned  n;
    
        if (table == NULL || key == NULL)
            return (NULL);
        
        // 1. 根据哈希函数算出key对应的索引n
        n = table->hash_fn(key, strlen(key));
        n = n % table->size;
    
        // 2. 循环n地址的链表，比对key，如果找到了就返回相应value
        for(ht = table->data[n]; ht ; ht = ht->next){
        
            if (STREQ(key, ht->key)){
        
                return (ht->value);
            }
        }
    
        return (NULL);
    }
    
    // 查找对应的项地址
    DEBUG_HTABLE_INFO *debug_htable_locate(DEBUG_HTABLE *table, const char *key)
    {
        
        DEBUG_HTABLE_INFO *ht;
        unsigned  n;
    
        if(table == NULL || key == NULL)
            return (NULL);
    
        n = table->hash_fn(key, strlen(key));
        n = n % table->size;
    
        for (ht = table->data[n]; ht; ht = ht->next) {
        
            if (STREQ(key, ht->key)) {
        
                return (ht);
            }
        }
    
        return (NULL);
    }

## 删除key对应的项 ##

既然有插入查找，就一定有删除。 当`table`和`key`均不为空时删除

*  第一步：找到key对应的索引n
 *  第二步：计算出n对应的地址，循环这个地方的链表，比对key，如果找得到，删除这个key对应的项目（相当于删除双向链表中的某一项）
    
     *  处理前后指针
        
         *  如果当前项的prev不为null，`ht.prev.next = ht.next`
         *  如果当前项的prev为null，说明是头指针，那么只需要`*h=ht.next`
         *  如果当前项的next不为null，`ht.next.prev = ht.prev`
     *  处理当前空间
        
         *  释放`ht.key`的空间
         *  如果`ht.value`需要释放，那么释放
         *  释放`ht`的空间

/* debug_htable_delete - delete one entry */
    int debug_htable_delete(DEBUG_HTABLE *table, const char *key, void (*free_fn) (char *)){
        
        if (table && key) {
        
            DEBUG_HTABLE_INFO *ht;
            unsigned          n;
            DEBUG_HTABLE_INFO **h;
            
            // 计算key对应的索引n;
            n = table->hash_fn(key, strlen(key));
            n = n % table->size;
            
            // 计算出n对应的地址
            h = table->data + n;
            // 循环链表，查找key
            for(ht = *h; ht; ht = ht->next){
        
                if (STREQ(ht->key, key)){
        
                    // 处理链表
                    if (ht->next){
        
                        ht->next->prev = ht->prev;
                    }
                    if (ht->prev){
        
                        ht->prev->next = ht->next;
                    }else{
        
                        *h = ht->next;
                    }
                    table->used--;
                    
                    // 处理当前空间
                    free(ht->key);
                    if(free_fn && ht->value){
        
                        (*free_fn)(ht->value);
                    }
                    free(ht);
                    return (0);
                }
            }
        }
        return(-1);
    }

## 销毁哈希表 ##

当不需要hash表，我们必须把申请到的空间（table不为null）还回去

*  声请到的链表空间都指向null（把申请到的项空间都释放调用），声请到的存储链表的空间都指向null（把申请到的表指向的数据空间释放掉），把申请到的这个表地址空间也释放掉

void debug_htable_free(DEBUG_HTABLE *table, void (*free_fn) (char *))
    {
        
        if (table) {
        
            unsigned i;
            DEBUG_HTABLE_INFO *ht;
            DEBUG_HTABLE_INFO *next;
            DEBUG_HTABLE_INFO **h;
    
            i = table->size;
            h = table->data;
    
            while (i-- > 0) {
        
                for (ht = *h++; ht; ht = next) {
        
                    next = ht->next;
                    free(ht->key);
                    if (free_fn && ht->value)
                        (*free_fn) (ht->value);
                    free(ht);
                }
            }
            free(table->data);
            table->data = 0;
            free(table);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 10]

## 重置hash表 ##

重置hash表和销毁hash表的唯一区别在于：在声请到的链表空间都指向null（把申请到的项空间都释放调用），声请到的存储链表的空间都指向null（把申请到的表指向的数据空间释放掉）之后，我们并不把table空间释放掉，而是重新给table分配并初始化一个未使用的空间

int debug_htable_reset(DEBUG_HTABLE *table, void (*free_fn) (char *))
    {
        
        if (table) {
        
            unsigned i;
            DEBUG_HTABLE_INFO *ht;
            DEBUG_HTABLE_INFO *next;
            DEBUG_HTABLE_INFO **h;
            int ret;
    
            i = table->size;
            h = table->data;
    
            while (i-- > 0) {
        
                for (ht = *h++; ht; ht = next) {
        
                    next = ht->next;
                    free(ht->key);
                    if (free_fn && ht->value)
                        (*free_fn) (ht->value);
                    free(ht);
                }
            }
            free(table->data);
            table->data = 0;
            
            ret = debug_htable_size(table, table->init_size < 13 ? 13 : table->init_size);
            return (ret);
        }
    
        return (-1);
    }

## other ##

void debug_htable_walk(DEBUG_HTABLE *table, void (*action)(DEBUG_HTABLE_INFO *, char *), char *ptr)
    {
        
        if (table) {
        
            unsigned i = table->size;
            DEBUG_HTABLE_INFO **h = table->data;
            DEBUG_HTABLE_INFO *ht;
    
            while (i-- > 0)
                for (ht = *h++; ht; ht = ht->next)
                    (*action) (ht, ptr);
        }
    }
    
    DEBUG_HTABLE_INFO **debug_htable_list(const DEBUG_HTABLE *table)
    {
        
        DEBUG_HTABLE_INFO **list;
        DEBUG_HTABLE_INFO *member;
        int     count = 0;
        int     i;
    
        if (table != 0) {
        
            list = (DEBUG_HTABLE_INFO **) malloc(sizeof(*list) * (table->used + 1));
            for (i = 0; i < table->size; i++)
                for (member = table->data[i]; member != 0; member = member->next)
                    list[count++] = member;
        } else {
        
            list = (DEBUG_HTABLE_INFO **) malloc(sizeof(*list));
        }
        list[count] = 0;
        return (list);
    }

# 总结 #

1.  cmakelist.txt

cmake_minimum_required(VERSION 3.16)
    project(c)
    
    set(CMAKE_C_STANDARD 11)
    
    add_executable(c main.cpp htable.cpp)

1.  htable.c

#include <stdlib.h>
    #include <string.h>
    #include <stddef.h>
    #include "htable.h"
    
    
    /**
     * 哈希函数类型定义
     * @param buffer 需要被哈希的字符串
     * @param len s 的长度
     */
    typedef unsigned (*DEBUG_HASH_FN)(const void *buffer, size_t len);
    
    /* Structure of one hash table. */
    struct DEBUG_HTABLE {
        
        int     size;			/* length of entries array */
        int     init_size;		/* length of initial entryies array */
        int     used;			/* number of entries in table */
        DEBUG_HTABLE_INFO **data;		/* entries array, auto-resized */
        DEBUG_HASH_FN  hash_fn;		/* hash function */
    };
    
    
    
    /* debug_htable_size -分配并初始化一个hash table */
    static int debug_htable_size(DEBUG_HTABLE *table, unsigned size){
        
        DEBUG_HTABLE_INFO **h;
    
        // HashTable会尽量使用素数、奇数作为容量的大小。当哈希表的大小为素数时，简单的取模哈希的结果会更加均匀
        size |= 1;   // 找出与size最近的素数
    
        // 使用malloc分配的内存空间在虚拟地址空间上是连续的
        table->data = h = (DEBUG_HTABLE_INFO **) malloc(size * sizeof(DEBUG_HTABLE_INFO *));
        if(table->data == NULL)
            return(-1);
    
        table->size = size;
        table->used = 0;
    
    
        while (size-- > 0)
            *h++ = 0;
    
    
        return(0);
    }
    /* __def_hash_fn - hash a string */
    static unsigned __def_hash_fn(const void *buffer, size_t len)
    {
        
        unsigned long h = 0;
        unsigned long g;
        const unsigned char* s = (const unsigned char *) buffer;
    
        /*
         * From the "Dragon" book by Aho, Sethi and Ullman.
         */
        while (len-- > 0) {
        
            h = (h << 4) + *s++;
            if ((g = (h & 0xf0000000)) != 0) {
        
                h ^= (g >> 24);
                h ^= g;
            }
        }
    
        return (unsigned) h;
    }
    
    
    /* debug_htable_create - create initial hash table */
    DEBUG_HTABLE *debug_htable_create(int size){
        
        DEBUG_HTABLE *table;
        int	ret;
    
        table = (DEBUG_HTABLE *) calloc(1, sizeof(DEBUG_HTABLE));
        if(table == NULL)
            return (NULL);
    
        table->init_size = size;
    
        ret = debug_htable_size(table, size < 13 ? 13 : size);
        if(ret < 0) {
        
            free(table);
            return(NULL);
        }
    
        table->hash_fn = __def_hash_fn;
    
        return (table);
    }
    
    /* debug_htable_link - insert element into table */
    #define debug_htable_link(_table, _element, _n) { \
    	DEBUG_HTABLE_INFO **_h = _table->data + _n; \
    	_element->prev = 0; \
    	if ((_element->next = *_h) != 0) \
    		(*_h)->prev = _element; \
    	*_h = _element; \
    	_table->used++; \
    }
    /* debug_htable_grow - extend existing table */
    static int debug_htable_grow(DEBUG_HTABLE *table){
        
        int ret;
        unsigned old_size = table->size;
        DEBUG_HTABLE_INFO **h0 = table->data;
        DEBUG_HTABLE_INFO *ht;
        DEBUG_HTABLE_INFO *next;
        unsigned n;
        DEBUG_HTABLE_INFO **old_entries = h0;
    
        // 第一步：申请原来2倍大的空间
        ret = debug_htable_size(table, 2 * old_size);
        if (ret < 0)
            return(-1);
    
        //第二步：将原来空间的值重新映射到新的空间
        while (old_size-- > 0) {
        
            for (ht = *h0++; ht; ht = next) {
        
                next = ht->next;
                n = table->hash_fn(ht->key, strlen(ht->key)) % table->size;
                debug_htable_link(table, ht, n);
            }
        }
    
        // 第三步：将原来空间释放掉
        free(old_entries);
    
        return ret;
    }
    #define	STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0))
    char *debug_htable_find(DEBUG_HTABLE *table, const char *key){
        
        DEBUG_HTABLE_INFO *ht;
        unsigned  n;
    
        if (table == NULL || key == NULL)
            return (NULL);
    
        // 1. 根据哈希函数算出key对应的索引n
        n = table->hash_fn(key, strlen(key));
        n = n % table->size;
    
        // 2. 循环n地址的链表，比对key，如果找到了就返回相应value
        for(ht = table->data[n]; ht ; ht = ht->next){
        
            if (STREQ(key, ht->key)){
        
                return (ht->value);
            }
        }
    
        return (NULL);
    }
    /* debug_htable_locate - lookup entry */
    DEBUG_HTABLE_INFO *debug_htable_locate(DEBUG_HTABLE *table, const char *key)
    {
        
        DEBUG_HTABLE_INFO *ht;
        unsigned  n;
    
        if(table == NULL || key == NULL)
            return (NULL);
    
        n = table->hash_fn(key, strlen(key));
        n = n % table->size;
    
        for (ht = table->data[n]; ht; ht = ht->next) {
        
            if (STREQ(key, ht->key)) {
        
                return (ht);
            }
        }
    
        return (NULL);
    }
    
    /* debug_htable_enter - enter (key, value) pair */
    DEBUG_HTABLE_INFO *debug_htable_enter(DEBUG_HTABLE *table, const char *key, char *value){
        
        unsigned           n;
        DEBUG_HTABLE_INFO  *ht;
        int                ret;
    
        // 空间自增长
        if (table->used >= table->size) {
        
            ret = debug_htable_grow(table);
            if(ret < 0) {
        
                return(NULL);
            }
        }
    
        // 1. 根据key获取hash值
        n = table->hash_fn(key, strlen(key));
    
        // 2. 根据hash值映射到哈希数组: 拿到哈希值之后，我们要将这个值映射到数组的某一个空间，也就是进行数组寻址。如果数组的长度为len，那么index = xxhash(key) % len。
        // 2.1 数组寻址
        n = n % table->size;
    
        // 2.1 链表寻址: 是否hash冲突
        for(ht = table->data[n]; ht; ht = ht->next){
        
            if (STREQ(key, ht->key)){
        
                return (ht);
            }
        }
    
        //3. 将value插入到数组位置
        //3.1 申请空间(并且将这个空间原来存放的空间清空)用来存储项
        ht = (DEBUG_HTABLE_INFO *) malloc(sizeof(DEBUG_HTABLE_INFO));
        if (ht == NULL) {
        
            return(NULL);
        }
    
        ht->key = strdup(key); //将key拷贝的申请空间的key处 (如果key为null会出现严重的段错误)
        if (ht->key == NULL) {
        
            free(ht);   // 将原来申请的空间释放掉
            return(NULL);
        }
    
        ht->value = value;
    
        //3.2 开始插入
        debug_htable_link(table, ht, n);
        return ht;
    }
    
    /* debug_htable_delete - delete one entry */
    int debug_htable_delete(DEBUG_HTABLE *table, const char *key, void (*free_fn) (char *)){
        
        if (table && key) {
        
            DEBUG_HTABLE_INFO *ht;
            unsigned          n;
            DEBUG_HTABLE_INFO **h;
    
            // 计算key对应的索引n;
            n = table->hash_fn(key, strlen(key));
            n = n % table->size;
    
            // 计算出n对应的地址
            h = table->data + n;
            // 循环链表，查找key
            for(ht = *h; ht; ht = ht->next){
        
                if (STREQ(ht->key, key)){
        
                    // 处理链表
                    if (ht->next){
        
                        ht->next->prev = ht->prev;
                    }
                    if (ht->prev){
        
                        ht->prev->next = ht->next;
                    }else{
        
                        *h = ht->next;
                    }
                    table->used--;
    
                    // 处理当前空间
                    free(ht->key);
                    if(free_fn && ht->value){
        
                        (*free_fn)(ht->value);
                    }
                    free(ht);
                    return (0);
                }
            }
        }
        return(-1);
    }
    
    /* debug_htable_free - destroy hash table */
    void debug_htable_free(DEBUG_HTABLE *table, void (*free_fn) (char *))
    {
        
        if (table) {
        
            unsigned i;
            DEBUG_HTABLE_INFO *ht;
            DEBUG_HTABLE_INFO *next;
            DEBUG_HTABLE_INFO **h;
    
            i = table->size;
            h = table->data;
    
            while (i-- > 0) {
        
                for (ht = *h++; ht; ht = next) {
        
                    next = ht->next;
                    free(ht->key);
                    if (free_fn && ht->value)
                        (*free_fn) (ht->value);
                    free(ht);
                }
            }
            free(table->data);
            table->data = 0;
            free(table);
        }
    }
    int debug_htable_reset(DEBUG_HTABLE *table, void (*free_fn) (char *))
    {
        
        if (table) {
        
            unsigned i;
            DEBUG_HTABLE_INFO *ht;
            DEBUG_HTABLE_INFO *next;
            DEBUG_HTABLE_INFO **h;
            int ret;
    
            i = table->size;
            h = table->data;
    
            while (i-- > 0) {
        
                for (ht = *h++; ht; ht = next) {
        
                    next = ht->next;
                    free(ht->key);
                    if (free_fn && ht->value)
                        (*free_fn) (ht->value);
                    free(ht);
                }
            }
            free(table->data);
            table->data = 0;
    
            ret = debug_htable_size(table, table->init_size < 13 ? 13 : table->init_size);
            return (ret);
        }
    
        return (-1);
    }
    
    /* debug_htable_walk - iterate over hash table */
    void debug_htable_walk(DEBUG_HTABLE *table, void (*action)(DEBUG_HTABLE_INFO *, char *), char *ptr)
    {
        
        if (table) {
        
            unsigned i = table->size;
            DEBUG_HTABLE_INFO **h = table->data;
            DEBUG_HTABLE_INFO *ht;
    
            while (i-- > 0)
                for (ht = *h++; ht; ht = ht->next)
                    (*action) (ht, ptr);
        }
    }
    
    DEBUG_HTABLE_INFO **debug_htable_list(const DEBUG_HTABLE *table)
    {
        
        DEBUG_HTABLE_INFO **list;
        DEBUG_HTABLE_INFO *member;
        int     count = 0;
        int     i;
    
        if (table != 0) {
        
            list = (DEBUG_HTABLE_INFO **) malloc(sizeof(*list) * (table->used + 1));
            for (i = 0; i < table->size; i++)
                for (member = table->data[i]; member != 0; member = member->next)
                    list[count++] = member;
        } else {
        
            list = (DEBUG_HTABLE_INFO **) malloc(sizeof(*list));
        }
        list[count] = 0;
        return (list);
    }

1.  htable.h

#pragma once
    #include <stddef.h>
    
    /**
     * 哈希函数类型定义
     * @param buffer 需要被哈希的字符串
     * @param len s 的长度
     */
    typedef unsigned (*DEBUG_HASH_FN)(const void *buffer, size_t len);
    
    /**
     * 哈希表对象结构句柄, 该类型定义在 htable.c 中是为了保护内部成员变量
     */
    typedef struct DEBUG_HTABLE	DEBUG_HTABLE;
    
    /* 哈希表中每一个哈希项的存储信息类型 */
    typedef struct DEBUG_HTABLE_INFO {
        
        char   *key;			/* lookup key */
        char   *value;			/* associated value */
        struct DEBUG_HTABLE_INFO *next;	/* colliding entry */
        struct DEBUG_HTABLE_INFO *prev;	/* colliding entry */
    } DEBUG_HTABLE_INFO;
    
    /**
     * 建立哈希表
     * @param size 哈希表长度
     * @return 所建哈希表的头指针或为空(这时表示出了严重的错误, 主要是内存分配问题)
     */
    DEBUG_HTABLE *debug_htable_create(int size);
    
    /**
     * 往哈希表里添加新的项
     * @param table 哈希表指针
     * @param key 键, 在函数内部会复制此 key 键
     * @param value 用户自己的特定数据项(可以由类型硬转化而来, 但是此数据项必须不能堆栈变量)
     * @return 所分配的哈希表项的指针, == NULL: 表示内部分分配内存出错, 为严重的错误
     */
    DEBUG_HTABLE_INFO *debug_htable_enter(DEBUG_HTABLE *table, const char *key, char *value);
    
    /**
     * 由所给的 key 键查寻某一特定哈希项
     * @param table 哈希表指针
     * @param key 键
     * @return 不为空指针: 表示查到了对应于 key 键的哈希项
     *         为空: 表示未查到对应于 key 键的哈希项
     */
    DEBUG_HTABLE_INFO *debug_htable_locate(DEBUG_HTABLE *table, const char *key);
    
    /**
     * 由所给的 key 键查寻用户的数据项
     * @param table 哈希表指针
     * @param key 键
     * @return 不为空: 表示查到了对应于 key 键的数据项, 用户可以根据用户自己的数据类型进行转换
     *         为空: 表示未查到对应于 key 键的数据项
     */
    char *debug_htable_find(DEBUG_HTABLE *table, const char *key);
    
    /**
     * 功能:		根据所给的 key 键删除某一哈希项
     * @param table 哈希表指针
     * @param key 键
     * @param free_fn 如果该函数指针不为空并且找到了对应于 key 键的数据项, 则先调用用户
     *        所提供的析构函数做一些清尾工作, 然后再释放该哈希项
     * @return 0: 成功;  -1: 未找到该 key 键
     */
    int debug_htable_delete(DEBUG_HTABLE *table, const char *key, void (*free_fn) (char *));
    
    /**
     * 释放整个哈希表
     * @param table 哈希表指针
     * @param free_fn 如果该指针不为空则对哈希表中的每一项哈希项先用该函数做清尾工作, 然后再释放
     */
    void debug_htable_free(DEBUG_HTABLE *table, void (*free_fn) (char *));
    
    /**
     * 重置哈希表, 该函数会释放哈希表中的所有内容项, 并重新初始化
     * @param table 哈希表指针
     * @param free_fn 如果该指针不为空则对哈希表中的每一项哈希项先用该函数做清尾工作, 然后再释放
     * @return 是否重置成功. 0: OK; < 0: error.
     */
    int debug_htable_reset(DEBUG_HTABLE *table, void (*free_fn) (char *));
    
    /**
     * 对哈希表中的每一项哈希项进行处理
     * @param table 哈希表指针
     * @param walk_fn 处理每一项哈希项的函数指针, 不能为空
     * @param arg 用户自己类型的数据
     */
    void debug_htable_walk(DEBUG_HTABLE *table, void (*walk_fn) (DEBUG_HTABLE_INFO *, char *), char *arg);
    
    /**
     * 将哈希表里的所有项组合成一个链表
     * @param table 哈希表
     * @return 不为空: 链表指针; 为空: 表示该哈希表里没有哈希项
     */
    DEBUG_HTABLE_INFO **debug_htable_list(const DEBUG_HTABLE *table);

1.  main.c

#include "htable.h"
    #include <stdio.h>
    
    int main(){
        
        auto table = debug_htable_create(5);
        debug_htable_enter(table, "key", "value");
        printf("%s", debug_htable_find(table, "key") );
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20221120/7226d256ca624edeaa5f0d227a2b269a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: /images/20221120/a16ed540a8764eb19ed5e9d2fff8934e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]: /images/20221120/f4f930e53e1e4cf3b8d662b2fa01f421.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3]: /images/20221120/472e4da8747540529e5f17c98d4a40ab.png
[20201204105306479.png]: /images/20221120/b930c39de9bb4c30841e9ce397b1022d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4]: /images/20221120/ea30547fc3d2428bbd47fd71ff641bdd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 5]: /images/20221120/fd6ecfb12b334837ae81dc6951be34fd.png
[20201204133330707.png]: /images/20221120/0cceac9590744d5db37ae77da0928cfd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 6]: /images/20221120/1cf4451b6d914102b2bafc91287198f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 7]: /images/20221120/5356bfe383674603b415b6db0dbaa9bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 8]: /images/20221120/ba477ebd2cd74bba83057a677094700b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 9]: /images/20221120/2370b8bca2254c0aa56756bceb9bc29b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 10]: /images/20221120/c476cb1b9dd54a38af2eadaa9087a648.png