glibc库中HASH算法的浅析

最近在做基于内存数据库的索引，因为之前接触的算法比较少，还好上头对索引这个事儿摧得不是很紧，头儿对这个事儿也很谨慎，让我们遵循着“要么不做，要做就要有突破”的思想。最近学习了一些数据结构和算法，刚开始只听说ORACLE索引用的是B树，所以就在网上搜罗许多关于B树的讲解，代码也有许多现成的，但是都不符号我们项目中场景，干脆就根据《算法导论》上B树的规则自己写了一份，唉，第一次接触这种高级的算法，这代码写了两天！写完之后，静下心来一想，我们的应用场景完全不一样啊！我们是基于内存的，ORACLE可是基于磁盘的啊！！我们主要是对更新数据和读取数据效率的要求，心想只要选用搜索最快，更新时操作次数最少的算法就好了！之后又学习了似乎当前搜索性能很强的红黑树，发现内存耗用还有复合键索引等方面不是很方便处理！接下来就轮到了HASH头上了，希望真的能有所突破吧！在HASH的学习中，这里真心地要感谢诸位前辈啊！谢谢你们在前方给道路照亮！
看了CU上兄的关键glibc中HASH的讲解，然后自己依据自己对HASH的需求，对比glibc源码简单地学习一下，下面给出自己对其中HASH的理解，望兄台们尽管把砖拍过来！也非常希望诸位能给予基于内存数据库索引方面的见解或者相关资料！！！^_^

之前我先申明一下GLIBC中HASH表处理冲突的方式，采用严蔚敏的《数据结构（C语言版）》教材中哈希算法的“开放定址”法来处理冲突问题，
即在某个桶的位置发现冲突，立即查看下一个桶位置有没有被占用。
HASH表结构
struct _GHashTable
{
  gint             size;      // 桶的个数
  gint             mod;       // 获得桶位置时的“基数”
  guint            mask;      // 用来取桶位置时用
  gint             nnodes;    // 应该是节点数
  gint             noccupied;  /* nnodes + tombstones */

  gpointer        *keys;     //存放关键字数组
  guint           *hashes;   //现存HASH值，注意这是一个当前占用该桶的HASH值，这个值是不小于2的
        // 如果这个值等于0，表示这个桶是一个“处女”桶；
         // 如果这个值等于1，表示这个桶刚被删除过；
  gpointer        *values;   //存放KEY 对应的VALUE值
        // 目前，VALUE的地址是复用KEY的地址

  GHashFunc        hash_func;  // 取得HASH值的HASH函数，HOOK函数
  GEqualFunc       key_equal_func;  // HOOK函数，关键字比较函数
  gint             ref_count;   //
#ifndef G_DISABLE_ASSERT
  /*
   * Tracks the structure of the hash table, not its contents: is only
   * incremented when a node is added or removed (is not incremented
   * when the key or data of a node is modified).
   */
  int              version;
#endif
  GDestroyNotify   key_destroy_func;  //KEY值撤销函数，HOOK函数
  GDestroyNotify   value_destroy_func;  //VALUE值撤销函数，HOOK函数
};
对于这个“桶”这里谈谈我的理解，主要就是keys、hashes、values，简单的理解就是一个“桶”里面有一个KEY值，
一个HASH值和一个VALUE值（这里可以忽略）。
hash表结构的创建，这是一个外部接口
GHashTable *
g_hash_table_new_full (GHashFunc      hash_func, //钩子函数，产生HASH值的HASH函数
                       GEqualFunc     key_equal_func, //判断关键字是否等的函数
                       GDestroyNotify key_destroy_func, //撤销KEY值空间的函数
                       GDestroyNotify value_destroy_func) //撤销VALUE值空间的函数
{
  GHashTable *hash_table;

  hash_table = g_slice_new (GHashTable);   //这里只是一个分配GHashTable结构体的过程
  g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT); //这里是对GHashTable结构进行初始化的过程
  hash_table->nnodes             = 0;
  hash_table->noccupied          = 0;
  hash_table->hash_func          = hash_func ? hash_func : g_direct_hash; //HASH函数初始化
  hash_table->key_equal_func     = key_equal_func; //KEY值判断函数的初始化
  hash_table->ref_count          = 1;
#ifndef G_DISABLE_ASSERT
  hash_table->version            = 0;
#endif
  hash_table->key_destroy_func   = key_destroy_func;   //KEY空间撤销函数的初始化
  hash_table->value_destroy_func = value_destroy_func; //VALUE空间撤销函数的初始化
  hash_table->keys               = g_new0 (gpointer, hash_table->size); //分配KEY空间的过程
  hash_table->values             = hash_table->keys;  //VALUE复用了KEY空间
  hash_table->hashes             = g_new0 (guint, hash_table->size); //分配存放命中HASH值的空间

  return hash_table;
}
功能：
检索HASH表，判断当前某个KEY值在对应的HASH表中存在与否，这是一个内部接口（static)
返回：
如果存在，返回桶的位置和HASH值；
如果不存在，返回最近的一个空桶的位置和HASH值
static inline guint
g_hash_table_lookup_node (GHashTable    *hash_table,   //HASH表结构
                          gconstpointer  key,  //KEY值
                          guint         *hash_return)   //返回HASH值
{
  guint node_index;
  guint node_hash;
  guint hash_value;
  guint first_tombstone = 0;
  gboolean have_tombstone = FALSE;
  guint step = 0;

  hash_value = hash_table->hash_func (key);        //根据应用提供的HASH函数产生一个HASH值
  if (G_UNLIKELY (!HASH_IS_REAL (hash_value)))     //如果HASH值为小于2的，就将HASH值强制定为2
    hash_value = 2;

  *hash_return = hash_value;   //填充返回的HASH值

  node_index = hash_value % hash_table->mod;      //取桶的位置
  node_hash = hash_table->hashes[node_index];     //取桶对应位置存放的HASH值

  while (!HASH_IS_UNUSED (node_hash))      //在遇到“处女”桶之前，检验当前桶中的HASH值和KEY值
    {
      /* We first check if our full hash values
       * are equal so we can avoid calling the full-blown
       * key equality function in most cases.
       */
      if (node_hash == hash_value)  //如果当前桶中的HASH值相等，就判断KEY是否相等
        {
          gpointer node_key = hash_table->keys[node_index];

          if (hash_table->key_equal_func)       //判断HASH表的KEY比较函数应用是否填充
      //如果已经填充，说明KEY值的类型是非默认类型
      //KEY值的比较就根据应用提供的比较函数来比较
            {
              if (hash_table->key_equal_func (node_key, key))    //用应用提供的HOOK函数进行KEY值的比较，
        //如果相等就直接返回桶的位置，
        //不相等就继续遍历桶
                return node_index;
            }
          else if (node_key == key)  //如果没有填充，说明KEY值的类型是默认的类型
      //KEY值的比较就直接进行比较，相等就直接返回桶的位置
      //不相等就继续遍历桶
            {
              return node_index;
            }
        }
      else if (HASH_IS_TOMBSTONE (node_hash) && !have_tombstone)   //记录下遍历过程中遇到的第一个被删除过的桶的位置
        {
          first_tombstone = node_index;
          have_tombstone = TRUE;
        }
/*
*  下面几步就是自加桶的位置过程
*/
      step++;      
      node_index += step;
      node_index &= hash_table->mask;
      node_hash = hash_table->hashes[node_index];
    }

  if (have_tombstone)  //如果遇到被删除过的桶，则返回第一个
    return first_tombstone;

  return node_index;
}

删除节点，这是一个内部接口
static void
g_hash_table_remove_node (GHashTable   *hash_table, //HASH表
                          gint          i,  //桶的位置
                          gboolean      notify)  // 是否通知，目前尚且还不知道实际意义在哪儿
{
  gpointer key;
  gpointer value;

  key = hash_table->keys[i]; 
  value = hash_table->values[i];

  /* Erect tombstone */
  hash_table->hashes[i] = TOMBSTONE_HASH_VALUE;   // 直接先把存放的HASH值置为“被删除”状态

  /* Be GC friendly */
  hash_table->keys[i] = NULL;   // 把KEY和VALUE值置空，其实是重复操作
  hash_table->values[i] = NULL;

  hash_table->nnodes--;   //节点个数减一

  if (notify && hash_table->key_destroy_func)    //如果通知为真，且KEY撤销函数不为空，撤销KEY
    hash_table->key_destroy_func (key);

  if (notify && hash_table->value_destroy_func)   //如果通知为真，且VALUE撤销函数不为空，撤销VALUE
    hash_table->value_destroy_func (value);

}

看到后面的插入，扫了一眼我就不想看了，它这里面很多东西对我来说没有多大用，它这里面的大概思想对我来说还是很有启发的。首先它这个HASH函数可以由应用自己灵活选定，没有把它给定死；第二它选择的这个处理冲突的方案非常适合我们这里，如果让我做的话首先想到的肯定是那个什么链地址法，但是这个在冲突率不高的情况下可能会学浪费很多内存空间；第三它的那个处理“处女”桶的方式也是比较好的；第四就是它对不同类型的“兼容”性，即对不同类型的KEY值，比较函数可以由应用指定。
如果诸位兄台想了解glibc中HASH详细介绍的还是看兄的相关介绍，http://blog.chinaunix.net/uid-24774106-id-3605760.html分析得相当到位！只是我初看的时候，还不知道它采用的什么处理冲突的办法（因为这一点是我们非常关注的），再次仔细品的时候才想起来，这不就是学生时代老师在课堂上说的几种常见处理冲突方法中的”开放地址法“嘛！唉，敝人还是太愚钝了！^_^