c - GHashTable 是如何使用哈希值来存储它的节点的呢？

Question

g_hash_table_new() 的文档表示

Hash values are used to determine where keys are stored within the GHashTable data structure.

但是如何使用哈希值？

好像g_hash_table_foreach()遍历表从 0 到 N- 1 为 N 个节点。我使用这个函数打印出每个节点的散列、键和值:

测试.c

#include <glib.h>

static GHashTable* _htab = NULL;

static int VALS[] = { 1, 2, 3, 4, 5 };

struct kv {
  gpointer key;
  gpointer val;
};

static struct kv KEYVALS[] = {
  { "aaa",    &VALS[0] },
  { "a",      &VALS[1] },
  { "b",      &VALS[2] },
  { "bbbbbb", &VALS[3] },
  { "aaaaa",  &VALS[4] }
};

static void iter(gpointer key, gpointer val, gpointer data) {
  g_printf("key=%s(%p) val=%d(%p) hash=%u\n",
      (char*)key, key,
      *(int*)val, val,
      g_str_hash((char*)key)
  );
}

int main(int argc, char* argv[]) {
  int i;

  if (!_htab) {
    _htab = g_hash_table_new(g_str_hash, g_str_equal);
    g_assert(_htab);
  }

  for (i = 0; i < sizeof(KEYVALS) / sizeof(KEYVALS[0]); i++) {
    g_hash_table_insert(_htab, KEYVALS[i].key, KEYVALS[i].val);
  }
  g_hash_table_foreach(_htab, iter, NULL);
  g_hash_table_remove_all(_htab);
  g_hash_table_destroy(_htab);
  return 0;
}

即使经过多次运行，输出始终相同(指针值除外)，因此这里使用了某种算法。 节点的哈希值(例如，来自 g_str_hash() )如何确定它在 GHashTable 中的存储位置？

$ gcc `pkg-config --cflags glib-2.0` `pkg-config --libs glib-2.0` test.c
$ ./a.out
key=bbbbbb(0x10f142ee0) val=4(0x10f1430ac) hash=4087176913
key=a(0x10f142edc) val=2(0x10f1430a4) hash=177670
key=b(0x10f142ede) val=3(0x10f1430a8) hash=177671
key=aaaaa(0x10f142ee7) val=5(0x10f1430b0) hash=252781386
key=aaa(0x10f142ed8) val=1(0x10f1430a0) hash=193485928
$

Answer 1

让我们看看是什么the source code可能会告诉我们。

static inline guint
g_hash_table_lookup_node (GHashTable    *hash_table,
                          gconstpointer  key,
                          guint         *hash_return)
{
  /* ... */
  hash_value = hash_table->hash_func (key);
  /* ... */
  node_index = hash_value % hash_table->mod;
  /* ... */

哈希值取模一些值。让我们看看它可能是什么。

static void
g_hash_table_set_shift (GHashTable *hash_table, gint shift)
{
  /* ... */
  hash_table->size = 1 << shift;
  hash_table->mod  = prime_mod [shift];
  /* ... */

啊哈，来自 static const 预定义素数数组的素数。但是它设置在哪里呢？

#define HASH_TABLE_MIN_SHIFT 3  /* 1 << 3 == 8 buckets */

/* ... */

GHashTable *
g_hash_table_new_full (GHashFunc      hash_func,
                       GEqualFunc     key_equal_func,
                       GDestroyNotify key_destroy_func,
                       GDestroyNotify value_destroy_func)
{
  /* ... */
  hash_table = g_slice_new (GHashTable);
  g_hash_table_set_shift (hash_table, HASH_TABLE_MIN_SHIFT);

和

static void
g_hash_table_resize (GHashTable *hash_table)
{
  /* ... */
  g_hash_table_set_shift_from_size (hash_table, hash_table->nnodes * 2);

因此，在创建 GHashTable 时，一个特定的质数被分配给它，它用于将哈希值转换为索引。之后，当哈希表增长时，再次调用 g_hash_table_set_shift 来更新素数，并针对给定的哈希值返回不同的索引。