[자료구조 C 언어] C 프로그래밍 자료구조 - 21 : 해싱 (Hasing)

하하

 

날아갔어요

 

다시 쓰는 해싱입니다.

 

자료구조의 마지막 단계입니다.

 

이후에는 파이썬으로 다이나믹 프로그래밍이나 강화학습, 오픈 CV를 활용한 이미지 인식 등을 함께 공부해보겠습니다.

 

이전까지 배운 모든 탐색 및 정렬 방법은 데이터 값 (키 값)을 직접적으로 이용해서 탐색하고자 하는 항목에 접급했습니다.

 

해싱은 키 값에 산술적인 연산을 한 뒤, 연산 결과를 해시 테이블의 주소 (해시 테이블 배열의 인덱스)로 정합니다.

 

키 값에 산술적인 연산을 하여 만들어진 주소와 해시 테이블을 이용해 탐색하는 것이 바로 '해싱' 입니다.

 

EX)

본래 데이터가 [4, 6, 9]이 있다고 합시다.

 

산술적인 연산은 데이터 값 % 4 로 설정하겠습니다.

 

연산 결과는 [0, 2, 1]로 계산됩니다.

 

해시 테이블은 배열 형식으로 초기화 됩니다. --> ht[]

 

연산 결과와 해시 테이블 ht는 다음과 같이 정리됩니다.

 

h[0] = 4

h[1] = 9

h[2] = 6

 

해싱을 사용하면 0을 사용하면, 해시 테이블에서 4를 반환 받을 수 있습니다.

 

예시와 같이 설정된 해시 테이블의 주소 (해시 테이블 배열의 인덱스)와 해시 테이블을 사용하여 데이터를 정렬하고 탐색하는 것을 해싱이라고 합니다.

 

 

 

1. 해싱의 구조

 

 

사전구조 (dictionary): 맵 (map)이나 테이블 (table)로 불리우기도 합니다.

 

사전구조는 다음과 같이 두 종류의 필드를 가집니다.

 

1) 탐색 키 (search key): 영어 단어나 사람의 이름과 같은 데이터

2) 값 (value): 단어의 정의나 사람의 전화번호와 같은 탐색 키와 관련된 데이터

 

즉, 전화번호부에서 (김뭉뭉 = 010-1111-2222)이 있을 때

 

탐색 키는 김뭉뭉, 값은 010-1111-2222입니다.

 

해시 함수 (hash function): 탐색 키를 입력으로 받아 해시 주소 (hash address)를 생성합니다.

해시 테이블 (hash table): 배열에 해시 주소를 인덱스로 한 값을 저장하고 있습니다.

 

 

 

 

2. 해시 테이블의 구조

 

해시 테이블 배열의 이름을 ht라고 하겠습니다.

 

ht는 M개의 버켓 (bucket: row와 같습니다.)으로 이루어져있습니다.

 

각각의 버켓을 s개의 슬롯 (slot)을 가집니다.

해시 테이블은 탐색 값을 해시 함수를 이용해 재정의 하기 때문에 서로 다른 데이터가 동일한 탐색 값을 가질 수 있습니다.

 

이러한 경우를 '충돌 (collision)'이라고 합니다.

 

충돌이 일어나면 버켓의 빈 슬롯을 찾아 값을 저장해 줄 수 있는데, 충돌의 발생 횟수가 버켓에 할당된 슬롯 보다 많아질 수 있습니다.

 

이러한 경우를 '오버플로우 (overflow)'라고 합니다.

 

해시를 적절히 사용하기 위해선, 충돌과 오버플로우를 해결할 수 있는 방법이 반드시 필요합니다.

 

EX)

가장 기본적인 해시 함수는 탐색 키 (k)를 해시 테이블의 크기 (M)로 나눈 나머지를 해시 테이블의 주소로 삼는 것입니다.

 

i = k % M;

ht(i) = 탐색 키와 관련된 값

 

k1 = 5, k2 = 9 라면 i1 = 1, i2 = 1이 되어 두 탐색 키의 해시 테이블 주소가 충돌합니다.

 

좋은 해시의 조건은 다음과 같습니다.

 

1) 충돌이 적다.

2) 해시 함수의 결과 값 (해시 테이블의 주소)이 해시 테이블 영역 내에서 고르게 분포되어야 한다.

3) 계산이 빨라야 한다.

 

 

 

3. 해시 함수의 종류

 

1) 제산 함수

 

나머지 연산자 (mod)를 사용하여 탐색 키를 해시 테이블의 크기로 나눈 나머지를 이용하는 방법입니다.

 

해시 테이블의 주소를 저장하는 배열을 hi라고 할 때, 다음과 같습니다.

 

hi(k) = k % M;

(k = 탐색 키, M = 해시 테이블의 크기 -> 이후 모든 함수에서 동일합니다.)

 

 

2) 폴딩 함수

 

탐색 키가 해시 테이블의 크기보다 더 큰 정수일 경우에 사용합니다.

 

탐색 키를 분할한 뒤 분할된 각 부분을 더하거나 XOR 등을 이용한 부울 연산을 하는 방법입니다.

 

폴딩 함수는 두가지 종류로 나뉘어 집니다.

 

  1] 이동 폴딩: 탐색 키를 여러 부분으로 나눈 값들을 더하거나 부울 연산을 합니다.

  2] 경계 폴딩: 여러 부분으로 나뉘어진 탐색 키의 두 값의 이음 부분을 역으로 정렬하여 더하거나 부울 연산을 합니다.

 

 

 

3) 중간 제곱 함수

 

탐색 키를 제곱한 다음, 중간의 몇 개의 비트만 추출하여 해시 테이블의 주소로 사용합니다.

 

제곱한 값들은 탐색 키의 모든 문자와 관련되 있기 때문에 서로 다른 탐색 키는 몇 개의 문자가 같을 순 있어도, 서로 다른 해싱 주소를 갖게 된다고 합니다

 

하지만, 이 방법도 반드시 중복은 됩니다.

 

 

4) 비트 추출 방법

 

해시 테이블의 크기가 M = 2^k 일 때 탐색 키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시 주소로 사용하는 것입니다.

 

즉, M = 2^4고 탐색 키가 [12, 14, 25, 65]로 제시됐다고 가정하겠습니다.

 

12 (10) = 1100 (2)

14 (10) = 1110 (2)

25 (10) = 11100 (2)

65 (10) = 1000001 (2)

 

임의의 위치는 2진수 변환 값의 맨 마지막 자리부터 4자리로 하겠습니다.

 

그럼 해시 함수로 계산된 탐색 키의 해시 테이블 주소값은 다음과 같습니다.

 

12 => 1100

14 => 1110

25 => 1100

65 => 0001

 

벌써 12와 25의 해시 테이블 주소 값이 충돌한 것을 확인할 수 있습니다.

 

이처럼 탐색 키의 일부 정보만을 사용하므로 해시 테이블 주소의 집중 현상이 일어날 가능성이 높은 방법입니다.

 

5) 숫자 분석 방법

 

탐색 키의 각각의 위치에 있는 숫자 중에 편중되지 않는 수들을 해시 테이블의 크기에 적합한 만큼 조합하여 해시 주소로 사용하는 방법이라고 합니다.

 

예로는 학번이 있습니다.

 

6) 탐색 키가 문자인 경우

 

탐색 키가 문자인 경우에는 문자 자체에 순서대로 숫자를 할당하거나 (a~z -> 1~26)

 

문자의 아스키 코드나 유니 코드 값을 사용하는 방법 등이 있습니다.

 

즉, 문자를 숫자로 치환한 뒤에는 위에서 설명한 여러 해시 함수들을 동일하게 적용할 수 있습니다.

 

문자는 cup, puc, cpu와 같이 다양한 조합에서 동일한 철자를 가진 단어가 많기 때문에 충돌에 더욱 취약합니다.

 

따라서 아스키 코드로 문자를 변환했을 때, 문자의 값 위치에 따라 가중치를 부과하여 더하거나 부울 연산 하는 등의 방법도 사용될 수 있습니다.

 

EX)

c = 1, u = 2, p = 3으로 가정하겠습니다.

 

각 문자에 할당된 숫자를 더하는 해시 함수를 쓴다면, (c, u, p)를 사용하는 모든 단어의 해시 테이블 주소는 '6'으로 통일됩니다

 

하지만, 문자의 위치에 따라 가중치를 부과한다면 다음과 같은 결과가 나옵니다.

 

c u p = 1*2^1 + 2*2^2 + 3*2^3 == 2 + 8 + 81 = 91

p u c = 3*2^1 + 2*2^2 + 1*2^3 == 6 + 8 + 27 = 41

c p u = 1*2^1 + 3*2^2 + 2*2^3 == 2 + 12 + 16 = 30

 

가중치를 부과하는 기준은 설명 안 드려도 되겠죠?

 

 

 

4. 충돌 해결책

 

충돌은 서로 다른 탐색 키가 해시 함수를 거쳤을 때, 동일한 해시 테이블 주소 값을 갖는 것을 현상입니다.

 

충돌을 해결하기 위한 방법은 크게 다음 두 가지로 대표됩니다.

 

1) 선형 조사법 (linear probing): 충돌이 일어난 항목을 해시 테이블의 비어있는 공간에 저장합니다.

2) 체이닝 (chaining): 해시 테이블 내 하나의 공간이 여러 항목을 저장할 수 있도록 해시 테이블의 구조를 변경합니다.

 

 

1) 선형 조사법

 

특정 버켓에서 충돌이 일어나면 해시 테이블의 빈 버켓을 찾는 방법입니다.

 

조사 (probing): 해시 테이블의 빈 공간을 찾는 것입니다.

 

조사를 하는 방법에 따라 효율이 달라지게 됩니다.

 

선형 조사법의 조사 방법은 다음과 같습니다.

 

  1] 해시 테이블 배열 ht의 k번 째에서 충돌이 일어났다면, k+1번 째가 비었는 지 조사합니다.

 

  2] 만약, 비어있다면 해당 위치에 값을 저장합니다.

 

  3] 비어있지 않다면 k+2번 째 공간을 조사합니다.

 

  4] 테이블의 끝에 도달하면 다시 1번 째 공간으로 돌아갑니다.

 

  5] 처음 출발했던 위치로 돌아오면 해당 버켓이 가득찬 것으로 판단합니다.

 

 

 

선형 조사법은 간단하다는 장점 있습니다

 

하지만, 오버플로우가 자주 발생하면 집중과 결합에 의해 효율이 크게 저하될 수 있습니다.

 

계속 같은 자리부터 하나씩 조사하게 되는 경우가 그렇죠..

 

어차피 없는거 아는데 어쩔 수 없이 다시 조사를 반복하는 경우를 말합니다.

 

 

2) 이차 조사법 (quadratic probing)

 

이차 조사법은 선형 조사법과 유사하지만, 조사할 위치를 다음 식에 의하여 결정합니다.

 

(h(k) + i * i) % M

 

따라서 조사되는 위치는 다음과 같이 됩니다

 

h(k)  ->  h(k) + 1*1  ->  h(k) + 2*2  -> ....

 

선형 조사법의 문제점인 집중과 결합을 크게 완화해줄 수 있습니다.

 

 

3) 이중 해싱법 (double hasing) or 재해싱 (rehasing)

 

오버플로우가 발생할 때, 다음 저장 위치를 결정하는 방법을 원래 해시 함수가 아닌 다른 해시 함수를 사용하는 방법입니다.

 

두가지 예시를 알아보겠습니다.

 

  1] 탐색 키를 참조하여 h(k) + a 의 a가 결정된다.

      => 해시 함수의 결과 값이 같아도 탐색 키가 다르면 서로 다른 조사 순서를 갖습니다. (이차 집중을 피할 수 있다.)

 

  2] 조사 간격을 결정하는 방법을 설정합니다.

      => step = C - (k % C)

      => h(k)  ->  h(k) + step  ->  h(k) + 2 * step  ->  ....

 

EX)

크기가 7인 해시 테이블을 가정합니다.

 

이때, 해시 함수가 h(k) = k % M이고, 오버플로우 발생 시 step = 5 - (k % 5)인 경우를 확인해 보겠습니다.

 

 

4) 체이닝

 

체이닝은 오버플로우 문제를 연결 리스트로 해결합니다.

 

각 버켓에 삽입과 삭제가 가능한 연결 리스트를 할당합니다.

 

충돌되면 단순히 연결리스트를 이용해 원래 있던 값을 한칸 뒤로 미뤄주고, 그 앞에 새로 들어온 값을 저장한 뒤에

 

새로 들어온 값의 링크를 원래 있던 값에 연결해줍니다

 

값을 갯수 제한없이 저장할 수 있지만, 해싱에서 굳이 인덱스를 해시 함수를 사용해서 단순화 시킨 보람이 없어집니다.

 

원하는 데이터를 검색하려면 해시 테이블 주소로 해당 위치를 참조한 뒤 연결 리스트를 하나씩 조사해줘야 합니다.

 

EX)

크기가 7인 해시테이블을 가정합니다

.

이때, 해시 함수는 h(k) = k % 7이고 입력 데이터는 8, 1, 9, 6, 13 입니다.