GHashTableはそのノードを格納するためにハッシュ値をどのように使用しますか？

Question

g_hash_table_new()のドキュメントは

ハッシュ値をキーがGHashTableデータ構造内に格納されている場所を決定するために使用される示します。

ハッシュ値はどのように使用されますか？

g_hash_table_foreach()がNノードに対してN- 1から0からテーブルを横断ようです。私は、ハッシュを印刷するためのキーを、この機能を使用し、各ノードの値：出力が常に同じである

test.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が再び呼び出されてプライム値が更新され、与えられたハッシュ値に対して異なるインデックスが返されます。