[알고리즘] 해시 테이블

Huko·2023년 3월 16일
0

알고리즘

목록 보기
4/11

해시 테이블은 (Key, Value)로 데이터를 테이블 형태로 저장하는 자료구조이다.

해시 테이블은 Key값에 해시함수를 적용해 배열의 고유한 Index를 생성하고, 이 Index를 이용하여 값을 저장하거나 검색한다.

실제 값이 저장되는 장소를 버킷 or 슬롯이라고 한다.

1. 생성

해시 함수는 두 가지 중요한 성질을 가지는데

  1. 입력 원소가 해시 테이블 전체에 고루 저장되어야한다.

  2. 계산이 간단해야한다.

1번은 Index가 한곳에 몰려 있다면 한 주소를 놓고 충돌할 확률이 작아지기 때문이고, 2번은 값 계산 자체가 복잡해서 시간 복잡도를 키우면 해시 테이블 사용 자체에 의미가 없어지기 때문이다.

이런 부분을 만족하면서 해시 함수를 만드는 대표적인 방법2가지를 간단하게 설명할 것이다.

책에서는 2가지지만 나왔지만 찾아보면 총 4가지 방법이 있다.

1-1. Division Method

m의 크기를 가진 해시 테이블에 값을 저장한다 하면

Index = hash_function(Key) mod m

위와 같이 Key값에 해시 한 후 해시 테이블의 크기를 mod 연산 한 후 그 Index에 Value값을 저장한다.

HashTable[Index] = Value

1-2 Multiplication Method

입력값을 0과 1사이의 소수로 대응시킨 다음 해시 테이블 크기 m을 곱하여 0부터 m-1사이로 팽창시킨다.

  1. 숫자로 된 Key값에 0과 1사이의 소수 A를 곱한다음 mod 1을 통해 정수 부분을 버리고 소수 부분만을 얻는다.

  2. 그 후 해시 테이블 크기 m을 곱하여 그 정수부분을 Index로 정한다.

*m은 보통 2의 제곱수이다.

h(x) = [m(xA mod 1)]

2. 해시(Hash)충돌

Index를 정하는 부분을 배웠다면 이제 한가지 의문이 생길 수 있다.

그것은 바로 Index의 중복이다.

해시의 성질상 같은 해시 값이 나오는 경우는 거의 불가능에 가깝지만 여기에 연산을 더하거나 때로는 해시 자체의 충돌이 있어서 같은 Index값을 가지는 경우가 생길 수 있다.

이런 문제를 해시충돌이라고 하는데 이를 해결하기 위한 2가지 아이디어가 있다.

1. 체이닝(Chaining)

같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트에 매달아서 관리하는 방법이다.

하지만 Index가 같은 값을 중복해서만 가지고 비어 있는 테이블이 많아지면 비효율적이다.

그리고 추가적인 공간을 사용해야하고 그에 따른 링크드 리스트를 관리해야한다.

2. 개방 주소 방법(Open Addressing)

개방 주소 방법은 체이닝과 같이 추가 공간을 허용하지 않는다.

2-1. 선형 조사(Linear Probing)

가장 간단한 충돌 해결 방법으로 충돌이 일어난 바로 뒷자리를 보는 방법이다.

즉 넣을려는 자리에 값이 있으면 그 다음 그 다음에도 있으면 그 다음 이런식으로 값을 대입한다.

h(x) = (h(x) + i) mod m

2-2. 이차원 조사(Quadratic Probing)

선형조사가 저장순서 폭을 고정했다면 이차원 조사는 그 넒여가는 폭을 지속적으로 증가시켜주는 방식이다. 이로써 군집화를 피할 수 있다.

h(x) = (h(x) + c1 i**2 + c2 i) mod m

2-3 이중 해싱(Double Hashing)

Double Hashing은 이름 그대로 해시함수를 두개를 사용한다.

충돌이 발생하면 다음 폭의 공간을 전혀 다른 Hash를 사용하여 더해서 계산한다.

첫번째 Hash값이 같더라도 두번째 Hash값이 같을 가능성이 아주 작기 때문이다.

h(x) = (h(x) + i * f(x)) mod m

이중 해싱에서 권장하는 방법은

h(x) = x mod m으로 잡고 m보다 조금 작은 소수 m'에 대해 f(x) = 1 + (x mod m')으로 잡는 것이다.

EX) m = 1601이라 할 때, m' = 1597으로 잡으면 원소 x = 10025에 대해 h(10025) = 149, f(10025) = 444가 되어 조사 순서는

419 -> (419 + 444) mod 1601 - > (419 + 2*444) mod 1601 -> ...

이 된다.

y = 8424에 대해 조사 순서를 보자면

h(8424) = 419로 위와 동일하지만 f(8424) = 440이 되어 조사 순서는

419 -> (419 + 440) mod 1601 -> (419 2*440) mod 1601

이 된다.

h(x) == h(y)이지만

f(x) != f(y)이 된다.

3. 해시 삭제(Hash Delete)

해시 삭제 시 주의해야 할 점이 있다.

중간에 값을 삭제만 해버리면 값을 검색(Search)할 때 문제가 생길 수 있는 것이다.

이것은 간단하게 값을 삭제하고 그 자리에 표식을 해두면 해결되는 문제이다.

4. 값 검색(Search)

4-1. 체이닝의 경우

적재율 α
해시 테이블 전체에서 얼마나 원소가 차 있는지를 의미.

α = n / m (n은 테이블에 있는 원소의 갯수, m은 테이블 크기)

성공하는 검색에서 조사 횟수의 기대치는 아래와 같다.

(1 + α)/2 + α/2n

4-2. 개방주소 경우

가정
조사순서 h0(x), h1(x), ... , hm-1(x)가 0부터 m-1사이의 수로 이루어진 순열을 이루고, 모든 순열은 같은 확률로 일어난다.

정리1
적재율 α = n/m 인 개방주소 해싱에서 실패하는 검색에서 조사횟수의 기대치는 최대 1/(1 - α)이다.

정리2
적재율 α = n/m인 개방주소 해싱에서 성공하는 검색에서 조사횟수의 기대치는 최대 (1/α)log(1/(1-α))이다.

5. 적재율이 높아지는 경우

적재율이 높아지면 일반적으로 해시 테이블의 효율이 떨어진다.
일반적으로, 임계값을 미리 설정해 놓고 적재율이 이에 이르면 해시 테이블의 크기를 두 배로 늘린 다음 해시 테이블에 저장되어 있는 모든 원소를 다시 해싱하여 저장한다.

profile
iOS 개발자 지망생

0개의 댓글