Как GHashTable использует хеш-значение для хранения своих узлов? - PullRequest
Новая
       19

Как GHashTable использует хеш-значение для хранения своих узлов?

3 голосов
/ 13 января 2012

Документация для g_hash_table_new() указывает

Хеш-значения используются для определения того, где ключи хранятся в структуре данных GHashTable.

но как используются значения хеша?

Кажется, g_hash_table_foreach() пересекает таблицу от 0 до N- 1 для N узлов,Я использовал эту функцию, чтобы распечатать хеш, ключ и значение для каждого узла:

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
$

1 Ответ

4 голосов
/ 13 января 2012

Давайте посмотрим, что может сказать нам исходный код . 

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 вызывается еще раз для обновления простого значения и вызывает возвращение различных индексов для данных хеш-значений.

...