C语言哈希表的实现

今天药忘吃喽~ 2023-06-17 15:59 15阅读 0赞

# 使用C语言实现HashMap #

--------------------

写这个HashMap的最初目的是在单片机上使用，后来就着学习的态度自己就把他完善了一下，HashMap的大小、key的最大长度、value的最大长度都是在头文件中通过宏定义配置。  
完整代码使用到了：

*  链表(该链表移植自Linux内核中的双向链表)，使用方法见：[https://blog.csdn.net/qq153471503/article/details/79180659][https_blog.csdn.net_qq153471503_article_details_79180659]
 *  内存管理(自己实现的内存管理，参考正点原子)

完整代码：[https://github.com/ankun6/HashMap][https_github.com_ankun6_HashMap]

--------------------

## 头文件如下： ##

//
    // Created by AnKun on 2019/12/3.
    //
    
    #ifndef MYHASHMAP_HASHMAP_H
    #define MYHASHMAP_HASHMAP_H
    
    #include <stdlib.h>
    #include <string.h>
    #include <stdint.h>
    #include <stdbool.h>
    #include "malloc.h"
    #include "List.h"
    
    #define hmalloc mem_malloc
    #define hfree mem_free
    #define hmemcpy mem_memcpy
    #define hmemset mem_memset
    #define hrealloc mem_realloc
    
    
    #define KEY_MAX_LEN 16 // key的最大长度
    #define VAL_MAX_LEN 32 // value的最大长度
    
    #pragma pack(4)
    
    typedef struct list_head HashTable;
    
    typedef struct
    { 
        HashTable *items;   // 键值对条目，如果有冲突键值对则挂在链表后
        uint32_t used;      // 使用量
        uint32_t size;      // 总大小
    } HashMap;
    
    typedef struct
    { 
        uint8_t key[KEY_MAX_LEN];
        uint8_t value[VAL_MAX_LEN];
        struct list_head node;
    } Entry;
    
    HashMap *HashMap_Create(uint32_t size);
    void HashMap_Destroy(HashMap *hashMap);
    bool HashMap_Put(HashMap *hashMap, const void *key, const void *value);
    void *HashMap_Get(const HashMap *const hashMap, const void *key);
    void HashMap_Clear(HashMap *hashMap);
    void HashMap_Remove(HashMap *hashMap, const void *key);
    bool HashMap_Exists(const HashMap *const hashMap, const void *key);
    void HashMap_GetKeys(const HashMap *const hashMap, uint8_t **keys, uint32_t *count);
    
    #pragma pack()
    
    #endif //MYHASHMAP_HASHMAP_H

--------------------

## 使用例程： ##

#include <stdio.h>
    #include "HashMap.h"
    
    #define Put(key, value) HashMap_Put(hashMap, key, value)
    #define Get(key) HashMap_Get(hashMap, key)
    #define GetKesy(keys, count) HashMap_GetKeys(hashMap, keys, count)
    #define Remove(key) HashMap_Remove(hashMap, key)
    #define Clear() HashMap_Clear(hashMap)
    #define Exists(key) HashMap_Exists(hashMap, key)
    
    int main()
    { 
    	char pairs[][2][10] = { { "key1", "value1"},
    						   { "key2", "value2"},
    						   { "key3", "value3"}};
        const unsigned int npair = sizeof(pairs) / sizeof(pairs[0]);
    
        // 初始化自建内存池
        mem_init();
    
        // 创建HashMap
        HashMap *hashMap = HashMap_Create(10);
    
        // 加入和获取
        for (int i = 0; i != npair; i++)
        { 
            Put(pairs[i][0], pairs[i][1]);
            printf("[%s] ", Get(pairs[i][0]));
        }
        printf("\r\n");
    
        // 查看内存池信息
    	printf("memory: <preused:%.2f%%> <used:%d> <free:%d> \r\n", mem_perused(), mem_getused(), mem_getfree());
    
        // 获取所有key
        int count = 0;
        uint8_t *keys[10];
        GetKesy(keys, &count);
        for (int j = 0; j < count; ++j)
        { 
            printf("[%s] ", keys[j]);
        }
        printf("\r\n");
    
        // 删除
        Remove("key1");
    
        // 检测是否存在
        bool isExists = Exists("key1");
        printf("%s\r\n", isExists ? "true" : "false");
    
        // 清空
        Clear();
    
        // 销毁HashMap
        HashMap_Destroy(hashMap);
    
        // 查看内存池信息
    	printf("memory: <preused:%.2f%%> <used:%d> <free:%d> \r\n", mem_perused(), mem_getused(), mem_getfree());
    
        return 0;
    }

## 运行效果： ##

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

--------------------

ends…

[https_blog.csdn.net_qq153471503_article_details_79180659]: https://blog.csdn.net/qq153471503/article/details/79180659
[https_github.com_ankun6_HashMap]: https://github.com/ankun6/HashMap
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUzNDcxNTAz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191205163545402.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTUzNDcxNTAz,size_16,color_FFFFFF,t_70