glib中hash table

10340阅读　3评论2013-04-20　Bean_lee
分类：C/C++

     Glib是一个C语言编写的库，它本身是Gnome的一个部分，后来Glib剥离出来，它为Gnome提供了一些操作字符串和常用数据结构的工具函数。这些好的工具函数既然可以提供给gnome，使用，自然也可以提供给我们使用。（靠，这逻辑，怎么这么像 和尚摸的，我自然也摸的，晕死啊）。最近看到我们老大用了Glib的hash表，在工期紧急的情况下解决了一个功能扩展的问题，所以我也就动了玩玩Glib的心思。
   Glib是个好东西，它提供了好多常用的数据结构：双向链表，单链表，hashtable ，平衡二叉树，N叉树等等。如果你花点时间熟悉开放出来的API，可以直接用在你自己的程序中，减少自己写这些基础数据结构的effort。当然了这个拿来主义的理念和我自己的理念不太一致，我不喜欢黑盒子的东西，如果我奉行拿来主义的话中，那我会选择用python。不喜欢归不喜欢，也不影响我爱心大泛滥学下glib。
   我们看下Glib的hash表怎么使用，首先给个简单的例子。
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <glib.h>
  4. #include <time.h>
  5. #include <assert.h>


  8. #define TIMES 20
  9. static void free_data(gpointer hash_data)
  10. {
  11.     g_free(hash_data);
  12.     hash_data = NULL;
  13. }

  15. void print_key_value(gpointer key, gpointer value ,gpointer user_data)
  16. {
  17.     printf("%s -------------------->%s\n",(char*)key,(char*)value);
  18. }

  20. int hash_test_1()
  21. {
  22.     GHashTable* name_score = NULL;
  23.     int ret = 0;
  24.     name_score = g_hash_table_new(g_str_hash,g_str_equal);
  25.     if(name_score == NULL)
  26.     {
  27.         fprintf(stderr, "create hash table failed\n");
  28.         return -1;
  29.     }

  31.     g_hash_table_insert(name_score,"Bean","77");
  32.     g_hash_table_insert(name_score,"Ted","79");
  33.     g_hash_table_insert(name_score,"Lucy","87");
  34.     g_hash_table_insert(name_score,"Jim","90");
  35.     g_hash_table_insert(name_score,"Candy","84");

  37.     g_hash_table_foreach(name_score,print_key_value,NULL);
  38.     char* Bean_score = g_hash_table_lookup(name_score,"Bean");
  39.     if(Bean_score == NULL)
  40.     {
  41.         fprintf(stderr,"can not found Bean Score\n");
  42.         ret = -2;
  43.         goto exit;
  44.     }
  45.     printf("Bean\'s score = %s\n",(char*)Bean_score);

  47.     printf("modify Bean\' Score to 86\n");
  48.     g_hash_table_replace(name_score,"Bean","86");

  50.     Bean_score = g_hash_table_lookup(name_score,"Bean");
  51.     if(Bean_score == NULL)
  52.     {
  53.         fprintf(stderr,"can not found Bean Score after modify\n");
  54.         ret = -2;
  55.         goto exit;

  57.     }

  59.     printf("Bean\'s score = %s\n",Bean_score);
  60. exit:
  61.     g_hash_table_destroy(name_score);

  63.     return ret;

  65. }

  67. int main()
  68. {
  69.      hash_test_1();
  70.     // hash_test_2();
  71. }
   这个例子是一个最简单的版本了，原因在于key和value都不是动态分配（malloc）出来的，不需要释放，所以我们不需要传递释放key和释放value的函数。
   这个版本太简单，他不符合实战的需求，我们搞一个稍复杂点的版本：
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <glib.h>
  4. #include <time.h>
  5. #include <assert.h>

  7. #define TIMES 20
  8. static void free_data(gpointer hash_data)
  9. {
  10.     g_free(hash_data);
  11.     hash_data = NULL;
  12. }


  15. void print_key_value(gpointer key, gpointer value ,gpointer user_data)
  16. {
  17.     printf("%4s -------------------->%s\n",(char*)key,(char*)value);
  18. }

  20. int hash_test_2()
  21. {
  22.      GHashTable* dictionary = NULL;
  23.      dictionary = g_hash_table_new_full(g_str_hash,g_str_equal,free_data,free_data);

  25.      if(dictionary == NULL)
  26.      {
  27.          fprintf(stderr,"create hash table failed\n");
  28.          return -1;
  29.      }

  31.      srandom(time(NULL));

  33.      int i = 0;
  34.      int ret = 0;
  35.      char key[64] ;
  36.      char value[64] ;
  37.      for(i = 0; i< TIMES;i++)
  38.      {
  39.          snprintf(key,sizeof(key),"%d",i);
  40.          snprintf(value,sizeof(value), "%d", random());
  41.          
  42.          char* key_in_hash = strdup(key);
  43.          char* value_in_hash = strdup(value);

  45.          if( value_in_hash == NULL || key_in_hash == NULL)
  46.          {
  47.              ret = -2;
  48.              fprintf(stderr,"key or value malloc failed\n");
  49.              goto exit;
  50.          }

  52.          if(strcmp(key_in_hash,"10") == 0)
  53.          {
  54.              printf("before insert key(10) address(%p) : value(%s) address(%p)\n",key_in_hash,value_in_hash,value_in_hash);
  55.          }
  56.          g_hash_table_insert(dictionary, key_in_hash,value_in_hash);

  58.      }

  60.     g_hash_table_foreach(dictionary,print_key_value,NULL);
  61.     printf("there are %d records in dictory\n",(unsigned int) g_hash_table_size(dictionary));

  63.     char* key_10 = NULL;
  64.     char* value_10 = NULL;
  65.     ret = g_hash_table_lookup_extended(dictionary,"10",(void **)&key_10, (void **)&value_10);
  66.     if(ret==FALSE)
  67.     {
  68.         fprintf(stderr, "can not the key 10\n");
  69.         goto exit;
  70.     }
  71.     else
  72.     {
  73.         fprintf(stderr,"In dictionary, key(%s) address(%p) : value (%s) address(%p)\n",key_10,key_10,value_10,value_10);
  74.     }

  76.     char* key_10_new = strdup("10");
  77.     char* value_10_new = strdup("new 10 value");

  79.     g_hash_table_replace(dictionary,key_10_new,value_10_new);


  82.     ret = g_hash_table_lookup_extended(dictionary,"10",(void **)&key_10,(void**)&value_10);
  83.     if(ret == FALSE)
  84.     {
  85.         fprintf(stderr, "found failed after modify\n");
  86.         
  87.     }
  88.     else
  89.         printf("After replace In dictionary, key(%s) address(%p) : value (%s) address(%p)\n",key_10,key_10,value_10,value_10);
  90.     
  91.     g_hash_table_remove(dictionary,"10");
  92.     value_10 = g_hash_table_lookup(dictionary,"10");
  93.     assert(value_10 == NULL);

  95.     ret = 0;
  96. exit:
  97.     g_hash_table_destroy(dictionary);
  98.     return ret;
  99. }

  101. int main()
  102. {
  103.      hash_test_2();
  104. }
   编译：
  1. gcc -o use ghash_use.c `pkg-config --cflags --libs glib-2.0 `
   输出：
  1. root@manu:~/code/c/self/ghash# ./use
  2. before insert key(10) address(0x82b29c8) : value(890994488) address(0x82b29d8)
  3.    9 -------------------->518218022
  4.   10 -------------------->890994488
  5.   11 -------------------->1367601760
  6.   12 -------------------->154022116
  7.   13 -------------------->1596002810
  8.   14 -------------------->297169373
  9.   15 -------------------->309362452
  10.   16 -------------------->2009687739
  11.   17 -------------------->899619098
  12.   18 -------------------->1938444585
  13.   19 -------------------->858182021
  14.    0 -------------------->737059251
  15.    1 -------------------->809558677
  16.    2 -------------------->1707784285
  17.    3 -------------------->2000110468
  18.    4 -------------------->155424423
  19.    5 -------------------->671731059
  20.    6 -------------------->1157942798
  21.    7 -------------------->1512213641
  22.    8 -------------------->488939051
  23. there are 20 records in dictory
  24. In dictionary, key(10) address(0x82b29c8) : value (890994488) address(0x82b29d8)
  25. After replace In dictionary, key(10) address(0x82b2b08) : value (new 10 value) address(0x82b2b18)
   我们的例子用到了如下的API：
1 创建hash table
  1. name_score = g_hash_table_new(g_str_hash,g_str_equal)
我们的hash table 叫做name_score，使用了g_hash_table_new这个API去创建，这个API本质是：
  1. GHashTable *
  2. g_hash_table_new (GHashFunc hash_func,
  3.                   GEqualFunc key_equal_func)
  4. {
  5.   return g_hash_table_new_full (hash_func, key_equal_func, NULL, NULL);
  6. }

  1. GHashTable *
  2. g_hash_table_new_full (GHashFunc hash_func,
  3.                        GEqualFunc key_equal_func,
  4.                        GDestroyNotify key_destroy_func,
  5.                        GDestroyNotify value_destroy_func)
我们看到了,g_hash_table_new 是 g_hash_table_new_full的弱化版，弱化在key_destroy_func和value_destroy_func都是NULL。对于我们第二个例子，key value的值都是我们malloc出来的（strdup），为了防止内存泄漏，我们销毁key-value对的时候，必须释放这些空间。如何释放？创建hashtable的时候指定。 从两个参数的含义当需要的时候，释放key需要对key对应的地址调用key_destroy_func，value亦然。
   什么是需要的时候呢？
   最直观的就是将这个hashtable 销毁的时候， 也就是我们调用 g_hash_table_destroy的时候，hash table会销毁插入到hashtable的每一个 key-value对
   再其次就是删除key-value对。我们调用g_hash_table_remove()的时候。会根据key找到对应key-valude，根据创建时有无对应销毁函数分别销毁之
   最难想到的是replace。 首先看下replace的API
  1. void
  2. g_hash_table_replace (GHashTable *hash_table,
  3.                       gpointer key,
  4.                       gpointer value)
  5. {
  6.   g_hash_table_insert_internal (hash_table, key, value, TRUE);
  7. }
    这个API里面要求用户提供的新的key 和value，注意此处，replace和insert的本质几乎是一样的，如果你创建hash table 的时候，指定了key_destroy_func和value_destroy_func, 这两个函数必须等够施加在你提供的key value上。何意？
  1.     char* key_10_new = strdup("10");
  2.     char* value_10_new = strdup("new 10 value");

  4.     g_hash_table_replace(dictionary,key_10_new,value_10_new);
    这是正确的用法，因为hashtable创建的时候制定了free_data作为key和value的销毁函数。如下是错误的用法，我学习glib hash之初，没少犯错误：
  1. static void free_data(gpointer hash_data)
  2. {
  3.     g_free(hash_data);
  4.     hash_data = NULL;
  5. }
  6.      
  7. dictionary = g_hash_table_new_full(g_str_hash,g_str_equal,free_data,free_data);
  8. g_hash_table_replace(dictionary,"10","new 10 value");
原因就在于，等destroy的时候会将free_data函数施加在"10" 和 “new 10 value”，两个常量字符串上，从而引发错误。
    g_hash_table_replace拿着key查找有没有对应的key-value对。如果找不到，就赤裸裸的变成了insert操作了，如果找的到old的key-value对，那么就需要释放了。

2  insert和replace
   因为我在学习glib hashtable replace的时候，写的代码总是段错误，一怒之下，我就看了glib的source code。发现glib的实现挺有意思的。
  1. void
  2. g_hash_table_insert (GHashTable *hash_table,
  3.                      gpointer key,
  4.                      gpointer value)
  5. {
  6.   g_hash_table_insert_internal (hash_table, key, value, FALSE);
  7. }

  9. void
  10. g_hash_table_replace (GHashTable *hash_table,
  11.                       gpointer key,
  12.                       gpointer value)
  13. {
  14.   g_hash_table_insert_internal (hash_table, key, value, TRUE);
  15. }
    我们到了这里，就不得不说下Glib对hash table的实现 了。我们常见的hash table的实现，基本是bucket list + 链表，何意？
                   
   如上图所示，前面是一排桶，对一一个key-value对，通过key使用hash function计算桶号，放入合适的桶中。如果桶中已经有了相同的hash值，这叫冲突。冲突的解决办法是链入链表。lookup的时候，首先根据key计算出桶号，依次遍历桶后面挂在每个key- value，知道找到对应的key为止。这个方法通俗易懂，我见过很多hash table都是这么写的，你要是让我写hash table ，我也这么写。这么写好不好，当然很好。但是也有不好的地方。链表是缓存杀手。一次命中也就罢了，如果命不中，链表next的内存位置几乎肯定用不上cache。之前我写queue，stack用链表的时候，已经有网友指出这一点。

   glib是如何实现的呢？   glib用的是数组来实现的。数组的好处不多说了，内存连续从而增大了缓存命中的概率。严格意义上讲，glib的hash是由三个数组：

  1. struct _GHashTable{
  2.       ....
  3.       gpointer *keys;
  4.       guint *hashes;
  5.       gpointer *values;
  6.       ....

  8. }
    看下创建过程g_hash_table_new_full，如何初始化这三个数组：
  1.   hash_table->keys = g_new0 (gpointer, hash_table->size);
  2.   hash_table->values = hash_table->keys;
  3.   hash_table->hashes = g_new0 (guint, hash_table->size)
    有些人看到这里可能迷惑了，明明是两个数组啊，keys和hash都开辟了空间，可是values没有开辟复用了key的数组。严格意义上将，对于hash table来讲，是三个数组，此处初始化两个数组，key 和value复用一个的原因，是为了照顾set集合。集合的概念和hash table是很像的，只不过hash table是key-value对，set的概念只有key，将一个元素插入集合，在集合中查找某个元素，这么一想，set和hash table本质是一样的，set 不过是弱化版的hash table。对于set来说，只有key 没有value，所以，value一开始是指向key的数组的。当然，这种兼顾hash table 和set给我们带来的一定的困惑。不过没关系，记住hash table本质是有三个数组就好了。真正的value数组的开辟是在g_hash_table_insert_node里面实现的：
  1. if (G_UNLIKELY (hash_table->keys == hash_table->values && key != value))
  2.     hash_table->values = g_memdup (hash_table->keys, sizeof (gpointer) * hash_table->size);
    另外我看过glib-2.24.0的代码，那时候还是创建hashtable的时候，直接分配三个数组。glib-2.34.0为了照顾set，已经改成现在这个样子。
    接下来我们将描述如何利用数组，做成hash table的。这就不得不讲整个hash table中最重要的两个function，说最重要，绝非虚言，绝不是考前老师划重点 ，到处都是重点的行径

   1  g_hash_table_lookup_node

  1. static inline guint
  2. g_hash_table_lookup_node (GHashTable *hash_table,
  3.                           gconstpointer key,
  4.                           guint *hash_return)
  5. {
  6.   guint node_index;
  7.   guint node_hash;
  8.   guint hash_value;
  9.   guint first_tombstone = 0;
  10.   gboolean have_tombstone = FALSE;
  11.   guint step = 0;

  13.   hash_value = hash_table->hash_func (key);
  14.   if (G_UNLIKELY (!HASH_IS_REAL (hash_value)))
  15.     hash_value = 2;

  17.   *hash_return = hash_value;

  19.   node_index = hash_value % hash_table->mod;
  20.   node_hash = hash_table->hashes[node_index];

  22.   while (!HASH_IS_UNUSED (node_hash))
  23.     {
  24.       /* We first check if our full hash values
  25.        * are equal so we can avoid calling the full-blown
  26.        * key equality function in most cases.
  27.        */
  28.       if (node_hash == hash_value)
  29.         {
  30.           gpointer node_key = hash_table->keys[node_index];

  32.           if (hash_table->key_equal_func)
  33.             {
  34.               if (hash_table->key_equal_func (node_key, key))
  35.                 return node_index;
  36.             }
  37.           else if (node_key == key)
  38.             {
  39.               return node_index;
  40.             }
  41.         }
  42.       else if (HASH_IS_TOMBSTONE (node_hash) && !have_tombstone)
  43.         {
  44.           first_tombstone = node_index;
  45.           have_tombstone = TRUE;
  46.         }

  48.       step++;
  49.       node_index += step;
  50.       node_index &= hash_table->mask;
  51.       node_hash = hash_table->hashes[node_index];
  52.     }

  54.   if (have_tombstone)
  55.     return first_tombstone;

  57.   return node_index;
  58. }
     这个函数是如此的重要，以至于我不得不无耻的把整个函数都搬出来了。上来就是闷头一棒，what is the fuck HASH_IS_REAL/HASH_IS_UNUSED/HASH_IS_TOMBSTONE？
    原谅我的粗俗，看这个简短函数的时候我的直观感受就是这个。
  1. #define UNUSED_HASH_VALUE 0
  2. #define TOMBSTONE_HASH_VALUE 1
  3. #define HASH_IS_UNUSED(h_) ((h_) == UNUSED_HASH_VALUE)
  4. #define HASH_IS_TOMBSTONE(h_) ((h_) == TOMBSTONE_HASH_VALUE)
  5. #define HASH_IS_REAL(h_) ((h_) >= 2)
    其实和前面hash table 桶的概念是一样的，只不过0号和1号被特殊处理了。如果你的key通过hash 函数散列以后，发现你的桶号是0或者是1,那么你的桶号强制改成2号。那0号和1号干啥用呢？ 因为前面提到的数组有个数组叫做hashes，它记录的是已经存在在hash table中所有的key经过散列之后的值（hash_key）。有两种情况是特殊的，
    1 数组的此位置从来没有被插入过，那么hashes这个数组的此位置 存储的是0，UNUSED_HASH_VALUE
    2 曾将存放过某个hash_key，但是被删除了，OK，记录成TOMBSTONE_HASH_VALUE。
   UNUSED_HASH_VALUE，告诉我们的，此处是天涯海角，是人类活动的极限，确切的说，是如果冲突了，和你有相同hash_key的那些key的活动的极限，从来没有和你冲突的key可到过此处，如果你找到了此处，依然没有找到你要找的key，就没有必要继续找下去了。
   TOMBSTONE_HASH_VALUE，告诉我们，曾经有个和你冲突的key（你们两个具有相同的hash_key）到达过此处，但是，后来被移除了。这表示此处可用。

        如上图所示，hashtable的数组hashes里面的记录分三种，如上图三种颜色，
   第一种是UNUSED_HASH_VALUE.也就是里面的值是0.表示此位置可用，我们可以将key存放到key数组的此位置，value数组也是同理。可以想见，刚初始化的的hash table全部是这个颜色的，统统可用。插入效率很高，直接插入对应位置即可。
   第二中颜色是红色，表示冲突了，已经有一个key占用了此位置，对不起，请查找其他位置。查找规则是
  1.       step++;
  2.       node_index += step
     如上图所示，直到遇到第一个UNUSED_HASH_VALUE，就不要再浪费时间继续差找了。为何？
    注意，key通过hash function之后得到hash_key，如果冲突，表示hash_key相同，那么大家查找的起点都是上图第一个红色位置，步进的规则又是相同的，如果后面仍有相同hash_key，此处必不会为UNUSED_HASH_VALUE。此处为UNUSED_HASH_VALUE，表示具有相同hash_key的key-value足迹从没有到达此处。hash_key都不一样，key也必然不一样。所以没有继续查找的必要了。
    另外一种颜色表示，曾有和我具有相同hash_key的兄弟到达此处，但是斯人已去，空余一个坑位。
    代码的含义就比较好懂了，
    1 遇到UNUSED_HASH_VALUE之前，和每个红色的比较key值，如果key值相同，不必多说，找到了相同的key。返回这个位置。
    2 遇到UNUSED_HASH_VALUE之前，如果遇到了TOMBSTONE_HASH_VALUE，把遇到的第一个坑位记住
    3 遇到了UNUSED_HASH_VALUE表示找不到相同的key，可以返回了。有TOMBSTONE_HASH_VALUE的坑位则返回第一个这种坑位，否则返回遇到的第一个UNUSED_HASH_VALUE类型坑位。

第二个重要函数就要迫不及待的闪亮登场了：

2   g_hash_table_insert_node
  第二个函数虽然重要，但是远不及第一个函数重要，第一个函数真正反映了hash的设计思想，如何处理碰撞，是全hash table的精华所在。但是这个函数，则承担了一些脏活累活。这个函数没那么重要，我依然把他全部copy了下拉。好吧，我本身就这么无耻。
  1. static void
  2. g_hash_table_insert_node (GHashTable *hash_table,
  3.                           guint node_index,
  4.                           guint key_hash,
  5.                           gpointer key,
  6.                           gpointer value,
  7.                           gboolean keep_new_key,
  8.                           gboolean reusing_key)
  9. {
  10.   guint old_hash;
  11.   gpointer old_key;
  12.   gpointer old_value;

  14.   if (G_UNLIKELY (hash_table->keys == hash_table->values && key != value))
  15.     hash_table->values = g_memdup (hash_table->keys, sizeof (gpointer) * hash_table->size);

  17.   old_hash = hash_table->hashes[node_index];
  18.   old_key = hash_table->keys[node_index];
  19.   old_value = hash_table->values[node_index];

  21.   if (HASH_IS_REAL (old_hash)) //找到的红色坑位，不仅仅是hash_key相等，而且key也相等
  22.     {
  23.       if (keep_new_key)
  24.         hash_table->keys[node_index] = key;
  25.       hash_table->values[node_index] = value;
  26.     }
  27.   else    
  28.     {
  29.       hash_table->keys[node_index] = key;
  30.       hash_table->values[node_index] = value;
  31.       hash_table->hashes[node_index] = key_hash;

  33.       hash_table->nnodes++;

  35.       if (HASH_IS_UNUSED (old_hash))
  36.         {
  37.           /* We replaced an empty node, and not a tombstone */
  38.           hash_table->noccupied++;
  39.           g_hash_table_maybe_resize (hash_table);
  40.         }

  42. #ifndef G_DISABLE_ASSERT
  43.       hash_table->version++;
  44. #endif
  45.     }

  47.   if (HASH_IS_REAL (old_hash))
  48.     {
  49.       if (hash_table->key_destroy_func && !reusing_key)
  50.         hash_table->key_destroy_func (keep_new_key ? old_key : key);
  51.       if (hash_table->value_destroy_func)
  52.         hash_table->value_destroy_func (old_value);
  53.     }
  54. }
    算了，不多说了，理解了第一个函数，再理解这个函数就是摧枯拉朽了。只要记住，hash_key相等表示冲突，这个坑位是三种颜色的，如前所述 。
   我希望大家注意keep_new_key这个标志位，对于g_hash_table_insert，这个标志位传递是FALSE，对于g_hash_table_replace，这个标志传递的是TRUE。两者仅仅在对待old_key的态度上不同，对于insert，仍然使用old_key释放新key，而replace则相反，仅此而已。

   最后的最后，对glib hash table性能感兴趣的，可以去此处 ， 对API感兴趣的可以去此处https://developer.gnome.org/glib/unstable/glib-Hash-Tables.html#g-hash-table-unref，对源码看兴趣的可以去此处，都不感兴趣的，谢谢你能看到此处，这是一个奇迹。

   本文提供PDF文档下载，不喜欢网上看的可以点击下面下载此文：
glib中hash table.pdf

参考文献：
1  glib是如何实现hash table的
2 glib-2.34.0 源码。
上一篇：PostgreSQL源码分析之解析配置文件
下一篇：file和page cache 的一些事儿

文章评论