devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

哈希表C语言实现详解_c语言哈希表实现

作者：IT小白 | 2024-04-19 04:08:29

赞

踩

c语言哈希表实现

目录

1、数据结构

2、操作函数声明

3、具体实现

1、数据结构

  1. #define HASH_TABLE_MALLOC(size)    rt_malloc(size);
  2. #define HASH_TABLE_REALLOC(p,size) rt_realloc(p,size);
  3. #define HASH_TABLE_CALLOC(n,size)  rt_calloc(n,size);
  4. #define HASH_TABLE_FREE(p)         rt_free(p);
  5.  
  6. struct hash_table_node;
  7. struct hash_table;
  8.  
  9. /* 哈希函数,根据key计算哈希值 */
  10. typedef int (*hash_fun)(struct hash_table *table, const void *key);
  11. /* 
  12.  *哈希key比较, key_cmp:传入的要比较的key, key_becmp:哈希表中被比较的key
  13.  * hash桶中的元素是从小到大排列的，
  14.  * 返回值 > 0 : key_cmp > key_becmp
  15.  * 返回值 = 0 : key_cmp = key_becmp
  16.  * 返回值 < 0 : key_cmp < key_becmp
  17. */
  18. typedef int (*hash_keycmp)(struct hash_table *table, const void *key_cmp, const void *key_becmp);
  19. /* hash桶中的节点数据删除函数,如果插入节点为动态分配,则需要在该函数中释放节点空间 */
  20. typedef int (*node_value_free)(struct hash_table_node *node);
  21.  
  22. struct hash_table_node
  23. {
  24.     void *key;
  25.     void *value;
  26.     struct hash_table_node *next; /*哈希桶节点下个节点*/
  27. };
  28.  
  29. struct hash_table
  30. {
  31.     int size; /*哈希桶的大小,即数组的大小*/
  32.     int num;  /*各个哈希桶中节点个数的总和*/
  33.     hash_fun hashfun; /*哈希函数*/
  34.     hash_keycmp keycmp; /*哈希key比较*/
  35.     node_value_free valuefree; /*哈希桶节点数据删除*/
  36.     struct hash_table_node **tables; /*哈希桶,其实就是一个数组*/
  37. };
  38.  
  39. /*根据当前结构体元素的地址，获取到结构体首地址*/
  40. //#define OFFSETOF(TYPE,MEMBER) ((unsigned int)&((TYPE *)0)->MEMBER)
  41. //#define container(ptr,type,member) ({\
  42. //  const typeof( ((type *)0)->member) *__mptr = (ptr);\
  43. //  (type *) ((char *)__mptr - OFFSETOF(type,member));})
  44.  
  45. #define OFFSETOF(TYPE,MEMBER) ((unsigned int)&((TYPE *)0)->MEMBER)
  46. #define container(ptr,type,member) ((type *) ((char *)ptr - OFFSETOF(type,member)))

2、操作函数声明

 

  1. extern struct hash_table *hash_table_creat(int size, hash_fun hashfun, hash_keycmp keycmp, node_value_free valuefree);
  2. extern struct hash_table *hash_table_creat_default(int size, node_value_free valuefree);
  3. extern int    hash_table_insert(struct hash_table *hashtable, void *key, void *value);
  4. extern int    hash_table_delete(struct hash_table *hashtable, void *key);
  5. extern int    hash_table_modify(struct hash_table *hashtable, void *key, void *value);
  6. extern void * hash_table_search(struct hash_table *hashtable, void *key);
  7.  
  8. extern void hash_table_sample(void);

3、具体实现

  1. #include "algo_hash_table.h"
  2. /**
  3.  * 默认使用的哈希函数.
  4.  * 
  5.  * @return 哈希值
  6.  */
  7. static int hash_fun_default(struct hash_table *table, const void *key)
  8. {
  9.     unsigned int hash = 0;
  10.     unsigned int seed = 131;
  11.     char *temp = NULL;
  12.     
  13.     temp = (char*)key;
  14.     while(*temp)
  15.     {
  16.         hash = hash * seed + *temp++;
  17.     }
  18.     
  19.     hash &= 0x7FFFFFFF;
  20.     hash %= table->size;
  21.  
  22.     return hash;
  23. }
  24.  
  25. /**
  26.  * 哈希key比较, key_cmp:传入的要比较的key, key_becmp:哈希表中被比较的key
  27.  * 
  28.  * @return > 0 : key_cmp > key_becmp
  29.  * @return = 0 : key_cmp = key_becmp
  30.  * @return < 0 : key_cmp < key_becmp
  31.  * 
  32.  */
  33. static int hash_keycmp_default(struct hash_table *table, const void *key_cmp, const void *key_becmp)
  34. {
  35.     return strcmp(key_cmp, key_becmp);
  36. }
  37.  
  38. /**
  39.  * 动态创建一个哈希表.
  40.  * 
  41.  * @return NULL:创建失败
  42.  *        !NULL:创建成功
  43.  */
  44. struct hash_table *hash_table_creat(int size, hash_fun hashfun, hash_keycmp keycmp, node_value_free valuefree)
  45. {
  46.     struct hash_table *hashtable = NULL;
  47.     struct hash_table_node **tables = NULL;
  48.     int i = 0;
  49.  
  50.     if (size < 0 || hashfun == NULL || keycmp == NULL)
  51.         return NULL;
  52.  
  53.     /*申请哈希表结构空间*/
  54.     hashtable = HASH_TABLE_MALLOC(sizeof(*hashtable));
  55.     if (hashtable == NULL)
  56.         return NULL;
  57.     
  58.     /*申请哈希桶数据空间,实际就是申请size大小的数组空间*/
  59.     tables = (struct hash_table_node**)HASH_TABLE_MALLOC(size * sizeof(tables));
  60.     if (tables == NULL)
  61.         return NULL;
  62.  
  63.     hashtable->num       = 0;
  64.     hashtable->size      = size;
  65.     hashtable->tables    = tables;
  66.     hashtable->hashfun   = hashfun;
  67.     hashtable->keycmp    = keycmp;
  68.     hashtable->valuefree = valuefree;
  69.  
  70.     /*清零哈希桶(数组)空间*/
  71.     for (i = 0; i < size; i++)
  72.     {
  73.         hashtable->tables[i] = NULL;
  74.     }
  75.     
  76.     return hashtable;
  77. }
  78.  
  79. /**
  80.  * 使用默认的函数函数、key比较函数、节点删除函数 动态创建一个哈希表.
  81.  * 
  82.  * @return NULL:创建失败
  83.  *        !NULL:创建成功
  84.  */
  85. struct hash_table *hash_table_creat_default(int size, node_value_free valuefree)
  86. {
  87.     return hash_table_creat(size, hash_fun_default, hash_keycmp_default, valuefree);
  88. }
  89.  
  90. /**
  91.  * 向一个哈希桶插入一个节点,有3种情况:
  92.  * 1、prev==NULL,插入位置是头结点 2、key小于cur->key 3、cur==NULL,链表尾插入
  93.  * 
  94.  * @param hashtable: 散列表
  95.  * @param key: 关键值
  96.  * @param value: 节点数据
  97.  * @param value: 节点数据大小
  98.  * 
  99.  * @return 0:插入成功
  100.  *        -1:哈希表不存在 或 key为空 或 value为空
  101.  *        -2:节点已经存在
  102.  */
  103. int hash_table_insert(struct hash_table *hashtable, void *key, void *value)
  104. {
  105.     struct hash_table_node *prev = NULL;
  106.     struct hash_table_node *cur = NULL;
  107.     struct hash_table_node *new_node = NULL;
  108.     int hvalue = 0;
  109.  
  110.     if (hashtable == NULL || key == NULL || value == NULL)
  111.         return -1;
  112.  
  113.     /*根据key计算出哈希值*/
  114.     hvalue = hashtable->hashfun(hashtable, key);
  115.     cur = hashtable->tables[hvalue];
  116.  
  117.     /*hash桶中的元素是从小到大排列的,查找要插入的位置*/
  118.     while((cur != NULL) && (hashtable->keycmp(hashtable, key, cur->key) > 0))
  119.     {
  120.         prev = cur;
  121.         cur = cur->next;
  122.     }
  123.  
  124.     /*如果key相同,表示节点以及存在,直接返回*/
  125.     if ((cur != NULL) && (hashtable->keycmp(hashtable, key, cur->key) == 0))
  126.         return -2;
  127.  
  128.     /*插入新增节点*/
  129.     new_node = (struct hash_table_node*)HASH_TABLE_MALLOC(sizeof(*new_node));
  130.     if (new_node == NULL)
  131.         return NULL;
  132.  
  133.     new_node->key = key;
  134.     new_node->value = value;
  135.     if (prev == NULL) /*第1种情况*/
  136.     {
  137.         new_node->next = NULL;
  138.         hashtable->tables[hvalue] = new_node;/*这里不能为cur = new_node,因为此时的cur和table[hvalue]都是无效的*/
  139.     }
  140.     else /*第2、3种情况*/
  141.     {
  142.         new_node->next = cur;
  143.         prev->next = new_node;
  144.     }
  145.     
  146.     hashtable->num ++;
  147.  
  148.     return 0;
  149. }
  150.  
  151.  
  152. /**
  153.  * 删除一个节点.
  154.  * 
  155.  * @param hashtable: 散列表
  156.  * @param key: 删除节点关键值
  157.  * 
  158.  * @return 0:删除成功
  159.  *        -1:哈希表不存在 或 key为空
  160.  *        -2:节点不存在
  161.  */
  162. int hash_table_delete(struct hash_table *hashtable, void *key)
  163. {
  164.     struct hash_table_node *prev = NULL;
  165.     struct hash_table_node *cur = NULL;
  166.     int hvalue = 0;
  167.  
  168.     if (hashtable == NULL || key == NULL)
  169.         return -1;
  170.  
  171.     /*根据key计算出哈希值*/
  172.     hvalue = hashtable->hashfun(hashtable, key);
  173.     cur = hashtable->tables[hvalue];
  174.  
  175.     /*hash桶中的元素是从小到大排列的,查找要删除的位置*/
  176.     while((cur != NULL) && (hashtable->keycmp(hashtable, key, cur->key) >= 0))
  177.     {
  178.         if (hashtable->keycmp(hashtable, key, cur->key) == 0)
  179.         {
  180.             if (prev == NULL)/*如果删除的是头结点*/
  181.             {
  182.                 hashtable->tables[hvalue] = cur->next;
  183.             }
  184.             else
  185.             {
  186.                 prev->next = cur->next;
  187.             }
  188.             /*若节点所指向的数据(包括key和value)为动态分配,则需要在这里释放*/
  189.             hashtable->valuefree(cur);
  190.             HASH_TABLE_FREE(cur);
  191.  
  192.             hashtable->num --;
  193.             return 0;
  194.         }
  195.         else
  196.         {
  197.             prev = cur;
  198.             cur = cur->next;
  199.         }
  200.     }
  201.  
  202.     return -2;
  203. }
  204.  
  205. /**
  206.  * 修改一个节点.注意事项:
  207.  * 1、会先释放节点指向的就数据空间(这里如果是realloc更大的数据空间,容易造成指针泄露,且是不知道整个数据结构的大小的) 
  208.  * 2、修改的节点必须为新动态分配的空间
  209.  *
  210.  * @param hashtable: 散列表
  211.  * @param key: 修改节点关键值
  212.  * @param value: 修改节点数据
  213.  * 
  214.  * @return 0:修改成功
  215.  *        -1:哈希表不存在 或 key为空 或value为空
  216.  *        -2:节点不存在
  217.  */
  218. int hash_table_modify(struct hash_table *hashtable, void *key, void *value)
  219. {
  220.     struct hash_table_node *cur = NULL;
  221.     int hvalue = 0;
  222.  
  223.     if (hashtable == NULL || key == NULL || value == NULL)
  224.         return -1;
  225.  
  226.     /*根据key计算出哈希值*/
  227.     hvalue = hashtable->hashfun(hashtable, key);
  228.     cur = hashtable->tables[hvalue];
  229.  
  230.     /*hash桶中的元素是从小到大排列的,查找要修改的位置*/
  231.     while((cur != NULL) && (hashtable->keycmp(hashtable, key, cur->key) >= 0))
  232.     {
  233.         if (hashtable->keycmp(hashtable, key, cur->key) == 0)
  234.         {
  235.             hashtable->valuefree(cur);
  236.             cur->key = key;
  237.             cur->value = value;
  238.             return 0;
  239.         }
  240.         else
  241.         {
  242.             cur = cur->next;
  243.         }
  244.     }
  245.  
  246.     return -2;
  247. }
  248.  
  249. /**
  250.  * 根据key查找节点数据.
  251.  * 
  252.  * @param hashtable: 散列表
  253.  * @param key: 查找节点关键值
  254.  * @param value: 查找节点数据
  255.  * 
  256.  * @return NULL:查找失败
  257.  *        !NULL:查找成功
  258.  */
  259. void * hash_table_search(struct hash_table *hashtable, void *key)
  260. {
  261.     struct hash_table_node *cur = NULL;
  262.     int hvalue = 0;
  263.  
  264.     if (hashtable == NULL || key == NULL)
  265.         return NULL;
  266.  
  267.     /*根据key计算出哈希值*/
  268.     hvalue = hashtable->hashfun(hashtable, key);
  269.     cur = hashtable->tables[hvalue];
  270.  
  271.     /*hash桶中的元素是从小到大排列的,查找要查找的位置*/
  272.     while((cur != NULL) && (hashtable->keycmp(hashtable, key, cur->key) >= 0))
  273.     {
  274.         if (hashtable->keycmp(hashtable, key, cur->key) == 0)
  275.         {
  276.             return cur->value;
  277.         }
  278.         else
  279.         {
  280.             cur = cur->next;
  281.         }
  282.     }
  283.  
  284.     return NULL;
  285. }
  286.  
  287.  
  288. /*******************************************************************************************
  289.  *                                          使用示例
  290.  *******************************************************************************************/
  291. struct test_node
  292. {
  293.     char key[10];
  294.     char value[10];
  295. };
  296.  
  297. int node_value_free_sample(struct hash_table_node *node)
  298. {
  299.     struct test_node *node_temp = NULL;
  300.  
  301.     /*根据key在test_node结构体中的偏移地址,找到散列表节点实际指向的结构体首地址*/
  302.     node_temp = container(node->key, struct test_node, key);
  303.     /*如果节点所指向数据空间为动态申请的则需要释放*/
  304.     HASH_TABLE_FREE(node_temp);
  305.     
  306.     return 0;
  307. }
  308.  
  309. struct hash_table *hash_table_test;
  310. char table_node_read[5][10];
  311.  
  312. void hash_table_sample(void)
  313. {
  314.     int i = 0;
  315.     struct test_node *node_temp = NULL;
  316.     char rd_key[10] = {10}, del_key[10] = {0};
  317.     char *temp = NULL;
  318.     
  319.     hash_table_test = hash_table_creat_default(5, node_value_free_sample);
  320.     
  321.     /*插入 -- 查询*/
  322.     for (i=0; i<5; i++)
  323.     {
  324.         node_temp = HASH_TABLE_MALLOC(sizeof(*node_temp));
  325.         memset(node_temp, 0, sizeof(*node_temp));
  326.         sprintf(node_temp->key, "AAA%d", i);
  327.         sprintf(node_temp->value, "%d", i+10);
  328.         hash_table_insert(hash_table_test, node_temp->key, node_temp->value);
  329.     }
  330.     for (i=0; i<5; i++)
  331.     {
  332.         sprintf(rd_key, "AAA%d", i);
  333.         temp = hash_table_search(hash_table_test, rd_key);
  334.         memcpy(table_node_read[i], temp, 10);
  335.     }
  336.     
  337.     /*修改 -- 查询*/
  338.     for (i=0; i<5; i++)
  339.     {
  340.         node_temp = HASH_TABLE_MALLOC(sizeof(*node_temp));
  341.         memset(node_temp, 0, sizeof(*node_temp));
  342.         sprintf(node_temp->key, "AAA%d", i);
  343.         sprintf(node_temp->value, "%d", i+20);
  344.         hash_table_modify(hash_table_test, node_temp->key, node_temp->value);
  345.     }
  346.     for (i=0; i<5; i++)
  347.     {
  348.         sprintf(rd_key, "AAA%d", i);
  349.         temp = hash_table_search(hash_table_test, rd_key);
  350.         memcpy(table_node_read[i], temp, 10);
  351.     }
  352.     
  353.     /*删除 -- 查询*/
  354.     for (i=0; i<3; i++)
  355.     {
  356.         sprintf(del_key, "AAA%d", i);
  357.         hash_table_delete(hash_table_test, del_key);
  358.     }
  359.     for (i=0; i<5; i++)
  360.     {
  361.         temp = NULL;
  362.         memset(table_node_read[i], 0, 10);
  363.         sprintf(rd_key, "AAA%d", i);
  364.         temp = hash_table_search(hash_table_test, rd_key);
  365.         if (temp != NULL)
  366.         {
  367.             memcpy(table_node_read[i], temp, 10);
  368.         }
  369.     }
  370. }

 

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/449855
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号