[자료구조] 해시 테이블(Hash Table)

테이블(Table)

테이블

맵(Map) 혹은 사전 구조(Dictionary)라고도 불리운다.

테이블은 데이터가 key와 Value가 쌍을 이루는 자료구조이다.

• key : 중복되지 않는 값
• value : 실질적인 데이터

key를 기반으로 value를 탐색해야 하기 때문에 value를 근거로 key를 만드는 공식이 필요하다.

그렇지만 key와 value가 완전히 구분되지 않고 value의 일부를 key로 활용하는 경우도 있다.

Ex) 학번이라는 value를 key로 활용 (학번은 중복되지 않기 때문)

O(1)라는 빠른 속도를 가지지만 많은 공간이 낭비되는 문제가 발생한다.

struct StudentInfo
{
    int id;
    string name;
};
StudentInfo arr[30000000];
arr[20200123].id = 20200123;
arr[20200123].name = "주세돈";

극단적인 예시로 만약 학번을 key로 활용하여 index로 활용한다고 하면 위와 같이 비효율적인 구조가 될 것이다.

이를 개선하기 위해서는 학번(key)을 바로 활용하지 않고 적당한 값으로 변환 해주어야한다.

 

해시 테이블(Hash Table)

해시 테이블

위와 같은 문제를 개선할 수 있는 것이 바로 해시 함수(해시 알고리즘)이다.

해시 테이블을 구성하는 하나의 공간을 슬롯(Slot)이라고한다.

슬롯의 상태

• EMPTY - 데이터가 저장된 적 없음
• DELETED - 데이터가 저장된 적 있지만 지금은 비어있음
• INUSE - 데이터가 저장되어 있음

슬롯의 상태는 데이터의 저장 및 탐색을 할 때 활용된다.

 

 

좋은 해시 함수

좋은 해시 함수는 데이터의 저장위치가 적당히 분산되어 있다. (충돌이 발생할 확률이 낮다)

좋지 않은 해시 함수

좋지 않은 해시 함수는 데이터가 특정위치에 몰려 있다.(충돌이 발생할 확률이 높다)

 

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

Ex) 자리수 폴딩 방법

 

해시 테이블은 큰범위의 값을 제한된 범위에 저장하려다보니 해시 값이 충돌하는 문제가 있다.

Ex) value를 3으로 나눈 나머지를 해시 값으로 사용한다고 했을 때, 5와 8은 둘다 2가 남으므로 충돌이 발생한다.

 

충돌(Collision) 문제 해결법

개방 주소법 (Open Address)

선형 조사법(Linear Probing)

선형 조사법

충돌 발생 시 다음 위치에 저장하는 방식이다.

간단하지만 클러스터 현상이 발생하는 단점이 있다.

클러스터 현상() : 데이터가 특정 영역에 몰리는 현상

 

이차 조사법(Quadratic Probing)

이차 조사법

선형 조사법과 유사하지만 다음 위치(+1)가 아닌 +1, +4 ,+9 처럼 제곱수 만큼 이동한 위치에 저장하는 방식이다.

 

이중 해시(Double Hashing)

이중 해시

해시 함수를 두 개 정의하여 각각 저장할 때 사용하는 해시, 충돌을 해결하기 위한 해시로 사용하는 방법이다.

 

폐쇠 주소법 (Close Addressing)

체이닝(Chaining)

체이닝

하나의 해시 값에 다수의 데이터를 저장하는 방법이다.

2차원 배열 혹은 1차원 배열 + 연결 리스트 등으로 구현이 가능하다.

ps. 테이블 문제에 체이닝을 적용해보려 했지만 최악의 경우 시간 초과 때문에 적용할 수 없었다. (백준 암기왕)

 

참조

윤성우의 열혈 C 자료구조