해시테이블
해시테이블
{key, value}로 데이터를 저장하는 자료구조로 원하는 값을 빠르게 검색할 수 있는 자료구조이다. 이러한 속도가 가능한 이유는 해시테이블이 내부 적으로는 배열로 구현되어있고 이러한 배열에 엑세스할 수 있는 인덱스를 해시 함수를 통해 산출해내기 때문에 검색의 대부분의 경우는 매우 빠르다.
해시함수
입력값이 있을 때 함수 f에 넣었 을때 인덱스가 반환되는 함수 f를 해시 함수라고 부른다. 이러한 해시를 구하는 함수는 해시테이블의 성능에 관여하는 바가 크기 때문에 매우 중요한데 여러 방법 중 4가지만 아래에 설명해 보겠다.
1. Division method
입력 값을 테이블의 크기로 나눠서 사용하는 방법으로 주소 값은 입력값을 테이블 크기로 모듈러 연산해서 나오는 값을 사용하는 것이다. 테이블의 크기를 소수이자 2의 제곱꼴은 피하는게 좋다고 하는데 그 이유는 굉장히 합리적이다. 가령 테이블의 크기가 소수가 아닌 특정한 값 N이라고 가정해보자. 그럴 경우 입력값이 1,2,3,4,5… 같이 균등하게 들어오면 상관없이 균등하게 분배 되겠지만 그런 경우가 아니라 특정 값에 치중되게 입력값이 들어올 경우를 가정해볼 수 있다. 가령 2의 배수로 입력값이 들어온다고 가정해보자
1
2
k = 2,4,6,8 ...
N이 8일때 f(k) = 0, 2, 4, 6, 0, 2, 4, 6 ....
사실상 절반밖에 못쓰는 형태이다. 하지만 5와 같이 소수로 지정된다면 이야기는 다르다.
1
2
k = 2,4,6,8 ...
N이 5일때 f(k) = 2, 4, 1, 3, 0, 2, 4 ...
2의 배수로 데이터가 들어와도 5를 모듈러 연산 처리하면 꽤나 고르게 데이터가 분산된다. 이렇게 입력값이 고르지 않을 경우를 대비하여 소수를 쓰는 것이다.
2. Mid square
대상 입력 값을 제곱한 뒤 가운데 r 자리만 선택하는 방법이다. 여기서 r은 테이블의 크기에 따라 선택될 수 있다. 가령 예를 들어서 25를 Mid square로 해싱하는데 대상 테이블의 크기가 100이라고 가정해보자.
1
2
45^2 = 2,025
f(x) = 02
테이블의 크기가 100이라 0~99이므로 가운데 두 자리만 선정해서 02를 인덱스로 사용하는 방법이다.
3. Digit folding
각 자리 수를 더하여 인덱스를 얻는 방법으로 입력 값이 문자열일때 사용하면 좋다. 각 문자의 아스키코드나 유니코드 값을 모두 더한 데이터를 테이블의 주소로 사용하는 방법이다. 예를 들어 k값이 12345일때 테이블의 크기가 100이라고 가정하면 아래와 같이 구할 수 있다.
1
2
3
k = 11247
k1 = 11, k2 = 24, k3 = 7
f(k) = 11 + 24 + 7 = 42
4. Multiplication Method
숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 테이블 크기 m을 사용하여 다음과 같은 계산을 해준다.
1
h(k)=floor((kA % 1) × m)
이렇게보면 좀 헷갈릴 수 있으니 예시를 들어보겠다.
1
2
3
4
5
6
7
8
9
k = 112233
A = 0.22233
M = 100
f( 112233 ) = floor( 100 ( 112233 * 0.22233 % 1 ) )
= floor( 100 ( 24,952.76289 % 1 ) )
= floor( 100 ( 0.76289 ) )
= floor( 76.289 )
= 76
보통 m이 2의 제곱수인 이유는 곱셈의 용이성 때문인데 비트 시프트로 곱셈 연산을 처리하는게 효율적이기 때문이다.
해시 충돌 (collision)
아무리 해시 함수를 잘 만들었다고 해도 해시 충돌은 일어 날 수 밖에 없다. 그렇기 때문에 해시 충돌이 발생했을 때 이걸 어떻게 해결할지에 대한 것도 문제인데 이런 경우 대부분 아래의 두 가지 방법으로 해결하게 된다.
1. 분리 연결법(Separate Chaining)
동일한 인덱스에 접근하는 데이터를 다른 자료구조를 통해서 연결해서 관리하는 방법을 분리 연결법이라고 하는데 단순히 연결리스트를 이용해서 순차 검색하게끔 연결해둔 경우도 있지만 java의 경우 검색 상의 성능을 위해 자가 균형 이진 검색 트리로 구성해두었듯이 임의의 자료 구조를 통해 처리할 수도 있다.
2. 개방 주소법(Open Addressing)
분리 연결법과는 다르게 추가적인 데이터를 쓰지 않고 비어있는 곳을 이용하여 데이터를 넣는 방법인데 대부분 아래와 같은 세가지 방법을 사용한다.
1) Linear Probing
충돌이 난 인덱스 지점부터 순차적으로 인덱스를 고정된 값만큼 올려가며 빈 곳을 찾아 넣는 방법이다.
2) Quadratic Probing
충돌이 난 인덱스 지점부터 저장순서 폭을 제곱으로 더하여 순차적으로 빈 곳을 찾아 넣는 방법이다.
1
ex) 1, 2^2, 3^2
3) Double Hashing Probing
해싱된 값을 다시 해싱을 하여 새로 인덱스를 산출하는 방법이다.
적재 밀도
해시 충돌은 적재 밀도에 따라 빈도가 달라진다. 적재 밀도란 아래와 같은 수식으로 산출 할 수 있다.
1
적재밀도 = 입력된 원소의 수/테이블의 크기
적재 밀도에 따라 평균적으로 home address(첫번째 해싱 위치)에 적재되지 못하는 비율은 아래와 같다.
| 적재 밀도 | home address 에 적재되지 못하는 비율 |
| 10% | 4.8% |
| 20% | 9.4% |
| 30% | 13.6% |
| 40% | 17.6% |
| 50% | 21.4% |
| 60% | 24.8% |
| 70% | 28.1% |
| 80% | 31.2% |
| 90% | 34.1% |
| 100% | 36.8% |
따라서 적재밀도가 높아진다면 해시테이블의 크기를 더욱 크게 하여 원래 테이블에서 옮기는 작업이 필요하다.
해시 테이블에서의 값 삭제
분리 연결법에서는 연결된 리스트나 Tree에서 해당 값을 삭제해버리면 되니까 크게 문제될건 없다. 연결된게 list라면 최대 시간 복잡도는 O(N)일 것이고 Tree라면 O(logN)일 것이다.
하지만 개방 주소법이라면 이야기가 조금 달라진다. 이런 경우 삭제법은 두 가지다
데이터 삭제 후 재배치
데이터만 삭제해버리면 이전에 충돌이 일어나서 다른 곳의 배치된 데이터는 찾을 수 없게된다. 그렇기 때문에 데이터 삭제 후에 충돌이 일어나서 다른 곳에 배치된 데이터는 없는지 찾은 후 재배치를 해야한다.
데이터 삭제 후 Tombstone 배치
위의 방법 같이 재배치를 할 경우 여차하면 너무 큰 연산이 들 가능성이 있다. 그래서 삭제 후에 삭제되었다는 표기(Tombstone)만 해두고 차후 해당 위치에 쓸 일이 있을 때 쓸 수 있게끔 혀용하는 방법이 있는데 당장은 매우 좋아보이지만 이러한 Tombstone이 너무 많아질 경우 검색간 지연이 발생하게 된다. (Tombstone으로 인해 다른 곳들도 확인해 봐야하므로)
때문제 일정 Tombstone 개수가 넘어가게 된다면 이 방법 역시 재배치가 필요하다.
참고 자료
- R.Sedgewick and K. Wayne, Algorithms (4th Ed.), Addioson-Wesley.
- E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, Silicon Press, 2nd Edition.
- MangKyu’s Diary:티스토리