테이블(Table)과 해쉬(Hash)

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다.

 

1. 빠른 탐색을 보이는 해쉬 테이블

테이블(Table) 자료구조의 이해

• 테이블 자료구조의 탐색 연산은 O(1)의 시간 복잡도를 보임.
• 저장되는 데이터는 키(key)와 값(value)가 하나의 쌍을 이루며 모든 키는 중복되지 않음
• 테이블은 사전 구조라고도 불리며 맵(map)이라고도 불림.

테이블에 의미를 부여하는 해쉬 함수와 충돌 문제

• 배열을 기반으로 한 테이블의 문제점 ex) 직원 테이블
  • 직원 고유번호의 범위가 배열의 인덱스 값으로 사용하기에 적당하지 않음
  • 직원 고유번호의 범위를 수용할 수 있는 매우 큰 배열이 필요함.

• 해쉬 함수(hash function): 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 함.
• 8자리 고유번호를 2자리 단위로 변경함.
• 하지만, 이 경우도 충돌 문제가 발생하기 때문에 해결책이 아닌 회피책이다.

좋은 해쉬 함수의 조건

• 데이터가 테이블의 전체 영역에 고루 분포되어 있는 경우, 충돌이 발생할 확률이 낮다는 것을 의미
• 반면, 테이블의 특정 영역에 데이터가 몰린 경우, 충돌이 발생할 확률이 높다는 의미
• 좋은 해쉬 함수는 키의 일부분이 아닌 전체를 참조하여 해쉬 값을 만들어 내는 것이 좋다.

자릿수 선택(digit selection) 방법과 자릿수 폴딩(digit folding) 방법

• 좋은 해쉬 함수 디자인은 절대적인 방법은 없으며 다양한 방법이 존재함.
• 키의 특정 위치에서 중복의 비율이 높거나, 아예 공통으로 들어가는 값이 있다면, 이를 제외한 나머지를 가지고 해쉬 값을 생성하는 방법이 있음
• 그리고 유사하게 탐색 키의 비트 열에서 일부를 추출 및 조합하는 비트 추출 방법도 있음
• 자릿수 폴딩(digit folding)

27 + 34 + 19 = 80

• 이 외에도 다양한 방법이 존재하는데 이는 키의 특성과 저장공간의 크기를 고려하는 것이 우선

 

2. 충돌(Collision) 문제의 해결책

선형 조사법(Linear Probing)과 이차 조사법(Quadratic Probing)

• 선형 조사법
  • 충돌이 발생했을 때 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 방법
  • k의 키에서 충돌 발생시 선형 조사법의 조사 순서
  $$ f(k)+1 → f(k)+2 → f(k)+3 → f(k)+4 ... $$
  • 이러한 방법은 충돌 횟수가 증가함에 따라 특정 영역에 데이터가 집중적으로 몰리는 클러스터(cluster) 현상이 발생
• 이차 조사법
  • 이러한 단점을 극복하기 위해 충돌 발생 시 $n^2$칸 옆 슬롯을 검사한다.
• 슬롯의 상태
  • EMPTY : 이 슬롯에는 데이터에 저장된 바 없다.
  • DELETED : 이 슬롯에는 데이터가 저장된 바 있으나 현재는 비워진 상태
  • INUSE : 이 슬롯에는 현재 유효한 데이터가 저장되어 있음
• 만약 키가 9인 데이터를 삭제한 경우의 슬롯 상태이다.
• 해쉬 값이 2인 데이터는 DELETED 상태

• 이전 키가 2인 데이터가 충돌로 밀려났기 때문에 해쉬 값이 3으로 저장된 상황.
• 키가 2인 데이터 탐색을 위해 해쉬 함수를 거치면서 2를 인덱스로 하여 탐색을 진행
• 만약, DELETED 상태가 없이 EMPTY였다면 존재하지 않는다고 판단하여 탐색을 종료함.
• 하지만 DELETED 상태였기 때문에 충돌이 발생했었음을 의심할 수 있고 선형 조사법에 근거하여 탐색을 진행함.
• 결론
  • 선형, 이차 조사법과 같은 충돌 해결책을 적용하기 위해선 DELETED 상태가 존재해야 함.
  • 선형, 이차 조사법을 적용했다면, 탐색 과정에서도 이를 근거로 충돌을 의심하는 탐색의 과정을 포함해야 함.

이중 해쉬(Double Hash)

• 해쉬 값이 같으면, 충돌 발생 시 빈 슬롯을 찾기 위해서 접근하는 위치가 늘 동일한 문제가 있음
• 이중 해쉬는 두 개의 해쉬 함수를 사용하는 방식
  • 1차 해쉬 함수: 키를 근거로 저장위치를 결정하기 위한 것, $h1(k)=k\%15$
  • 2차 해쉬 함수: 충돌 발생시 몇 칸 뒤를 살필지 결정하기 위한 것, $h2(k)=1+(k\%c)$
• 해쉬 함수를 이중으로 두면 1차 해쉬 함수 값이 같더라도 2차 해쉬 함수 값이 달라져 클러스터 현상을 낮출 수 있음

⛓️체이닝(chaining)

• 열린 어드레싱 방법(open addressing method): 충돌이 발생하면 다른 자리에 대신 저장한다는 의미
• 닫힌 어드레싱 방법(closed addressing method): 충돌이 발생해도 자신의 자리에 저장을 한다는 의미

• 슬롯을 생성하여 연결 리스트의 모델로 연결해 나가는 방식으로 충돌 문제를 해결하는 방법
• 탐색을 위해선 동일한 해쉬 값으로 묶여있는 연결된 슬롯을 모두 조사해야 한다는 불편함이 있음.
• 체이닝을 구현하면 슬롯의 상태 정보를 표시할 필요가 없어짐
• 슬롯과 테이블 정의

typedef int Key;
typedef Person * Value;

typedef struct _slot
{
	Key key;
	Value val;
} Slot;

#define MAX_TBL 100

typedef int HashFunc(Key k);

typedef struct _table
{
	List tbl[MAX_TBL];
	HashFunc * hf;
} Table;

void TBLInit(Table * pt, HashFunc *f);
void TBLInsert(Table * pt, Key k, Value v);
void TBLDelete(Table * pt, Key k);
void TBLSearch(Table * pt, Key k);

• 연결리스트 선언 변경
  • 연결 리스트 노드의 data가 slot형 변수의 주소 값이 됨

  typedef Slot * Data;
  
  typedef struct _node
  {
  	Data data;
  	struct _node * next;
  } Node;
  

• 그 외의 코드는 연결리스트 구현과 동일하게 진행됨.

 

자료

• 윤성우의 열혈 자료구조 (윤성우 저, 2023.10)