전형준

해시테이블이란?

데이터를 담을 테이블을 미리 크게 확보해놓은 후 입력 받은 데이터를 해싱하여 테이블 내 주소를 계산하고 이 주소에 데이터를 담는 것.

해시 함수란?

테이블 내의 주소를 계산하는 계산식이나 방법론

1.나눗셈법

설명

주소 = 입력값 % 테이블의 크기
보통 테이블의 크기는 소수를 쓰는 것이 공간을 효율적으로 사용할 수 있다.
특히 2의 제곱수와 거리가 먼 소수를 사용하는 해시 함수가 좋은 성능을 낸다. ex) 193

충돌(collision)

서로 다른 입력값에 대해서 해시함수의 출력인 해시값이 동일할 수 있다. 즉 입력주소가 같을 수 있으며, 이 경우를 충돌(collision)이라고한다.

클러스터(cluster)

똑같은 해시값이 아니더라도 헤시 테이블 내 일부 지역의 주소들을 집중적으로 반환함으로써 데이터가 한 곳에 모이는 문제인 클러스터 가 발생할 가능성이 높다.

자릿수 접기 (Digits Folding)

숫자를 종이를 접듯이 숫자를 접어 일정한 크기 이하의 수로 만드는 방법 ex) 8129335

각 자릿 수를 모두 더한다. 31 = 8 + 1 + 2 + 9 + 3 + 3 + 5
- 이렇게 큰 숫자가 31이라는 숫자로 접힌다.
두 자리 씩 모두 더한다. 148 = 81 + 29 + 33 + 5
위의 두가지 방법 모두 일정한 범위 내의 해시값을 가질 수 있다.
- 첫번째는 9 * 7 = 63가지의 해시값을 가질 수 있음
- 두번째는 99 * 3 + 9 = 306개의 해시값을 가질 수 있음.
이 자릿수 접기는 문자열을 키로 사용하는 해시 테이블에 특히 잘 어울리는 알고리즘이다. 문자열의 각 요소를 해시 테이블로 바꾸고, 이 값을 각각 더해서 접으면 문자열을 깔끔하게 해시 테이블의 주소로 바꿀 수 있기 때문이다.

기본 알고리즘의 문제점

12289크기의 해시 테이블에서 10자리 글자를 각각 128개의 아스키 숫자중에 하나로 나타낸다고 하자.
그것에 대한 경우의 수는 127^10 = 1.091533853×10²¹이다.
그러나 해시값이 나올 수 있는 것은 최대 127 * 10 = 1270이다. 즉 collision이 너무나도 많이 생기게되며 테이블에서 10퍼센트만 사용하게된다.
해결책은 해시값을 이진수로 나타내는 것이다.
- 이 해시값은 이진수로 나타내면, 11개의 비트만 사용한다. 즉 전체 14비트(12289 크기) 중에서 앞에서 3개의 비트는 쓰지 않는다.
- 그래서 아래와 같이 아스키 코드를 3칸씩 shift연산을 하고, 각 자릿수를 더하는 방식을 취한다.

int Hash(char* key, int KeyLength, int TableSize)
{
  int i = 0;
  int HashValue = 0;
  for (i = 0; i < KeyLength; i++) {
    HashValue = (HashValue << 3) + Key[i];
  }

  return HashValue % TableSize;
}

충돌을 막는 방법

충돌을 해결하는 방법은 크게 두 가지가 있다.

개방 해싱(Open Hashing)
폐쇄 해싱(Closed Hashing)

개방 해싱

해시 테이블 주소 바깥에 새로운 공간을 할당하여 문제를 수습하는 것
- ex) 체이닝
처음에 주어진 해시 테이블의 공간 안에서 문제를 해결하는 것

체이닝 (Chaining)

충돌 시 해당 해당주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 것
테이블은 데이터를 저장하고 있는 것이 아닌 링크드 리스트에 대한 포인터를 저장하고 있는다.
삽입연산은 앞으로의 충돌을 고려해서 설계한다.
삭제 연산과 탐색 연산은 이미 발생한 충돌을 고려해서 설계되어야한다.
성능향상 방법
- 원하는 데이터를 찾기 위해서는 순차 탐색 방법을 선택해야한다.
- 그래서 이진탐색 트리를 섞는 것이 때로는 좋을 수 있다.

개방 주소법 (Open Addressing)

충돌이 일어날 때 해시 함수에 의해 만들어진 주소가 아니더라도 얼마든지 다른 주소를 사용할 수 있도록 허용하는 충돌 해결 알고리즘
개방 주소법은 새로운 주소를 탐사(probe)가 중요하다.

개방 주소를 위한 탐사(probe) 방법론

선형 탐사(Linear probing)
- 해시 함수로부터 얻어낸 주소에 이미 다른 데이터가 입력되어 있을 경우 현재 주소에서 고정 폭으로 주소를 이동
- 그 주소에 다른 데이터가 있어 충돌이 발생하면 또 그다음 주소로 이동한다.
- 선형 탐사를 쓰다 보면 충돌할 뻔한 데이터들이 한 곳에 모이는 클러스터 현상이 많이 발생함.
- 클러스터 현상이 발생하면 새로운 주소를 찾기 위해 수행하는 선형 탐사시간이 길어지고, 해시테이블의 성능도 저하된다.
제곱 탐사
- 선형탐사와 달리 이동 폭이 제곱수로 늘어난다.
- 충돌 발생시 1, 4, 9.. 순서대로 더해가면서 충돌여부를 검사한다.
- 하지만 클러스터가 발생할 수 있음
  - 이유는 하나의 주소에서 충돌이 발생할 때 탐사할 위치가 정해져있기 때문이다.
  - 그래서 같은 해시값을 가진 데이터에 대해서는 2차 클러스터(해시테이블의 크기를 넘어서 주소에서 다시 만남)
이중해싱
- 클러스터를 제대로 방지할 수 있는 방법은 탐사할 주소의 규칙성을 없애는 것뿐이다.
- 이동폭을 다른 해시함수로 계산하는 방법이 있다.(하나의 해시함수를 추가한다)
- 이러한 방식은 탐사 이동폭의 규칙성은 없애면서도 같은 키에 대해서는 항상 똑같은 결과를 얻을 수 있다.
재해싱
- 남은 공간이 거의 없는 해시 테이블에서는 연쇄 충돌이 자주일어난다.
- 재해싱(rehashing)은 이 문제를 해결하는 방법 중 하나이다.
- 이것은 해시 테이블의 크기를 늘리고 늘어난 해시 테이블의 크기에 맞춰 테이블 내의 모든 데이터를 다시 해싱한다.
- 통계적으로 해시 테이블의 공간 사용률이 70%~80%에 이르면 성능 저하가 나타나기 시작한다.
- 그러므로 공간 사용률이 이보다 적은 수준일 때 미리 재해싱해둬야 성능저하를 막을 수 있다.
- 하지만 오버헤드가 꽤 높은 기법이기 때문에, 78%일 때가 적절하다.

최종수정일 : 2023년 10월 28일