免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
› 论坛 › 程序设计 › C/C++ › 写了个哈希表，欢迎批评指正...(经强力测试, 伤得起)
123下一页
最近访问板块 发新帖
查看: 7250 | 回复: 24
打印 上一主题 下一主题

写了个哈希表，欢迎批评指正...(经强力测试, 伤得起) [复制链接]

三月廿七

论坛徽章:
0
跳转到指定楼层
1楼 [收藏(0)] [报告]
发表于 2011-10-29 12:02 |只看该作者 |倒序浏览
本帖最后由 三月廿七 于 2011-10-30 09:06 编辑
  1. #ifndef HASHTABLE_H_
  2. #define HASHTABLE_H_

  4. typedef struct xHashTable* HashTable;

  6. /*
  7. * 哈希函数
  8. */
  9. typedef unsigned int (*hashFunction)(const void* key, int capacity);

  11. /*
  12. * 比较函数
  13. */
  14. typedef int (*compareFunction)(const void* a, const void* b);

  16. /*
  17. * 显示函数
  18. */
  19. typedef void (*showFunction)(const void* key, const void* item);

  21. /*
  22. * 键复制函数
  23. */
  24. typedef void*(*keyCloneFunction)(void* key);

  26. /*
  27. * 项复制函数
  28. */
  29. typedef void*(*itemCloneFunction)(void* item);

  31. /*
  32. * 键释放函数
  33. */
  34. typedef void (*keyDeleteFunction)(void* key);

  36. /*
  37. * 项释放函数
  38. */
  39. typedef void (*itemDeleteFunction)(void* item);

  41. /*
  42. * 构造哈希表
  43. */
  44. HashTable HASHTABLEnew(int max, int number, hashFunction hash,
  45.                        compareFunction compare, showFunction show,
  46.                        keyCloneFunction keyClone, itemCloneFunction itemClone,
  47.                        keyDeleteFunction keyDelete, itemDeleteFunction itemDelete);

  49. /**
  50. * 释放哈希表
  51. */
  52. void HASHTABLEdelete(HashTable hashTable);

  54. /**
  55. * 添加项
  56. */
  57. int HASHTABLEinsert(HashTable hashTable, void* key, void* item);

  59. /**
  60. * 查找项
  61. */
  62. void* HASHTABLEsearch(HashTable hashTable, void* key);

  64. /**
  65. * 删除项
  66. */
  67. int HASHTABLEremove(HashTable hashTable, void* key);

  69. /**
  70. * 重设哈希表大小
  71. */
  72. int HASHTABLEresize(HashTable hashTable, int size);

  74. /**
  75. * 遍历哈希表
  76. */
  77. void HASHTABLEtraverse(HashTable hashTable);

  79. #endif
复制代码
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  4. #include "HashTable.h"

  6. #define TRUE 1

  8. #define FALSE 0

  10. typedef struct xHashTableNode HASHTABLEnode;

  12. typedef HASHTABLEnode* HashTableNode;

  14. struct xHashTableNode
  15. {
  16.     void* key;
  17.     void* item;
  18.     HashTableNode next;
  19. } ;

  21. typedef struct xHashTableChain HASHTABLEchain;

  23. typedef HASHTABLEchain* HashTableChain;

  25. struct xHashTableChain
  26. {
  27.     // 分离链中的第一个链接
  28.     HashTableNode head;

  30.     // 分离链的长度
  31.     int size;
  32. } ;

  34. typedef struct xHashTable HASHTABLE;

  36. struct xHashTable
  37. {
  38.     // 分离链表
  39.     HashTableChain* table;

  41.     // 项的最大个数
  42.     int max;

  44.     // 平均每个链中的项的个数
  45.     int number;

  47.     // 项的个数
  48.     int size;

  50.     // 分离链个数
  51.     int capacity;

  53.     hashFunction hash;
  54.     compareFunction compare;
  55.     showFunction show;
  56.     keyCloneFunction keyClone;
  57.     itemCloneFunction itemClone;
  58.     keyDeleteFunction keyDelete;
  59.     itemDeleteFunction itemDelete;
  60. };

  62. static HashTableNode HASHTABLENODEnew(void* key, void* item, HashTableNode next)
  63. {
  64.     HashTableNode node = malloc(sizeof * node);

  66.     if (node == NULL)
  67.     {
  68.         return NULL;
  69.     }

  71.     node->key = key;
  72.     node->item = item;
  73.     node->next = next;
  74.     return node;
  75. }

  77. static HashTableChain HASHTABLECHAINnew(void)
  78. {
  79.     HashTableChain chain = malloc(sizeof * chain);

  81.     if (chain == NULL)
  82.     {
  83.         return NULL;
  84.     }

  86.     chain->head = NULL;
  87.     chain->size = 0;
  88.     return chain;
  89. }

  91. HashTable HASHTABLEnew(int max, int number, hashFunction hash,
  92.                        compareFunction compare, showFunction show,
  93.                        keyCloneFunction keyClone, itemCloneFunction itemClone,
  94.                        keyDeleteFunction keyDelete, itemDeleteFunction itemDelete)
  95. {
  96.     HashTable hashTable = malloc(sizeof * hashTable);
  97.     int i, c;

  99.     if (hashTable == NULL)
  100.     {
  101.         return NULL;
  102.     }

  104.     c = max / number;
  105.     hashTable->table = malloc(c * sizeof * hashTable->table);

  107.     if (hashTable->table == NULL)
  108.     {
  109.         free(hashTable);
  110.         return NULL;
  111.     }

  113.     for (i = 0; i < c; i++)
  114.     {
  115.         hashTable->table[i] = NULL;
  116.     }

  118.     hashTable->max = max;
  119.     hashTable->number = number;
  120.     hashTable->size = 0;
  121.     hashTable->capacity = c;
  122.     hashTable->show = show;
  123.     hashTable->hash = hash;
  124.     hashTable->compare = compare;
  125.     hashTable->keyClone = keyClone;
  126.     hashTable->itemClone = itemClone;
  127.     hashTable->keyDelete = keyDelete;
  128.     hashTable->itemDelete = itemDelete;
  129.     return hashTable;
  130. }

  132. void HASHTABLEdelete(HashTable hashTable)
  133. {
  134.     int i;
  135.     assert(hashTable);

  137.     for (i = 0; i < hashTable->capacity; i++)
  138.     {
  139.         HashTableNode save, it;

  141.         if (hashTable->table[i] == NULL)
  142.         {
  143.             continue;
  144.         }

  146.         it = hashTable->table[i]->head;

  148.         for (; it != NULL; it = save)
  149.         {
  150.             save = it->next;
  151.             hashTable->keyDelete(it->key);
  152.             hashTable->itemDelete(it->item);
  153.             free(it);
  154.         }

  156.         free(hashTable->table[i]);
  157.     }

  159.     free(hashTable->table);
  160.     free(hashTable);
  161. }

  163. void* HASHTABLEsearch(HashTable hashTable, void* key)
  164. {
  165.     unsigned int h;
  166.     assert(hashTable);
  167.     h = hashTable->hash(key, hashTable->capacity);

  169.     if (hashTable->table[h] != NULL)
  170.     {
  171.         HashTableNode it = hashTable->table[h]->head;

  173.         for (; it != NULL; it = it->next)
  174.         {
  175.             if (hashTable->compare(key, it->key) == 0)
  176.             {
  177.                 return it->item;
  178.             }
  179.         }
  180.     }

  182.     return NULL;
  183. }

  185. int HASHTABLEinsert(HashTable hashTable, void* key, void* item)
  186. {
  187.     unsigned int h;
  188.     void* tempKey, *tempItem;
  189.     HashTableNode tempNode;
  190.     assert(hashTable);
  191.     h = hashTable->hash(key, hashTable->capacity);

  193.     // 不允许重复项
  194.     if (HASHTABLEsearch(hashTable, key) != NULL)
  195.     {
  196.         return FALSE;
  197.     }

  199.     tempKey = hashTable->keyClone(key);
  200.     tempItem = hashTable->itemClone(item);
  201.     tempNode = HASHTABLENODEnew(tempKey, tempItem, NULL);

  203.     if (tempNode == NULL)
  204.     {
  205.         return FALSE;
  206.     }

  208.     if (hashTable->table[h] == NULL)
  209.     {
  210.         hashTable->table[h] = HASHTABLECHAINnew();

  212.         if (hashTable->table[h] == NULL)
  213.         {
  214.             hashTable->keyDelete(tempNode->key);
  215.             hashTable->itemDelete(tempNode->item);
  216.             free(tempNode);
  217.             return FALSE;
  218.         }
  219.     }

  221.     tempNode->next = hashTable->table[h]->head;
  222.     hashTable->table[h]->head = tempNode;
  223.     hashTable->table[h]->size++;
  224.     hashTable->size++;

  226.     if (hashTable->size > hashTable->max / 2)
  227.     {
  228.         if (!HASHTABLEresize(hashTable, hashTable->max * 2))
  229.         {
  230.             return FALSE;
  231.         }
  232.     }

  234.     return TRUE;
  235. }

  237. int HASHTABLEremove(HashTable hashTable, void* key)
  238. {
  239.     unsigned int h;
  240.     HashTableNode save, it;
  241.     assert(hashTable);
  242.     h = hashTable->hash(key, hashTable->capacity);

  244.     if (hashTable->table[h] == NULL)
  245.     {
  246.         return FALSE;
  247.     }

  249.     it = hashTable->table[h]->head;

  251.     if (hashTable->compare(key, it->key) == 0)
  252.     {
  253.         hashTable->table[h]->head = it->next;
  254.         hashTable->keyDelete(it->key);
  255.         hashTable->itemDelete(it->item);
  256.         free(it);

  258.         if (hashTable->table[h]->head == NULL)
  259.         {
  260.             free(hashTable->table[h]);
  261.             hashTable->table[h] = NULL;
  262.         }
  263.         else
  264.         {
  265.             hashTable->table[h]->size--;
  266.         }
  267.     }
  268.     else
  269.     {
  270.         while (it->next != NULL)
  271.         {
  272.             if (hashTable->compare(key, it->next->key) == 0)
  273.             {
  274.                 break;
  275.             }

  277.             it = it->next;
  278.         }

  280.         if (it->next == NULL)
  281.         {
  282.             return FALSE;
  283.         }

  285.         save = it->next;
  286.         it->next = it->next->next;
  287.         hashTable->keyDelete(save->key);
  288.         hashTable->itemDelete(save->item);
  289.         free(save);
  290.         hashTable->table[h]->size--;
  291.     }

  293.     hashTable->size--;
  294.     return TRUE;
  295. }

  297. static TABLEfree(HashTable hashTable)
  298. {
  299.         HashTableNode it, save;
  300.         int i;

  302.         for (i = 0; i < hashTable->capacity; i++)
  303.         {
  304.                 if (hashTable->table[i] == NULL)
  305.                 {
  306.                         continue;
  307.                 }

  309.                 it = hashTable->table[i]->head;

  311.                 for (; it != NULL; it = save)
  312.                 {
  313.                         save = it->next;
  314.                         hashTable->keyDelete(it->key);
  315.                         hashTable->itemDelete(it->item);
  316.                         free(it);
  317.                 }

  319.                 free(hashTable->table[i]);
  320.         }

  322.         free(hashTable->table);
  323. }

  325. int HASHTABLEresize(HashTable hashTable, int size)
  326. {
  327.         HashTableChain* table;
  328.         HashTableNode it;
  329.         void* tempKey, *tempItem;
  330.         HashTableNode tempNode;
  331.         int i, c;
  332.         unsigned int h;
  333.        
  334.         c = size / hashTable->number;
  335.         table = malloc(c * sizeof * table);

  337.         if (table == NULL)
  338.         {
  339.                 return FALSE;
  340.         }

  342.         for (i = 0; i < c; i++)
  343.         {
  344.                 table[i] = NULL;
  345.         }

  347.         for (i = 0; i < hashTable->capacity; i++)
  348.         {
  349.                 if (hashTable->table[i] == NULL)
  350.                 {
  351.                         continue;
  352.                 }

  354.                 for (it = hashTable->table[i]->head; it != NULL; it = it->next)
  355.                 {
  356.                         h = hashTable->hash(it->key, c);

  358.                         if (table[h] == NULL)
  359.                         {
  360.                                 table[h] = HASHTABLECHAINnew();

  362.                                 if (table[h] == NULL)
  363.                                 {
  364.                                         return FALSE;
  365.                                 }
  366.                         }

  368.                         tempKey = hashTable->keyClone(it->key);
  369.                         tempItem = hashTable->itemClone(it->item);
  370.                         tempNode = HASHTABLENODEnew(tempKey, tempItem, NULL);

  372.                         tempNode->next = table[h]->head;
  373.                         table[h]->head = tempNode;
  374.                         table[h]->size++;
  375.                 }
  376.         }

  378.         TABLEfree(hashTable);

  380.         hashTable->table = table;
  381.         hashTable->max = size;
  382.         hashTable->capacity = c;
  383.         return TRUE;
  384. }

  386. void HASHTABLEtraverse(HashTable hashTable)
  387. {
  388.     int i;
  389.     assert(hashTable);

  391.     for (i = 0; i < hashTable->capacity; i++)
  392.     {
  393.         HashTableNode it;

  395.         if (hashTable->table[i] == NULL)
  396.         {
  397.             continue;
  398.         }

  400.         it = hashTable->table[i]->head;

  402.         for (; it != NULL; it = it->next)
  403.         {
  404.             hashTable->show(it->key, it->item);
  405.         }

  407.         printf("\n");
  408.     }
  409. }
复制代码
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include "HashTable.h"

  6. unsigned int STRINGhash(const void* key, int capacity);

  8. int STRINGcompare(const void* a, const void* b);

  10. void STRINGshow(const void* key, const void* item);

  12. void* STRINGkeyClone(void* key);

  14. void* STRINGitemClone(void* item);

  16. void STRINGkeyDelete(void* key);

  18. void STRINGitemDelete(void* item);

  20. int main(void)
  21. {
  22.     HashTable hashTable = HASHTABLEnew(10, 5, STRINGhash,
  23.                                        STRINGcompare, STRINGshow,
  24.                                        STRINGkeyClone, STRINGitemClone,
  25.                                        STRINGkeyDelete, STRINGitemDelete);
  26.     HASHTABLEinsert(hashTable, "BlueGuy0", "920170678");
  27.     HASHTABLEinsert(hashTable, "BlueGuy1", "920170678");
  28.     HASHTABLEinsert(hashTable, "BlueGuy2", "920170678");
  29.     HASHTABLEinsert(hashTable, "BlueGuy3", "920170678");
  30.     HASHTABLEinsert(hashTable, "BlueGuy4", "920170678");
  31.     HASHTABLEinsert(hashTable, "BlueGuy5", "920170678");
  32.     HASHTABLEinsert(hashTable, "BlueGuy6", "920170678");
  33.     HASHTABLEinsert(hashTable, "BlueGuy7", "920170678");
  34.     HASHTABLEinsert(hashTable, "BlueGuy8", "920170678");
  35.     HASHTABLEinsert(hashTable, "BlueGuy9", "920170678");
  36.     HASHTABLEinsert(hashTable, "BlueGuy ", "920170678");
  37.     HASHTABLEtraverse(hashTable);
  38.     HASHTABLEdelete(hashTable);
  39.     getchar();
  40.     return 0;
  41. }

  43. unsigned int STRINGhash(const void* key, int capacity)
  44. {
  45.     unsigned int h = 0, a = 255;
  46.     unsigned char* str = (unsigned char*)key;

  48.     for (; *str ; str++)
  49.     {
  50.         h = (a * h + *str) % capacity;
  51.     }

  53.     return h;
  54. }

  56. int STRINGcompare(const void* a, const void* b)
  57. {
  58.     const char* a1 = (const char*) a;
  59.     const char* a2 = (const char*) b;
  60.     return strcmp(a1, a2);
  61. }

  63. void STRINGshow(const void* key, const void* item)
  64. {
  65.     const char* a1 = (const char*) key;
  66.     const char* a2 = (const char*) item;
  67.     printf("%s: %s\n", a1, a2);
  68. }

  70. void* STRINGkeyClone(void* key)
  71. {
  72.     return key;
  73. }

  75. void* STRINGitemClone(void* item)
  76. {
  77.     return item;
  78. }

  80. void STRINGkeyDelete(void* key)
  81. {
  82. }

  84. void STRINGitemDelete(void* item)
  85. {
  86. }
复制代码
huxk

论坛徽章:
0
2楼 [报告]
发表于 2011-10-29 12:28 |只看该作者
牛逼，随便就写了个哈希表。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
三月廿七

论坛徽章:
0
3楼 [报告]
发表于 2011-10-29 12:29 |只看该作者
本帖最后由 三月廿七 于 2011-10-29 12:34 编辑
牛逼，随便就写了个哈希表。
huxk 发表于 2011-10-29 12:28

是吹的，
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
huxk

论坛徽章:
0
4楼 [报告]
发表于 2011-10-29 12:34 |只看该作者
回复 3# 三月廿七


    这种东东再配个内存管理 比如 内存池就更好了。
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
nketc

论坛徽章:
5
技术图书徽章 日期:2013-11-07 13:21:58技术图书徽章 日期:2013-12-07 10:34:46技术图书徽章 日期:2014-04-23 08:50:31双鱼座 日期:2014-09-16 09:12:34亥猪 日期:2015-01-23 13:37:49
5楼 [报告]
发表于 2011-10-29 13:28 |只看该作者
膜拜，哈希表是啥？这玩意又啥用？
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
mirnshi

论坛徽章:
2
技术图书徽章 日期:2013-09-04 15:21:51酉鸡 日期:2013-11-01 21:20:20
6楼 [报告]
发表于 2011-10-29 13:35 |只看该作者
现在好多系统都带哈希API了，构建一个hash算法，直接用就行了。干嘛总是要自己写呢？
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
三月廿七

论坛徽章:
0
7楼 [报告]
发表于 2011-10-29 14:13 |只看该作者
膜拜，哈希表是啥？这玩意又啥用？
nketc 发表于 2011-10-29 13:28

本来是想让你指点的， 结果被膜拜了, {:3_183:}
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
三月廿七

论坛徽章:
0
8楼 [报告]
发表于 2011-10-29 14:36 |只看该作者
本帖最后由 三月廿七 于 2011-10-29 14:43 编辑
现在好多系统都带哈希API了，构建一个hash算法，直接用就行了。干嘛总是要自己写呢？
mirnshi 发表于 2011-10-29 13:35

代码 和 代码能力 是 积累出来的，没事写几行代码练练动手能力...
说不定哪一天这段代码就会用的上， 也说不定哪一天代码能力会发生质变,
然后由众人鄙视的对象跃升为众人膜拜的偶像...
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
liexusong

论坛徽章:
0
9楼 [报告]
发表于 2011-10-29 15:47 |只看该作者
莫拜
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
davelv

论坛徽章:
0
10楼 [报告]
发表于 2011-10-29 18:06 |只看该作者
哈希函数，我就记得DEK的了，这个好记就是在于没有magic number

  2. unsigned int DEKHash(char* str, unsigned int len)
  3. {
  4.         unsigned int hash = len;
  5.         char* str_end = str+len;

  7.         for( ; str < str_end; str++)
  8.         {
  9.                 hash = ((hash << 5) ^ (hash >> 27)) ^ (*str);
  10.         }
  11.         return hash;
  12. }
复制代码
实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？
123下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号：11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们：huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP