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

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

- 원하는 바를 '단번에' 찾아내는 방식이다.

- 테이블 자료구조의 탐색 연산은 O(1)의 시간복잡도를 보인다.

 

"저장되는 데이터는 키(key)와 값(value)이 하나의 쌍을 이룬다."

"키(key)가 존재하지 않는 '값'은 저장할 수 없다. 그리고 모든 키는 중복되지 않는다"

 

---

배열을 기반으로 하는 테이블

https://github.com/GTAEKI/DataStructure_Study/blob/main/HashTable/ArrayTable/UnderstandTable.cpp

 

배열을 기반으로 하는 테이블의 문제점은

"고유 번호의 범위가 배열의 인덱스 값으로 사용하기에 적당하지 않다"

"고유번호의 범위를 수요할 수 있는 매우 큰 배열이 필요하다."

 

이 두가지 문제를 해결해 주는것이 '해쉬 함수'이다.

 

해쉬함수는 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 한다.

예를들어

int GetHashValue(int empNum)
{
	return empNum % 100;
}

라는 함수를 이용하게 될 경우

 

여러자리의 수 empNum(근로자의 번호)를 100 이하의 수(즉, 2자리 숫자)로 변경하여 값을 반환하게 된다.

 

이렇게 되면 배열을 기반으로 하는 테이블의 문제점 "고유 번호의 범위 및 매우 큰 배열" 두가지 문제중 1,2번은 해결되는 것처럼 보인다.

하지만 100으로 나머지 연산을 하여도 충돌(collision)이라는 문제는 남아있다.

문제점 1 -> 고유번호의 범위를 2자리 숫자로 변경하기 때문에 범위가 벗어날 일이 없음

문제점 2 -> 직원수가 100명 이내 99명보다 적다면, 저장을 할 수 있겠지만? 100명 이상의 숫자가 들어올 경우 배열 같은 인덱스, 즉 키값이 중복되는 문제가 생긴다. -> 이문제를 충돌(collision)이라고 표현

 

여기서는 배열의 길이를 늘리는 등의 방법으로 피해야할 상황이 아니다.

먼저 좋은 해쉬 함수의 조건을 알아보자.

좋은 해쉬 함수의 조건

"충돌을 덜 일으키는 해쉬함수" 가 좋은 해쉬함수이다.

-> 이는 특정 지역에 데이터가 몰리는것이 아니라 데이터가 테이블의 전체 영역에 고루 분포가 되어있어야 한다는 뜻이다.

-> 좋은 해쉬함수는 키의 일부분을 참조하여 해쉬 값을 만드는 것이 아닌, 키 전체를 참조하여 해쉬 값을 만들어 낸다.

 

좋은 해쉬 함수 디자인 방법은 키의 특성에 따라 달라지며, 절대적인 방법은 존재하지 않는다.

비트 추출방법, 자릿수 폴딩 방법, 키를 제곱하여 그 중 일부를 추출하는 방법, 폴딩 과정에서 덧셉대신 XOR연산을 하는 방법, 둘 이상의 방법을 조합하는 방법 등 통계적으로 넓은 분포를 보이는 다양한 방법들이 있다.

** 핵심은, 해쉬 함수를 디자인 할때 키의 특성과 저장공간의 크기를 고려하는것이 우선이라는 점이다.

 

충돌(Collision) 문제의 해결책

충돌이 발생하면 충돌이 발생한 그 자리를 대신할 빈 자리를 찾는것이 기본이다.

 

대표방법 두가지 : 선형조사법(Linear Probing)과 이차 조사법(Quadratic Probing)

선형조사법: 충돌이 날경우 바로 옆의 공간을 체크하여 빈공간일 경우 그 자리에 넣는 방법이다. 그 옆자리도 채워져 있다면 그 옆자리를 체크한다.

-> 충돌의 횟수가 증가함에 따라 '클러스터 cluster'현상(특정 영역에 데이터가 집중적으로 몰리는 현상)이 발생하므로 이 단점을 극복한것이 이차 조사법이다.

 

이차조사법: 충돌 발생시 n의 제곱칸 옆의 공간을 체크한다. 즉, 좀 더 멀리서 빈 공간을 찾으려는 노력이다.

 

위 두가지 방법을 활용하기 위해서는 공간(Slot,슬롯)의 상태를 3가지 상태로 나누는것이 중요하다.

1. EMPTY : 데이터가 저장된 적 없다.

2. DELETED : 데이터가 저장된 적은 있으나 현재는 비워진 상태이다.

3. INUSE :  유효한 데이터가 저장되어있다.

 

왜 중요할까?

1. 만약 %10으로 되어있는 해쉬함수가 있고 선형조사법이라는 가정.

2. 12라는 숫자가 들어온 뒤 2라는 숫자가 들어온다면

3. index 2번에는 충돌이 일어나서 2라는 숫자의 값은 3번 인덱스로 들어가서 저장될 것이다.

이 상황에서 12라는 숫자가 삭제된다고 생각해보자.

그런데 DELETED라는 상태가 없다면, 컴퓨터는 3번 인덱스를 찾을 길을 잃어버리게 될 것이다.

DELETED라는 상태를 통해, 컴퓨터에게 "아, 여기는 값이 들어왔다가 삭제된적이 있구나"를 알게하여 다음 주소인 3번값까지 찾게 만들어주는 역할을 하게된다.

 

이중 해쉬 (이차 조사법의 클러스터 현상을 극복할 다음 방법)

이차 조사법또한 선형 조사법보다는 덜하겠지만, 같은 규칙으로 공간(슬롯)을 체크하기때문에 클러스터 현상이 일어날 확률은 여전히 있다고 볼 수 있다.

이를 불규칙하게 구성한 것이 이중 해쉬방법이다.

 

1차 해쉬 함수 : 키를 근거로 저장위치를 결정 : h1(k) = k % 15;

2차 해쉬 함수 : 충돌 발생시 몇 칸 뒤를 살필지 결정 : h2(k) = 1 + (k % c)

->

여기서 1은 0이라는 값을 반환하지 않기 위함 (0을 반환하면 또다시 충돌)

여기서 c는 15보다 작은 소수(prime number)를 말한다. 15보다 작은 이유는 1차 해쉬값을 넘어가지 않게 하기 위함이며

소수를 사용하는 이유는 클러스터 현상의 발생 확률을 현저히 낮춘다는 통계가 근거이다.

 

실제로 이중 해쉬는 이상적인 충돌 해결책으로 알려져 있다고 한다.

 

여기까지 방법이 Open addressing method (열린 어드레싱 방법) 이라고 한다.

다음으로 Closed addressing method(닫힌 어드레싱 방법)을 알아보자.

---

체이닝(Chaining)

: 무슨 일이 있어도 자신의 자리에 저장을 하는 방식이다.

체이닝은 연결리스트를 이용하여 공간(Slot,슬롯)을 연결하는 방법이다.

 

** 이차원 배열을 기반으로 어드레싱 모델을 구현할 수 는 있으나, 배열을 기반으로 할 경우 충돌이 발생하지 않을경우 메모리 낭비가 심하며 또 충돌의 최대 횟수를 결정해줘야 한다는 문제점을 갖고있어서 사용하지 않는다.

 

이런식으로 구성된다.

 

체이닝 방법을 적용하면 하나의 해쉬 값에 다수의 슬롯을 둘 수 있다.

따라서 탐색을 위해서는 동일한 해쉬 값으로 묶여있는 연결된 슬롯을 모두 조사해야한다는 불편이 따른다.

하지만 해쉬 함수를 잘 정의한다면, 그래서 충돌 확률이 높지 않다면 연결된 슬롯의 길이는 부담스럽지는 않을것이라고 한다.

 

이때는 열린 어드레싱 방법에서의 공간(Slot,슬롯)의 상태를 표시하지 않는다. 다음 노드를 가리키는 포인터 변수로 컨트롤이 가능하기 때문이다.