자료구조 : 테이블과 해시

ROK·2022년 11월 16일
0

열혈 자료구조

목록 보기
30/30

테이블 자료구조

테이블도 탐색과 관련이 밀접하기 때문에 탐색과 관련이 크다고 할 수 있다.

테이블 자료구조

사번: Key직원: Value
99001짱구
99002맹구
99003철수
99004유리
99005훈이

테이블은 우리가 일상에서 자주 보는 표를 테이블이라고 한다.(표가 영어로 테이블)
하지만 자료구조의 관점에서 모든 표를 테이블이라고 하지 않고 표에 저장된 데이터의 형태가 키(Key)값(Value)이 하나의 쌍을 이룰때 테이블로 구분한다.

저장되는 데이터의 Key는 데이터를 구분하는 기준이 되기 때문에 중복이 되어서는 안되고, 필수적으로 존재해야한다.

테이블 예시

배열을 기반으로 하는 간단한 테이블 예시이다.

#include <stdio.h>

typedef struct _empInfo
{
    int empNum;
    int age;
} EmpInfo;

int main() {
    EmpInfo empInfoArr[1000];
    EmpInfo ei;
    int eNum;

    printf("사번과 나이 입력 : ");
    scanf("%d %d", &(ei.empNum), &(ei.age));
    empInfoArr[ei.empNum] = ei;

    printf("확인하고 싶은 직원의 사번 입력 : ");
    scanf("%d", &eNum);

    ei = empInfoArr[eNum];
    printf("사번 : %d, 나이 : %d \n", ei.empNum, ei.age);

    return 0;
}

결과

사번과 나이 입력 : 129 29
확인하고 싶은 직원의 사번 입력 : 129
사번 : 129, 나이 : 29 

핵심은 키와 값을 하나의 쌍으로 묶기 위해 정의된 구조체이다.
구조체를 통해 키와 값을 하나의 쌍으로 정의하고 키를 기반으로 데이터의 값을 쉽게 찾을 수 있다.

하지만 위 코드에서 문제는 배열의 길이가 1000이라는 점이다. 만약 직원의 고유번호가 3자리가 아니라 더 긴 수라면 배열은 더 커져야한다.

해시

위에서 테이블에 대해서 간단히 정의하고, 배열을 기반으로 테이블을 정의했을때 생기는 문제까지 확인했다.

문제를 정리하자면 직원의 고유번호를 인덱스 값으로 쓰기에는 범위가 클 수록 큰 배열이 필요하기 때문에 고유번호를 배열의 인덱스 값으로 쓰기에는 맞지 않다.

위 같은 문제를 해결하기 위한 것이 해시 함수이다.

해시 함수는 넓은 범위의 키 값을 좁은 범위로 변경해주는 역할을 한다.

그에 대한 간단한 예시를 확인하면

#include <stdio.h>

typedef struct _empInfo
{
    int empNum;
    int age;
} EmpInfo;

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

int main() {
    EmpInfo empInfoArr[100];

    EmpInfo emp1 = {20120003, 42};
    EmpInfo emp2 = {20130012, 33};
    EmpInfo emp3 = {20170049, 27};

    EmpInfo r1, r2, r3;

    // 키를 인덱스 값으로 이용해서 저장
    empInfoArr[GetHashValue(emp1.empNum)] = emp1;
    empInfoArr[GetHashValue(emp2.empNum)] = emp2;
    empInfoArr[GetHashValue(emp3.empNum)] = emp3;

    // 키를 인덱스 값으로 이용해서 탐색
    r1 = empInfoArr[GetHashValue(22120003)];
    r2 = empInfoArr[GetHashValue(20130012)];
    r3 = empInfoArr[GetHashValue(20170049)];

    // 탐색 결과 확인
    printf("사번 : %d, 나이 : %d \n", r1.empNum, r1.age);
    printf("사번 : %d, 나이 : %d \n", r2.empNum, r2.age);
    printf("사번 : %d, 나이 : %d \n", r3.empNum, r3.age);

    return 0;
}

위 코드에서는 직원의 고유번호가 총 8자리로 구성되어 있다. 이 키 값을 % 100을 통해 2자리 수로 변경해줬다.

지금은 쉽게 맨 뒤의 2자리만 추출해 이를 키값으로 사용하고 배열의 인덱스 값으로 사용했다.

하지만 또 여기서 문제는 직원수가 100명을 넘어 선다면 같은 키 값을 가지는 사람이 나오게 된다.

이러한 상황을 충돌(collision)이라고 하며, 이는 반드시 해결해야하는 문제이고 충돌의 해결방법에 따라 테이블의 구조가 달라지는 경우가 생긴다.

충돌의 해결은 테이블에서 필수불가결한 부분이다.

좋은 해시 함수의 조건

해시 함수는 좋은 해시 함수와 나쁜 해시 함수가 있다.

테이블에 메모리가 있다고 가정했을때 좋은 해시는 데이터가 테이블의 전체 영역에 골고루 분포되어있는 것이고 나쁜 해시는 반대로 특정 영역에 데이터가 몰려있는 것이다.

데이터가 골고루 분포되어 있으면 충돌 발생 가능성이 줄어들게되고, 반대로 데이터가 모여있으면 충돌 발생 가능성이 높아지게 된다.

좋은 해시 함수를 디자인하는 방법은 없다. 해시 함수는 데이터 키의 특성에 따라 달라지기 때문에 정석과 같은 방법은 없다.
하지만 일반적으로 가장 좋은 해시 함수를 만드는 방법은 키 전체를 참조해 해시 값을 만들어내는 것이 가장 좋은 방법이다.

자릿수 선택(Digit Selection), 자릿수 폴딩(Digit Folding)

일반적으로 해시 값을 생성할때, 특정 위치에 중복의 비율이 높거나, 공통적으로 들어가는 부분이 있다면 이를 제외한 나머지를 가지고 생성하는 것이 정석이다.

이와 유사한 방법으로 비트 추출 방식이 있다. 이는 탐색 키의 비트 열에서 일부를 추출 및 조합하는 방식이다.

자리수 폴딩이 있다. 폴딩은 말 그대로 접는다는 뜻으로 예를 들어 6자리 숫자 123456이 있다고 한다면 | 12 | 34 | 56 |으로 삼 등분 한 이후 각 두자리 수를 모두 더한 결과값 102가 해시 값이 된다.

이외에도 키를 제곱해 일부를 추출하는 방법, 폴딩 과정에 덧셈이 아닌 XOR 연산을 하는 방법, 둘 이상의 방법을 조합하는 방법 등 다양한 방법들이 있다.

해시 함수를 만들때는 키의 특성과 저장공간의 크기를 고려하는 것이 가장 선행해야 한다.

충돌

충돌은 테이블의 핵심주제라고도 할 수 있다. 충돌의 해결책은 어렵지 않다. 충돌이 발생하면 충돌이 발생한 자리를 대신할 빈 자리를 찾는 것이다. 단, 빈 자리를 찾는 방법에 따라 해결책이 구분된다.

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

충돌이 발생했을 때 옆 자리가 비었는지 확인하고, 만약 비었을 경우 그 자리에 대신 저장하는 방법이 선형 조사법이다.

예를 들어 서로 다른 key 값이 해시 함수를 통해 나온 해시값이 동일하다면, 충돌이 발생하게 된다. 해시값이 2라면 바로 옆인 인덱스 3을 확인하는 것이 선형조사법이다.

f(x)f(x)(해시값)에서 충돌한다면 f(x)+1f(x)+2f(x)+3f(x)+4f(x) + 1 \rightarrow f(x) + 2 \rightarrow f(x) + 3 \rightarrow f(x) + 4 \rightarrow \dots

이런 선형 조사법은 충돌 횟수가 증가함에 따라서 클러스터(cluster) 현상이 발생하는 단점이 있다.

클러스터(cluster) 현상: 데이터가 특정 영역에 집중적으로 몰리는 현상

이는 충돌 확률을 높이는 직접적인 원인이 된다.

선형 조사법의 단점을 극복하기 위해서 나온 것이 이차 조사법이다. 충돌 발생시 이차 조사법의 조사 순서는 아래와 같이 진행된다.

f(x)+12f(x)+22f(x)+32f(x)+42f(x) + 1^2 \rightarrow f(x) + 2^2 \rightarrow f(x) + 3^2 \rightarrow f(x) + 4^2 \rightarrow \dots

선형 조사법은 nn칸 옆을 확인하고, 이차 조사법은 n2n^2칸 옆을 확인한다.

이중 해시(Double Hash)

위 선형 조사법과 이차 조사법의 문제는 해시값이 같으면 충돌 발생시 빈 슬롯을 찾기 위해 접근하는 위치가 항상 동일하기 때문에 클러스터 발생 확률은 여전히 높다.

이는 빈 공간을 찾기 위한 방법이 규칙적이기 때문에 불규칙적으로 만든다는 생각에서 출발한다.

이중 해시는 이름 그대로 해시 함수를 두 개 사용하는 것이고, 하나의 해시 함수는 키를 근거로 저장 위치를 결정하고, 다른의 해시 함수는 충돌이 발생했을 때, 다른 공간을 확인할지 결정하는 것이다.

  • 1차 해시 함수 : 키를 근거로 저장위치를 결정
  • 2차 해시 함수 : 충돌 발생 시 몇 칸 뒤를 확인할지 결정

간단하게 이중 해시의 예시를 확인해본다.

  • 1차 해시 함수 : h1(k)=k  %  15h1(k) = k\; \% \; 15
  • 2차 해시 함수 : h2(k)=1+(k  %  c)h2(k) = 1+(k\; \% \;c)

1차 해시를 15로 나누는 것으로 배열의 길이가 15라고 한다면, 상수 C는 15보다 작으면서, 소수(prime number) 중 하나로 선택한다.

  • 1차 해시 함수 : h1(k)=k  %  15h1(k) = k\; \% \; 15
  • 2차 해시 함수 : h2(k)=1+(k  %  7)h2(k) = 1+(k\; \% \;7)

따라서 위와 같이 해시 함수를 정의할 수 있다.

2차 해시 함수에서 1을 더하는 것은 해시 값이 0이 되는 것을 방지하기 위해서 이ㅏㄷ.
또한 cc 값은 7이 아닌 15보다 작은 소수면 상관없다. c를 1차 해시 함수에서 나온 수 보다 작은 이유는 1차 해시의 최대값이 14인데, 2차 해시값이 14 이상이라면 빈 자리를 찾기위해 더 많이 돌아야 하기 때문에 매우 비효율적이다.

그리고 소수로 결정하는 이유는 클러스터 현상 발생 확률이 낮아진다는 통계가 있기 때문에

2차 해시값 예시

우선 1차 해시값이 전부 아래와 같이 동일하다면,

  • h1(3) = 3 % 15 = 3
  • h1(18) = 18 % 15 = 3
  • h1(33) = 33 % 15 = 3

키가 3인 데이터는 저장되고, 18, 33인 데이터를 저장할 때 충돌이 발생하게 된다. 이때 두 키를 2차 해시 함수로 계산한다면,

  • h2(18) = 1 + (18 % 7) = 5
  • h2(33) = 1 + (33 % 7) = 6

그리고 다음과 같이 진행된다

  • h2(18) -> h2(18) + 5 x 1 -> h2(18) + 5 x 2 -> h2(18) + 5 x 3
  • h2(33) -> h2(33) + 6 x 1 -> h2(33) + 6 x 2 -> h2(33) + 5 x 3

위 진행을 통해 클러스터 현상 발생 확률이 확실히 줄어드는 것을 알 수 있다. 실제로 이중 해시는 이상적인 충돌 해결책으로 알려져있다.

체이닝(Chaining)

앞의 충돌 해결법은 열린 어드레싱 방법(open addressing method)이라 하는데 이는 앞에서 봤듯이 충돌이 발생하면 다른 자리에 대신 저장한다는 의미가 있다.

하지만 체이닝과 같은 유형의 충돌 해결법은 닫힌 어드레싱 방법(closed addressing method)라고 한다. 이는 무슨 일이 있어도 자기 자리에 저장을 한다는 의미이다.

이는 무슨 일이 있어도 자기 자리에 저장하기 때문에 자리를 여러개 마련하는 방식으로 해결해야한다.

체이닝은 배열, 연결리스트를 이용하는 방법이 있는데,

배열을 기반으로 체이닝을 구현한다면,

위 그림과 같이 2차원 배열을 구성해서 구현할 수 있지만 만약 충돌이 발생하지 않을 경우 메모리 낭비가 심하다는 단점과 충돌의 최대 횟수가 정해져 있다는 문제가 있기 때문에 연결리스트를 이용해 구현한다.

위 그림처럼 슬롯을 생성해 연결 리스트로 연결해 나가는 방식으로 충돌을 해결하는 것이 체이닝 방법이다.

이는 탐색할 때 해시값에 모든 슬롯의 데이터를 모두 순회해야하는 단점이 있지만, 해시 함수를 잘 설정한다면 충돌이 적게 일어나 무리일 정도의 슬롯이 생기진 않아서 괜찮다.

profile
하루에 집중하자

0개의 댓글