Hash Dictionary란 무엇인가?

* 해당 글은 학과 수업으로 배운 내용과 코드가 포함되어 있으며 개인적 공부 목적으로 업로드하였습니다.

우리는 이전에 hash dictionary library를 살펴본 적이 있다. 

 

이 library는 generic한가?

-Generic Libraries란 1) client가 data type을 선택할 수 있어야 하고 2) 같은 application안에서 다른 data type에 따라 multiple instances 가  가능해야 한다.

 

Hash Dictionary를 살펴보면

// typedef ___ * entry;
// typedef ___ key;

를 통해 우리는 client가 data type을 선택할 수 있음을 확인할 수 있다. 

그러나 같은 application안에서 multiple instances가 불가능하다.

 

따라서 이전 게시물에서 살펴본 void*으로 해결해보고자 한다.

typedef void* entry;
typedef void* key;

library interface에서 이를 void*로 define했기 때문에 client가 일일히 type을 지정할 필요가 없다.

따라서 이전에 지정했던대로 client에게 entry는 여전히 struct inventory_item*이고 key는 현재 string*이다. 

 

/****Client interface****/

typedef void* entry;
typedef void* key;

/****Fulfiliing the library interface****/
//typedef struct inventory_item* entry;
//typedef string key;

따라서 모든 entry는 struct inventory_item* tag를 가지게 되고 모든 key는 string* tag를 가지게 된다.

따라서 key를 사용하기 전에 string*으로 cast하고 결과를 string으로 dereference한다.

int key_hash(key k)
//@requires k!=NULL && \hastag(string*, k);
{
  return lcg_hash_string(*(string*)k);
}

entry에서 key를 뽑아낼때 우리는 allocated memory안의 cell에 넣어놔야 한다.

key entry_key(entry e)
//@requires e!=NULL && \hastag(struct inventory_item*, e);
//@ensures \result !=NULL && \hastag(string*, \result);
{
   struct inventory_item* E = (struct inventory_item*) e;
   string* K = alloc(string);
   *K = E->fruit; #string
   return (key)K;
}

string을 string* 으로 바꾸는 helper function을 도입하면 읽기에 더 쉬워진다.

string* to_string_ptr(string s)
//@ensures \result !=NULL;
{
  string* s_ptr= alloc(string);
  *s_ptr = s;
  return s_ptr;
}


key entry_key(entry e)
//@requires e!=NULL && \hastag(struct inventory_item*, e);
//@ensures \result !=NULL && \hastag(string*, \result);
{
   struct inventory_item* E = (struct inventory_item*) e;
   string* K = to_string_ptr(E->fruit);
   return (key)K;
}

다른 hash dictionary library function도 비슷하게 바꿀 수 있다. 

bool key_equiv(key k1, key k2)
//@requires k1 !=NULL && \hastag(string*, k1);
//@requires k2 !=NULL && \hastag(string*, k2);
{
   return string_equal(*(string*)k1, *(string*)k2);
}

int key_hash(key k)
//@requires k!=NULL && \hastag(string*, k);
{
  return lcg_hash_string(*(string*)k);
}

단 library와 client interface가 같은 함수 이름을 가짐에 따라 이름을 바꿔주어야 할 필요가 있다. 

bool key_equiv_produce(key k1, key k2)
//@requires k1 !=NULL && \hastag(string*, k1);
//@requires k2 !=NULL && \hastag(string*, k2);
{
   return string_equal(*(string*)k1, *(string*)k2);
}

int key_hash_produce(key k)
//@requires k!=NULL && \hastag(string*, k);
{
  return lcg_hash_string(*(string*)k);
}

Library에게 어떤 function을 적절하게 써야할지 알려주기 위해 우리는 pointer를 사용할 수 있다.

option 1) library function에게 맞는 client function을 전달한다. 

entry A = make_inventory_item("apple", 20);
hdict_insert(H, A, &entry_key_produce, &key_hash_produce, &key_equiv_produce);

이럴 경우 우리는 hdict_insert와 hdict_lookup을 사용할때마다 매번 불러줘야 한다.

 

option 2) dictionary를 만들때 처음부터 맞는 client function을 pass한다. 

hdict_t H  = hdict_new(H, &entry_key_produce, &key_hash_produce, &key_equiv_produce);

이 client functions들을 넣을때 우리는 올바른 type을 define해야 한다.

/***client interface***/

typedef void* entry;
typedef void* key;

typedef key entry_key_fn(entry e) //@requires e!=NULL;
typedef int key_hash_fn(key k);
typedef bool key_equiv_fn(key k1, key k2);

이를 모든 data structure에 반영한다. 

->struct hdict_header에 추가한다.

struct hdict_header{
 int size;
 int capacity;
 chain*[] table;
 entry_key_fn * key;
 key_hash_fn* hash;
 key_equiv_fn* equiv;
};
typedef struct hdict_header hdict;

이에 따라 representation invariant도 변형된다

bool is_hdict(hdict* H){
   return H!=NULL && 
          H -> size >=0 &&
          H -> capacity >0 &&
          is_array_expected_length(H->table, H->capacity) &&
          H->key !=NULL &&
          H->hash !=NULL &&
          H->equiv !=NULL &&
          is_valid_hashtable(H);
}

hdict* hdict_new(int capacity, entry_key_fn* entry_key, 
                 key_hash_fn* hash, key_equiv_fn* equiv)
//@requires capacity >0;
//@ requires entry_key !=NULL && hash !=NULL && equiv !=NULL;
//@ensures is_hdict(\result);
{
  hdict* H = alloc(hdict);
  H->size = 0;
  H->capacity = capacity;
  H->table = alloc_array(chain* ,capacity);
  H->key = entry_key;
  H->hash = has;
  H->equiv = equiv;
  return H;
}

이를 통해 client function이 필요할 때 function pointer를 사용하면 된다

int index_of_key(hdict* H, key k)
//@requires is_hdict(H);
//@ensures 0<= \result && \result < H->capacity;
{
   # H->hash가 key_hash function
   return abs((*H->hash)(k)%H->capacity); 
}

Harmony

client definition functions를 pointer로 접근이 쉽게 가능해졌기에 몇가지를 살펴보자 

우선 이전에 만들었던 key_hash_produce와 key_equiv_produce에 대한 alternative version을 만들어보자

-> key_hash_produce_alt, key_equiv_produce_alt

key hash_produce 와 key_hash_produce_alt가 같은 일을 하고 key_equiv_produce와 key_equiv_produce_alt가 같은 일을 한다면 섞어서 쓰는것도 가능할까?

ex) hdict_t H hdict_new(H, & entry_key_produce, &key_hash_produce_alt, &key_equiv_produce);

-> 불가능하다!

 

이를 harmony라고 한다. 

key hash와 equivalent function은 같은 entries가 같은 hash value를 만들때 harmony 에 있다고 말한다. 

-harmony에 있지 않으면 hash dictionary는 제대로 작동하지 않는다.

-하지만 harmony에 있다 하더라도 efficient 한걸 보장할 순 없다.