[자료구조 Java] 해시 테이블 (2) - 체이닝(Chaining), 선형 조사법(Linear Probing), 이차 조사법(Quadratic Probing), 이중 해싱법(Double Hasing)

 

[자료구조 Java] 해시 테이블 (1) - 해시 테이블 및 해시 충돌(Hash Collision)

[자료구조 Java] 해시 테이블 (2) - 체이닝(Chaining), 선형 조사법(Linear Probing), 이차 조사법(Quadratic Probing),이중 해싱법(Double Hasing)

[자료구조 Java] 해시 테이블 (3) - 시간 복잡도, 장점과 단점

[Java] 자바 Collection Framework의 HashMap은 어떤 해시 충돌 알고리즘을 사용할까?

 

해시 충돌(Hash Collision) 해결 알고리즘 4가지

 

해시 테이블에서 해시 충돌에 대한 해결방법은 아주 중요하다. 체이닝(Chaining), 선형 조사법(Linear Probing), 이차 조사법(Quadratic Probing), 이중 해싱법(Double Hasing)과 같은 방법들이 존재한다. 어떤 해시 충돌 해결 알고리즘을 사용하는가에 따라 삽입연산 구현방법은 물론이고 삭제 연산까지도 그에 맞게 구현해야 하며 해시 테이블 전체의 성능을 결정하기에 적절한 해결 알고리즘을 선택해야 한다.

 

 

체이닝(Chaining)

 

체이닝 방법은 동일한 해시 값(Hash Value)을 갖는 Key들을 다른 버킷에 넣는 것이 아닌 동일한 버킷에 연결리스트 형식 연결하는 방법이다. 가장 간단하지만 체이닝의 문제점은 하나의 해시 값에 여러 엔트리가 몰릴 수 있다는 것이다. 이렇게 되면 배열, 리스트와 같은 선형적인 구조를 갖는 것이나 마찬가지기에 하나의 해시 값에 100개의 엔트리가 할당되어 있다면 탐색은 최악의 경우 100번의 접근을 하게 된다. 결국 탐색 시 최악의 경우 O(N)의 시간복잡도를 갖게 돼 탐색이 빠르다는 해시 테이블의 장점이 퇴색된다.

 

이러한 체이닝이 갖는 문제의 해결방법으로는 적재율에 따라 버킷의 크기를 동적으로 늘리거나 엔트리 들의 연결을 선형적 구조가 아닌 비선형적 구조로 변경하는 방법이 있다.

 

버킷의 크기 동적으로 늘리기

예를 들어의 크기가 2인데 엔트리가 10개면 해시 충돌이 일어날 가능성이 매우 높습니다. 따라서 bucket의 크기를 엔트리가 일정 적재율 이상으로 저장되면 동적으로 늘리는 방법을 통해 해시 충돌을 완화할 수 있습니다.

 

비선형적 구조로 entry 저장하기

기본 chaining이 해시 충돌시 엔트리를 연결 리스트 형태로 구성하여 선형적인 구조를 가져 탐색에 비효율적인 모습을 보였다. 이를 해결하고자 해시 충돌시 엔트리를 비선형적이고 계층적인 Red-Black Tree의 형태로 저장할 수 있다. Red-Black Tree를 구성하는 경우 삽입 순서에 상관없이 탐색에서 평균 O(logN) (밑은 2)의 시간복잡도를 갖는다. 실제로 자바에서 내부적으로 구현한 Collection Framework의 HashMap은 먼저 list형태로 해시 충돌된 것들을 연결하다가 entry가 일정 수를 넘어가면 Red-Black Tree로 연결 형태를 전환한다.

 

직접 주소 개방(Open-Addressing)

 

해시 충돌이 발생 시 다른 보조 함수를 이용하여 빈 버킷의 공간을 찾아 데이터를 저장한다. 보조 함수를 사용했는데도 빈 공간이 없다면 버킷의 크기를 늘리기도 한다. Open Addressing 방법을 통해 Bucket과 Entry는 1:1 대응 관계를 유지할 수 있어 해시 테이블의 빠른 탐색이라는 장점을 유지한다.

 

해시 함수의 결과에 Mod(나머지 연산)을 적용하여 bucket의 크기보다 index가 커지는 것을 방지한다. Bucket의 크기 m은 소수로 설정하는 것이 좋다. bucket 크기를 소수로 해야 해시 함수의 반환값이 편향되어도 mod(나머지 연산)을 했을 때 값이 고르게 분포되어 해시 충돌이 일어날 가능성이 낮아진다. 보다 자세한 설명은 해당 링크에서 확인 가능하다.

 

 

한계

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

 

 

Open Addressing 방법은 빈 버킷의 공간을 찾는 보조 해시 함수에 따라 선형 조사법(Linear Probing), 이차 조사법(Quadratic Probing), 이중 해싱법(Double Hasing) 이렇게  3가지로 나뉜다.

 

1) 직접 주소 개방 - 선형 조사법(Linear Probing)

 

선형 조사법의 보조 함수는 단순히 기존 해시값에 +1을 더하는 함수이다. 버킷의 크기가 m이라고 했을 때 보조함수는 output으로 0 ~ (m-1)의 범위의 해시값으로 변경하며 만약 해시 충돌이 발생한 경우 기존 output 해시 값 + 1의 index로 접근을 시도하며 이를 해시 충돌이 발생하지 않는 경우까지 반복한다.

 

기존 Hash 함수: h(key) mod m

충돌 시:

 

Ex) 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 // 저장

 

한계

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

 

선형 조사법의 문제는 군집화로 인해 선형적인 접근을 빈번하게 발생하며 빈 bucket을 찾지 못하면 최악의 경우 bucket 전체를 선형적으로 탐색한다. 군집화란 해시 충돌시 바로 다음 index에 접근을 시도하기에 해시충돌이 일어난 부분은 계속해서 길게 증가하며 해시충돌이 발생할 가능성이 높아지는 현상이다. 그렇게 bucket은 해시충돌이 일어난 index를 중심으로 순차적으로 데이터가 저장된다. 다시 여기에 접근하고자 할 때 bucket을 순차적으로 접근하여 해시 값은 동일하니 key를 일일히 비교하여 자신이 찾고자 하는 데이터가 있는지 확인하는 절차가 필요하다. 이는 결국 일반적이 배열과 유사한 구조를 갖게되고 해시 테이블로서 갖는 빠른 탐색이라는 장점이 없어진다.

 

 

2) 직접 주소 개방 - 이차 조사법(Quadratic Probing)

 

이차 조사법은 선형 조사법이 갖는 문제인 군집화를 해결하고자 나타난 방법이다. 선형 조사와 달리 보조 해시 함수로 기존 해시 값에 +1을 하는 것이 아닌 상수를 제곱한 값을 더하여 최초 해시 충돌 지점 index에 데이터가 몰리는 방지한다.

 

기존 Hash 함수: h(key) mod m

충돌 시:

 

Ex) 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에 공간이 있어도 이를 찾지 못할 수도 있음

 

이차 조사법의 경우 충돌시마다 더해진는 값이 다르기에 선형 조사법이 갖는 군집화는 어느 정도 해결한다. 하지만 이차 조사법 또한 결국에는 충돌시 동일한 규칙의 값을 더하기에 해당 규칙대로 약하지만 군집화가 이루어진다. 또한 충돌시마다 +1을 더하는 것은 아니기에 bucket에 저장할 수 있는 공간이 있음에도 이를 찾아내지 못하여 저장에 실패하는 경우가 생기기도 한다.

 

 

3) 직접 주소 개방 - 이중 해싱법(Double Hasing)

 

앞에서 살펴본 선형 조사법과 이차 조사법이 해결하지 못한 군집화는 결국 해시 충돌 발생시 일정한 규칙으로 동일하게 index를 증가시키기에  결국은 해당 규칙에 맞는 군집이 발생한다는 것이다. 이중 해싱법은 이러한 군집화를 아예 해시 함수를 추가하여 총 2개의 해시 함수를 사용하는 것으로 해결하고자 하였다. 서로 다른 해시 값을 합치고 추가 해시 함수에는 탐색 순서를 추가로 곱해주었기에 해시 충돌의 발생 가능성은 아주 낮아진다.

 

 

기존 해시 함수: h(key)

추가 해시 함수: J(key)

해시 충돌 발생시 함수: h(key) + i*J(key)  (i = 1, 2, 3...N)

 

 

한계

• 추가적인 해시 함수 연산이 있기에 해시 함수의 성능 자체가 전체적인 해시 테이블 전체에 큰 영향을 미친다.

 

 

해시 테이블 탐색

 

 

해시 충돌이 없는 경우 바로 해시 함수로부터 나온 해시 값을 bucket의 index로 바로 접근하여 값을 찾아낸다.

해시 충돌이 있는 경우 해당 해시충돌 해결 알고리즘 규칙에 따라 해시 값이 동일한 bucket중 찾고자 하는 key를 저장한 entry를 찾아 bucket을 탐색한다. 이를 반복하던 중 해당 index에 null값이 있다면 해당 key-value가 해시 테이블에 없다는 것이기에 탐색을 종료한다.

 

• key에 대한 해시 값을 찾거나, 빈 공간을 찾을 때까지 bucket을 탐색한다.
• 만약 빈 공간(null)을 찾으면 해당 key가 저장되지 않은 것이기에 탐색을 종료한다.
• 만약 key에 대한 해시 값을 index로 bucket에서 값을 찾으면 해당 bucket에 저장된 entry의 주소로 접근하여 entry를 반환한다.

 

 

해시 테이블 삭제

해시 테이블 삭제에서 해당 엔트리를 삭제하는 것은 간단하다. 사실상 탐색 연산이라고 할 수 있다. 해당 값을 탐색하고 그 값을 null값으로 만들면 되기 때문이다. 해시 테이블 삭제에서의 핵심은 해당 요소를 삭제하는 것이 아닌 해시 충돌 해결 알고리즘에 맞게 bucket에 저장된 해시 값을 적절하게 재배치 하는 것이다. 단순히 해당 bucket만 지우면 이후에 탐색을 진행 할 때 이후에 해시충돌로 동일한 해시값을 저장했다는 것을 탐색할 수 없기 때문이다.

 

 

정리하면

1. 동일한 키를 발견하거나 빈 공간(null)을 발견할 때 까지 충돌 해결 알고리즘에 맞게 탐색
2. 동일한 키를 발견하면 해당 bucket에 저장된 entry 제거
3. 충돌 해결 알고리즘에 맞게 bucket의 해시 값 재배치

 

1~2는 모든 충돌 해결 알고리즘이 동일하게 적용하기에 아래에서는 3. 해시 값 재배치만을 설명하도록 한다.

 

1) Chaining에서의 삭제

 

 

해시 충돌을연결 리스트 형태로 해결한 Chaining을 구현했다고 가정하자. 삭제 연산은 단순히 연결 리스트의 중간 노드 삭제와 완벽히 동일하다. Chaining의 경우 별도로 다른 bucket의 해시 값을 재배치 할 필요가 없다. 애초에 중복된 해시값을 bucket에 저장하지 않았기 때문이다.

 

2) Linear Probing에서의 삭제

 

Linear Probing의 재배치는 다음과 같은 규칙은 다음과 같다.

• 삭제한 bucket(null값 저장)의 인덱스 기준 다음 bucket 인덱스에 저장된 해시 값이 삭제한 bucket의 인덱스 보다 작거나 같으면 null값이 저장된 인덱스로 해당 값을 재배치한다.

 

다음 인덱스에 저장 된 해시 값이, 삭제한 bucket의 인덱스(=해시 값)보다 작거나 같다는 것은 해당 인덱스에 해시 충돌로 인해 해당 인덱스 값이 아닌 다른 해시 값이 저장되어 있다는 뜻이다.

 

여기서 삭제한 인덱스가 저장하던 해시 값과 같은 것만 재배치하면 되지 왜 굳이 해당 인덱스 값보다 작거나 같은 해시 값을 재배치해야 하는지 의문점이 들 수 있다. 이는 해시 충돌로 인해 인덱스가 낮은 곳에 인덱스가 더 높은 곳 보다 무조건 더 낮은 해시 값이 저장된다고 보장할 수 없기 때문이다.

그림을 보면 hash 값이 1인 버킷을 삭제하고 있다. 잘보면 인덱스 2에는 인덱스 1보다 더 작은 해시 값이 저장되어 있기 때문이다. 인덱스 0에 해시 값 0이 저장되고 인덱스 1에 해시 값 1이 저장된 상태에서 해시 값 0을 추가로 저장하고자 한느 경우 인덱스 0은 이미 차있고 그 다음 인덱스인 인덱스 1도 차 있기에 인덱스 2에 해시 값0을 넣게 된다.

 

 

다음: [자료구조 Java] 해시 테이블 (3) - 시간 복잡도, 장점과 단점

 

---

참고

 

https://www.codelatte.io/courses/java_data_structure

자바 자료구조 강의 - 코드라떼

 

C언어로 쉽게 풀어쓴 자료구조 - 천인국, 공용해, 하상호 지음