Chinaunix

标题: 写了个哈希表，欢迎批评指正...(经强力测试, 伤得起) [打印本页]
作者: 三月廿七    时间: 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    时间: 2011-10-29 12:28
牛逼，随便就写了个哈希表。
作者: 三月廿七    时间: 2011-10-29 12:29
本帖最后由 三月廿七 于 2011-10-29 12:34 编辑
牛逼，随便就写了个哈希表。
huxk 发表于 2011-10-29 12:28

是吹的，
作者: huxk    时间: 2011-10-29 12:34
回复 3# 三月廿七


    这种东东再配个内存管理 比如 内存池就更好了。
作者: nketc    时间: 2011-10-29 13:28
膜拜，哈希表是啥？这玩意又啥用？
作者: mirnshi    时间: 2011-10-29 13:35
现在好多系统都带哈希API了，构建一个hash算法，直接用就行了。干嘛总是要自己写呢？
作者: 三月廿七    时间: 2011-10-29 14:13
膜拜，哈希表是啥？这玩意又啥用？
nketc 发表于 2011-10-29 13:28

本来是想让你指点的， 结果被膜拜了, {:3_183:}
作者: 三月廿七    时间: 2011-10-29 14:36
本帖最后由 三月廿七 于 2011-10-29 14:43 编辑
现在好多系统都带哈希API了，构建一个hash算法，直接用就行了。干嘛总是要自己写呢？
mirnshi 发表于 2011-10-29 13:35

代码 和 代码能力 是 积累出来的，没事写几行代码练练动手能力...
说不定哪一天这段代码就会用的上， 也说不定哪一天代码能力会发生质变,
然后由众人鄙视的对象跃升为众人膜拜的偶像...
作者: liexusong    时间: 2011-10-29 15:47
莫拜
作者: davelv    时间: 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. }
复制代码
作者: 三月廿七    时间: 2011-10-29 19:21
本帖最后由 三月廿七 于 2011-10-29 21:01 编辑
哈希函数，我就记得DEK的了，这个好记就是在于没有magic number
davelv 发表于 2011-10-29 18:06


恩， 学习一下，
不是因为你的帖子，我还不知道原先的 hash函数哪写错了，
作者: sudayly    时间: 2011-10-29 23:22
回复 8# 三月廿七


    这个说的非常有道理！！！
作者: davelv    时间: 2011-10-29 23:33
回复 11# 三月廿七
这?说来听听，说不定我也会犯这样的错误。
作者: 三月廿七    时间: 2011-10-29 23:54
本帖最后由 三月廿七 于 2011-10-30 00:34 编辑
回复  三月廿七
这?说来听听，说不定我也会犯这样的错误。
davelv 发表于 2011-10-29 23:33


int hash(HASHTABLEkey key)
{
    int h = 0, a = 127;
        char* str = (char*)key;

    for (; *str ; str++)
    {
        h = (a * h + *str);
    }

    return h;
}

求双字节字符串的哈希值越界了， 忘了向函数传参数，而且返回int也容易越界
，还有一个比较严重的 bug, HASHTABLEresize() 的时候修改hash表无效，改的快要崩溃了. 伤不起

虽然，传了一个指针的指针勉强解决问题，但感觉代码写的多余了，
或者单独写一个删除/添加table的函数，那代码就更多余了， ...
{:3_183:}
作者: nketc    时间: 2011-10-30 00:34
哈希函数还是md5 sha1之类的nx啊
作者: 三月廿七    时间: 2011-10-30 09:09
哈希函数还是md5 sha1之类的nx啊
nketc 发表于 2011-10-30 00:34

比较仰慕md5, 你能具体说说吗？
作者: nketc    时间: 2011-10-30 09:46
回复 16# 三月廿七


    俺了解也不多。他们都是一种消息摘要算法，就是对任意的输入产生一个定长的输出。常常听有人说md5加密其实是错误的，它压根就不是加密算法，不过我们登录计算机的密码一般是md5后保存在计算机上的。
    用过git吧，每一个提交快照git都计算出一个sha1值，来索引这个提交。
    这些消息摘要算法，常用于消息验证，保证消息没有被篡改。

    对于md5，其算法实现一般是知其然，而不知其所以然。公开了算法实现，但是没有公开为什么这样做。老美也很滑头啊。
作者: 三月廿七    时间: 2011-10-30 09:53
回复  三月廿七


    俺了解也不多。他们都是一种消息摘要算法，就是对任意的输入产生一个定长的输出。 ...
nketc 发表于 2011-10-30 09:46


不是说 王小云破解了 md5 吗？
作者: nketc    时间: 2011-10-30 10:03
具体不知道，她应该是找到了一个碰撞吧。即：M1 ！= M2， md5(M1)==md5(M2)
作者: nketc    时间: 2011-10-30 10:05
回复 18# 三月廿七


    不知道具体怎么回事。应该是找到了产生碰撞的方法吧，即： M1 != M2 但 md5(M1)==md5(M2)
作者: davelv    时间: 2011-10-30 16:19
回复 14# 三月廿七
这两点的确是bug。
不过第二点的bug在于你用了四则运算来取得hash，纯位运算的话，int也是可以的。

刚才回复不了，内容丢失，气愤，现简略表达下。
作者: ironze    时间: 2011-10-31 17:33
编译过了么？
作者: ironze    时间: 2011-10-31 17:37
HashTableNode node = malloc(sizeof * node);
作者: shitou254    时间: 2011-10-31 18:00
光贴代码太坑爹，最起码发个代码包，说说编译环境。说说你的冲突怎么解决。 哈希的范围怎么控制的。这个hashtable最大能存放多少。 你用的什么hash算法。 算法名字是啥？
作者: 三月廿七    时间: 2011-10-31 21:07
HashTableNode node = malloc(sizeof * node);
ironze 发表于 2011-10-31 17:37

你编译过了吗，？，

不是说了吗， 经过强力测试， 无内存泄漏...
我见过好几个牛人的代码都是这样写的， 我也这样写了



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2