리루

[자료구조] 해시 테이블 본문

# Algorithm

[자료구조] 해시 테이블

뚱보리루 2017. 1. 15. 23:31

- 해시 테이블은 가장 효율적인 탐색 중 하나인 해싱을 제공한다.

- 기본적으로 해시 테이블은 키(key)라는 특별한 인덱스로 자료에 접근하는 배열로 구성된다.

- 해시 테이블의 주 개념은 모든 가능한 키들과 배열의 위치 사이에 해시 함수를 이용해서 매핑(mapping)을 만드는 것이다.

- 해시 함수는 키를 전달 받아서 그 키의 해시 값(hash coding or hash value)을 리턴한다.

- 키들의 형은 다양하지만 해시 값은 항상 정수이다.


- 해시 값을 계산하는 것과 배열에서 특정 위치의 값을 얻는 것은 모두 상수 시간에 실행되므로 해싱의 매력은 상수 시간 탐색을 제공하는 점이다.

- 해시 함수가 임의의 키에 대해 같은 해시값을 리턴하지 않는다면 이 때 생성되는 해시 테이블은 직접 참조된다라고 한다.( 이것은 이상적이지만 실제로는 거의 불가능하다.)


ex) 이름에 영문 8글자가 들어가는 전화번호부에서 이름을 해시하는 예를 보자. 직접 참조를 하려면 해시 테이블은 26^8 = (2.09) * 10^11 이상의 항목을 가지게 되는데 대부분의 문자 조합이 이름이 아니므로 대다수가 사용되지 않을 것이다.


- 전형적으로 해시 테이블의 항목 개수는 가능한 키들의 전체집합보다 작다. 따라서 부분의 해시 함두들은 몇몇의 키들을 테이블의 같은 위치에 매핑한다.

- 두 키가 같은 위치에 매핑되면 충돌이 발생한다.

- 좋은 해시 함수는 충돌을 최소화하지만 충돌에 대한 대비도 있어야 한다.


1. 연쇄 해시 테이블(Chained hash table)

 - 버킷(Bucket)에 자료를 저장하는 해시 테이블이다. 각 버킷은 충돌을 조정하기 위해 필요한 만큼 커질 수 있는 연결리스트다.



 - 각 리스트는 하나의 버킷을 이루는데 배열의 특정 위치로 해시되는 모든 항목들이 이 버킷에 들어간다.

 - 항목을 삽입하기 위해 우선 항목의 키를 해시함수에 전달한다.

 - 함수는 그 항목이 어느 버킷에 속할지 결정한다.

 - 그 다음에 해당 리스트 맨 앞에 그 항목을 삽입한다.

 - 항목을 찾거나 삭제 할 때에는 항목의 키를 다시 해시해서 버킷을 찾고 해당 리스트를 순회하면서 항목을 찾는다.

 - 특정 위치에 많은 충돌이 발생하면 버킷이 점점 길어져 그 버킷의 항목에 접근하는 데 점점 더 많은 시간이 걸리게 된다.


typedef struct CHTbl_{


int    buckets;


int     (*h)(const void *key);

int    (*match)(const void *key1, const void *key2);

void    (*destroy)(void *data);


int    size;

List    *table;

} CHTbl;


// 함수 포인터 h는 키를 해시하는 사용자 정의 해시 함수이다.

// 함수 포인터 match는 두 key가 일치하는지를 결정하는 사용자 정의함수로, key1과 key2가 일치하면 1을 아니면 0을 리턴한다.

// 매개변수 destroy는 chtble_destroy호출 시 동적으로 할당된 자료들을 해제하기 위해 사용된다.



int chtbl_insert(CHTbl *htbl, const void *data){


void    *temp;

int       bucket, 

retval;


// 자료가 테이블에 이미 있으면 아무것도 하지 않음.

temp = (void*) data;


if(chtbl_lookup(htbl, &temp) ==0 )

return 1;


// 키 해싱.

bucket = htbl->h(data) % htbl->buckets;


// 자료를 버킷에 삽입

// NULL : Linked list 제일 앞에 삽입

if ((retval = list_ins_next(&htbl->table[bucket], NULL, data)) == 0)

htbl->size ++;


return retval;

}


int chtbl_lookup(const CHTBbl *htbl, void ** data){


ListElmt    *element;

int            bucket;


//키 해싱

bucket = htbl->h(*data) % htbl->buckets;


// 버킷에서 자료탐색.

for( element = list_head(&htbl->table[bucket]); element != NULL; element = list_next(element) ) {


if(htbl->match(*data, list_data(element) ) ){

//테이블에서 자료를 넘겨받기.

*data = list_data(element);

return 0;

}


// 자료를 찾지 못함.

return -1;


}



연쇄 해시 테이블 예제) : 심볼 테이블

 - 해시 테이블의 중요한 에플리케이션으로 컴파일러가 프로그램 내 기호(symbol)들의 정보를 유지하는 방법을 들 수 있다.

 - 컴파일러는 C가튼 언어로 작성된 프로그램을 프로그램이 실행될 기계의 기계어로 번역한다.

 - 컴파일러는 프로그램 내 기호들의 정보를 유지하기 위해서 심볼 테이블이라는 자료 구조를 사용한다.

 - 컴파일러는 기호 정보를 아주 빠르게 저장하고 검색해야 하므로 심볼 테이블은 흔히 해시 테이블로 구현된다.

 - 연쇄해시 테이블은 정보를 저장하고 검색하는 데 효율적이고 사실상 무한한 양의 자료를 저장할 수 있으므로 심볼 테이블을 구현하는 좋은 방법이다.(어휘 분석 이전에 프로그램에 몇개의 기호가 있는지 알 수 없기 때문에 이런 특징은 컴파일러에서 중요하다.)


1-1) 충돌 해결

 - 두 키가 해시 테이블의 같은 위치로 해시되면 충돌(collision)이 발생한다.

 - 버킷들이 같은 비율로 커져서 버키들의 크기가 가능한 작고 같게 되는 것이 이상적이다.

 - 이런 이론적으로 완벽한 상황을 균등 해싱(uniform hashing)이라고 한다.

 - 균등해싱을 하더라도 결과적으로 버킷의 수가 적으면 전체적으로 성능이 떨어진다.

 - 그렇기 때문에 테이블의 부하 계수(load factor)에 주의를 기울이는 것이 중요하다. n이 테이블의 항목 개수이고 m이 버킷의 개수일 때 해시 테이블의 부하 계수는 a= n/m과 같다. 


1-2). 나눗셈 방식(division method)

 - 키 k가 정수일 때 단순한 해싱 방법 중 하나는 k를 m으로 나는 나머지의 위치에 매핑하는 것이다. 

 - h(k) = k mod m

  (위의 방식은 해시값이 테이블의 끝을 지나지 않음을 보장한다. 해시 함수가 이것을 보장하더라도 특히 해시 함수를 호출자가 제공하므로 해시 테이블 구현에서도 보장하는 것이 가치가 있다. 그러나 개방 주소지정 해시 테이블에서 키를 2중 해시할 때 나머지를 수행하는 이유와는 다르다. 이 경우에는 두 보조 해시 함수들이 각각 테이블 내의 해시값을 생성하더라도 2중 해싱 과정에서 테이블의 한계를 벗어나는 해시값을 생성할 수 있다. 두 해삭ㅄ들이 더해지기 때문이다.)

 - 일반적으로 m의 값으로 2의 제곱수는 피해야 한다. 왜냐하면 m=2^p일 때 h는 k의 p개의 최하위 비트가 되기 때문이다.

 - 보통 기억장치의 제약조건과 부하 계수를 생각해서 2의 제곱수에 가깝지 않은 소수를 m으로 선택한다.



2. 개방 주소지정 해시 테이블(Open-addressed)

 - 모든 항목들이 테이블 자체에 존재한다.

 - 이러한 특징은 고정된 크기의 테이블에 의존하는 애플리케이션에서 중요하다.

 - 각 위치에 저장되는 항목의 개수를 늘릴 방법이 없으므로 충돌을 방지하는 다른 방법이 필요하다.


 2-1) 충돌방지

  - 개방 주소지정 해시 테이블에서 충돌을 방지하는 방법은 테이블을 조사하는 것이다. 예로, 항목을 삽입할 때 빈 위치를 찾아 조사하고 그 위치에 항목을 삽입한다.

  - 항목을 삭제하거나 찾을 때에는 그 항목이 있는 위치나 빈 위치를 만날 때까지 조사한다. 항목을 찾기 전에 빈 위치를 만나거나 모든 위치를 순회하면 그 항목은 테이블이 없는 것이다.



Q. 해시 테이블이 임의 접근에는 좋지만 순차접근에는 좋지 않은 이유는 무엇인가? 예를 들어, 레코드들에 순차적인 방식으로 접근하는 데이터베이스 시스템에서 해시를 사용했을 때 발생하는 문제는 무엇인가?

A. 각 키가 테이블의 어디에 필요한 정보가 있는지 또는 충돌이 발생할 때에도 최소한 몇 단계 내에 있는지를 명확하게 알려주므로 해시 테이블은 이므이 접근에 아주 뛰어나다. 그러나 해시 테이블은 순차 접근을 지원하지 않는다. 어떤 위치로 해싱한 후에 다음으로 작거나 큰 키가 테이블의 어디에 있는지를 결정하는 방법이 없다. 



Q. 연쇄 해시 테이블에서 항목을 탐색하는 성능의 최악의 경우는 무엇이며 이런 상황이 발생하지 않음을 어떻게 보장할 수 있는가?

A. 모든 항목들이 하나의 버킷으로 해시될 때 연쇄 해시 테이블은 최악으로 수행된다. 이 경우에 테이블의 항목 개수가 n일때 항목을 찾는 거은 O(n)이다. 이런 결과를 낳는 터무니 없는 해시 함수는 c가 해시 테이블 범위 내의 어떤 상수 일 때 h(k)=c이다. 좋은 해시 함수를 선택하는 것은 이런 경우가 발생하지 않음을 보장한다. 해시 함수가 균등 해싱에 가깝다면 항목의 위치를 상수 시간에 결정할 수 있다.



Q. 개방 주소지정 해시 테이블에서 항목을 탐색하는 성능의 최악의 경우는 무엇이며 이런 상황이 발생하지 않음을 어떻게 보장하는가?

A. 개방 주소 지정 해시 테이블에서 항목을 탐색하는 성능의 최약의 경우는 해시 테이블이 꽉차고 찾는 항목이 테이블에 없을 때 발생한다. 이 경우에 테이블의 위치 개수가 m일 때 항목 탐색은 O(m) 연산이 된다. 이런 상황은 어떤 해시 함수에서도 발생할 수 있다. 개방주소지정 해시 테이블에서 적당한 성능을 보장하려면 테이블이 80%이상 차지 않게 해야한다.



[참조] C로 배우는 알고리즘

'# Algorithm' 카테고리의 다른 글

[자료구조] 집합(set)  (0) 2017.01.12
[C언어] 재귀  (0) 2017.01.05
[C언어] 메모리 영억  (0) 2017.01.05
[C언어]포인터  (0) 2017.01.04
자료구조 & 소프트웨어 공학 소개  (0) 2017.01.03