GLib의 GHashTable로 알아보는 해시 테이블의 충동 해결 방법

GLib에서 제공하는 해시 테이블(hash table)의 구현인 GHashTable의 충동을 해결하는 알고리즘을 살펴보자. GHashTable은 Open Addressing 방법 중에 Quadratic Probing 알고리즘을 사용하여 충동을 해결한다.^[각주:1]

해시의 연산-삽입(Insert), 검색(Lookup), 삭제(Remove)-을 할 때는, 주어진 키에 해당하는 적절한 해시 테이블의 인덱스 번호를 먼저 구해야 한다.

GHashTable에서는 g_hash_table_lookup_node() 함수가 이를 수행한다. 이 함수에서 해시키의 충동 해결 알고리즘이 구현되어 있다.

static inline guint
g_hash_table_lookup_node (GHashTable    *hash_table,
                          gconstpointer  key,
                          guint         *hash_return)
{
  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);
  if (G_UNLIKELY (!HASH_IS_REAL (hash_value)))
    hash_value = 2;

  *hash_return = hash_value;

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

  while (!HASH_IS_UNUSED (node_hash))
    {
      if (node_hash == hash_value)
        {
          gpointer node_key = hash_table->keys[node_index];

          if (hash_table->key_equal_func)
            {
              if (hash_table->key_equal_func (node_key, key))
                return node_index;
            }
          else if (node_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;
}

해시 테이블의 슬롯(Slot)에는 3가지 상태가 있다.

• UNUSED - 사용하지 않는 슬롯.
  
• TOMBSTONE - 사용되었으나 현재는 삭제된 슬롯. 충돌로 연결된 다른 값이 뒤이 있을 수 있다는 정보를 남겨두기 위해서 UNUSED가 아닌 TOMBSTONE을 사용한다. 즉, 해시 인덱스의 끊김을 방지한다.
  
• USED or REAL - 키의 해시값이 저장된 슬롯. HASH_IS_REAL 매크로 함수로 알 수 있다.
  

적절한 해시 인덱스를 찾는 과정은 UNUSED가 나오거나(23 줄) 주어진 해시키와 동일한 키를 찾을 때(29~37줄)까지 반복한다.

다음 해시 인덱스는 순차적으로 증가하는 값을 더해주는데(45~48줄), 이것이 Quadratic Probing 알고리즘이다. Quadratic Probing 알고리즘은 Open Addressing 방법 중에 하나이다. Open Addressing 방법 중에 Linear probing 알고리즘의 문제점을 개선하기 위한 것이다. Linear probing 알고리즘은 해시키 충돌이 나면 이것은 고정된 값(보통 1)을 더한 다음 인덱스에 저장한다. 따라서 충돌이 발생하다보면, 클러스터(Cluster)라는 연속된 데이타 블럭이 발생하게 된다. 이것은 해시 테이블의 연산의 효율을 떨어뜨린다. 반면에, Quadratic Probing 알고리즘은 다음 인덱스로 이동하는 값이 순차적이지 않아서 데이타가 연속으로 몰리게 되는 현상을 줄어든다.

그러나 Open Addressing 방법은 적재율(Load Factor, 해시 테이블에서 데이타가 존재하는 비율)의 증가에 따라서 매우 가파르게 성능이 떨어지는 문제가 있다. Quadratic Probing 알고리즘이 같은 계열의 Linear probing에 비해서 상대적으로 적재율에 따른 크러스터의 발생 가능성을 줄여주지만, 그 한계는 분명 존재한다. GHashTable은 Open Addressing 방법에서 이를 해결하기 위해서 테이블의 크기를 상황에 따라서 자동으로 변경하는 방법을 사용한다. 즉, 해시 연산에 문제가 발생하기 전에 테이블의 크기를 늘려서 일정한 적재율 이하로 유지한다. 즉, 해시 테이블의 크기를 사용하는 데이타의 양에 비례해서 증가하거나 감소한다. 이 방법은 해시 테이블의 연산 효율 뿐만 아니라 메모리를 효과적으로 사용할 수 있게 한다. GHashTable에서는 g_hash_table_maybe_resize() 함수에서 해시 테이블의 크기를 변경할 필요성을 확인되면 g_hash_table_resize() 함수를 호출하여 이를 수행한다.

static inline void
g_hash_table_maybe_resize (GHashTable *hash_table)
{
  gint noccupied = hash_table->noccupied;
  gint size = hash_table->size;

  if ((size > hash_table->nnodes * 4 && size > 1 << HASH_TABLE_MIN_SHIFT) ||
      (size <= noccupied + (noccupied / 16)))
    g_hash_table_resize (hash_table);
}

사용되지 않는(unused) 슬롯과 사용되었다가 삭제된(tombstones) 슬롯이 해시 테이블의 3/4을 차지하면 메모리 공간이 비효율적으로 사용되고 있다고 판단하여 크기를 재조정하게 된다. g_hash_table_resize() 함수를 보면 데이타의 개수의 2배로 만든다. 즉, 적재율을 50%로 재조정한다.

데이타 슬롯의 개수(nnodes)와 삭제된 슬롯의 개수(tombstones)를 합한 개수(hash_table->noccupied)가 많아지면 해시 연산을 할 때마다 과도한 비교가 발생하여 성능이 저하된다. GHashTable에서는 hash_table->noccupied가 해시 테이블의 93.75%가 되면, 적재율 50%로 재조정한다.

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

적재율 재조정 과정에서는 사용하는 슬롯만 복사한다. 즉, 삭제된 슬롯(tombstones)은 복사하지 않는다.

아래에 기타 다른 방법을 소개한다. 자세한 것은 직접 찾아서 공부하길 바란다.

• 충돌로 인한 성능 저하 문제를 해결하는 Chaining 방법: Open Addressing의 성능 저하 문제를 해결하는 다른 알고리즘으로는 Chaining이 있는데, 이 방법은 적재율에 크게 영향을 받지 않는다. 충돌이 발생하면 해당 슬롯에 연결 리스트의 형태로 슬롯을 추가한다.
  
• 성능의 저하없이 해시 테이블의 크기를 변경할 수 있는 동적 해싱(Dynamic Hashing): 일반적으로 해시 테이블은 메모리의 낭비가 발생한다. 동적 해싱은 테이블의 크기를 가변적으로 사용할 수 있어서 메모리를 효율적으로 사용할 수 있다. GHashTable에서는 이를 해결하기는 하지만, 정적 해싱(Static Hashing)의 단점인, 해시 테이블의 크기를 변경하는 과정에서 값의 복사가 수반되는 단점이 있다. 동적 해싱은 정적 해싱에서 발생하는 값의 복사가 일어나지 않는다.
  

---

1. glib-2.19 버젼부터 이 알고리즘으로 변경되었다. 그 이전에는 Chaining 알고리즘을 사용했다. [본문으로]