해시

정의

임의의 길이의 데이터(Key)를 해시함수를 통해 매핑된 고유의 데이터

구현방법

key → 함수 → 해시

해시함수

key 데이터를 고유한 데이터로 바꿔주는 함수

1. Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
2. Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
3. Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kAmod1) × m
4. Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

시간복잡도

key와 hash 검색과 삭제가 O(1)의 시간복잡도를 갖게된다

충돌

데이터가 많아지다보면 서로 다른 key가 같은 해시값을 갖는데 이를 충돌이라고 한다

해시테이블

정의

해시함수를 사용하여 key 해시값으로 매핑하고 해시값을 index 삼아 bucket에 값을 함께 저장하는 자료구조(reference를 저장하여 entry 생성)

구현방법

Key → hash function → Hash → Bucket(value)

시간복잡도

해시테이블은 해시 충돌이 일어나지 않는다는 가정하에 삽입, 삭제, 검색에 O(1)의 시간복잡도를 가지고

충돌이 일어나면 최악의 경우 O(n)의 시간 복잡도를 갖는다

해시테이블의 종류

해시테이블은 충돌을 막기위해 다양한 알고리즘을 해시 테이블에 적용하여 충돌을 피한다.

크게 두가지로 볼 수 있는데 체이닝, 직접주소개방

어떤 해시 충돌 알고리즘을 사용하냐에 따라 삽입연산 구현방법과 삭제연산도 맞게 구현해야한다

체이닝

체이닝 방법은 동일한 해시 값을 갖는 key를 다른 버킷에 넣는 것이 아니라 동일한 버킷에 연결리스트 형식으로 연결하는 방법이다.

가장 간단하지만 하나의 해시값에 여러 엔트리가 몰릴수 있다.

그렇게 되면 리스트처럼 선형구조를 갖는 것이라 최악의 경우 하나의 데이터를 찾는데 최대한 빠른시간이 아닌 O(n)의 시간복잡도를 가질 수 있음.

→ 해시테이블의 장점이 퇴색됨

해결방법

1. 비선형적 구조로 entry 저장하기
   충돌시 엔트리를 Red-Black Tree의 형태로 저장하면 O(logN)의 시간복잡도를 갖기때문에 좀더 효율적으로 구축할수 있다.
2. 버킷의 크기 동적으로 늘리기
   적재율이 일정 수준이상으로 올라가면 동적으로 bucket의 크기를 늘리면서 충돌을 완화할 수 있다.

직접 주소 개방(Open-Addressing)

해시충돌 발생시 다른 보조함수를 이용하여 빈버킷의 공간을 찾아 데이터를 저장하는 방식

bucket과 entry가 항상 1:1 대응 관계를 유지할 수 있어 빠른 탐색의 장점을 갖는다

해시함수의 결과에 Mod(나머지 연산)을 적용하여 bucket의 크기보다 index가 커지는 것을 방지

bucket의 크기도 소수로 해야 함수의 반환값이 편향되어도 mod 잏의 값이 고르게 분포된어 충돌 가능성을 낮춘다

한계

• 삭제 연산이 추가적인 보조 함수를 사용하여 복잡
• 해시함수+보조함수로 인해 전체 해시테이블 속도가 크게 달라짐

→ 보조 해시 함수에 따라 선형조사법, 이차조사법, 이중해싱법 세가지로 나뉜다

1. 선형 조사법(Linear Probing)

선형 조사법의 보조함수는 충돌 발생시 기존 해시값에 +1을 더하는 함수

충돌이 발생하지 않을때까지 +1을 반복하여 저장한다. 단, 충돌한 데이터와 같은 hash 값을 갖는다.

충돌 시: bucket의 크기는 7, key값 8에 대해 해시 값 10(h(8) = 10)이라고 가정

1. h(8) mod 7 = 10 mod 7 = 3 // 충돌 발생 가정
2. (h(8) + 1) mod 7 = 11 mod 7 = 4 //또 충돌 발생 가정
3. (h(8) + 2) mod 7 = 12 mod 7 = 5 // 저장

한계

• 군집화로 인해 빈번한 선형적 접근발생

해시 충돌이 한곳으로 집중되어 해당 index를 중심으로 군집화가 발생하면 처음 해시값을 찾아 하나씩 index를 더해가면서 찾아야 해서 결과적으로 배열과 유사한 구조를 갖게되어 빠른 탐색의 장점이 사라진다.

2. 이차 조사법(Quadratic Probing)

선형조사가 갖는 군집화를 해결하고자 나타난 방법.

+1이 아닌 상수 제곱 값을 더하여 군집화를 방지

충돌 시: bucket의 크기는 7, key값 8에 대해 해시 값 10(h(8) = 10)이라고 가정

1. h(8) mod 7 = 10 mod 7 = 3 // 충돌 발생 가정
2. (h(8) + 1^2) mod 7 = 11 mod 7 = 4 //또 충돌 발생 가정
3. (h(8) + 2^2) mod 7 = 14 mod 7 = 0 // 또 충돌 발생 가정
4. (h(8) + 3^2) mod 7 = 19 mod 7 = 5 // 저장

한계

• 약한 군집화 존재
• bucket에 공간이 있어도 내지 못할수 있음(^2값이 커지면서)

이중 해싱법(Double Hasing)

두가지 보조 해시함수를 적용하여 군집화를 해결하고 값이 커지면서 공간을 못찾는 문제 해결

한계: 추가 연산이 있어 함수의 성능이 테이블 성능에 영향을 미칠 수 있다.

해시테이블의 탐색과 삭제

탐색

일반적으로 해시값에 대응된 bucket으로 접근하지만

충돌이 있는경우 알고리즘 규칙에 따라서 해시값이 동일한 bucket 중 찾고자 하는 key를 저장한 entry를 찾아 bucket을 탐색한다.

이때 Null값이 있다면 해당key에 해시테이블이 없으므로 탐색을 종료

chaining의 경우 리스트 규칙에 따라

직접 개방 주소의 경우 보조 해시함수를 규칙에 따라

→ 이때문에 O(n)까지 증가 할수 있다

삭제

탐색 연산과 거의 같다. 해당값을 탐색하고 Null 값으로 만들면됨

삭제하는 것이 아니라 충돌 해결 알고리즘에 맞게 bucket의 저장된 값을 적절하게 재배치하는 것

bucket을 지워버리면 탐색을 할 수 없는 자료구조가 되어버림

체이닝

chaining의 경우 연결리스트 방식에 따라 삭제하면된다.(중복된 해시값에 저장하지 않았기때문)

선형 조사법

군집화로 인해 하나의 해시에 여러 데이터가 묶여있을수 있기떄문에

Null값이 저장된 인덱스로 해당값을 재배치해서 앞데이터와 뒤데이터를 이어줘야한다.

Reference

Java Backend Programming Blog![]