[자료구조] 해시 테이블, 해싱, 충돌 해결 방법은?

해시 테이블

 

트리 자료구조를 사용하여 삽입과 삭제 연산 시 수행 시간은 최소 O(logn)이 나오는데,(이 경우는 AVL 트리)

 

이보다 빠른 연산 속도를 위해 제시된 방법이 바로 해시 테이블이다.

 

해시 테이블은 키와 1차원 배열의 인덱스의 관계를 이용해 키(항목)을 지정한다.

 

 

키를 배열의 인덱스로 그냥 사용하면 되지 않냐고 할 수 있지만, 아래 예시처럼 키는 숫자가 아닌 일련의 문자열일 수 있다. 그렇기에 메모리 낭비를  줄이기 위해 우리는 해시 테이블을 사용한다.

 

 

 

해싱 : 키를 해시 함수를 사용해 변환한 해시 값을 배열의 인덱스로 이용하여 항목을 저장하는 것을 말한다.

 

용어 정리를 한번 해보자면,

 

해시 함수는 키들을 테이블의 인덱스로 변환하는 함수인데, 이때 가장 이상적인 해시 함수는 키들을 균등하게 인덱스로 변환하는 함수이다.

 

• 대표적인 해시 함수로 중간 제곱 함수(Mid-square)와 접기 함수가 있다.
• 중간 제곱 함수는 키를 제곱한 후, 적절한 크기의 중간 부분을 사용하는 함수이다.
• 접기 함수는 몇 자리 씩 일정하게 끊어서 만든 숫자들의 합을 이용한다. 
• 해시 함수들은 키의 모든 자리의 숫자가 함수 계산에 참여한다는 특징이 있고,
• 계산 결과에서 해시 테이블의 크기에 따라 특정 부분만을 해시 값으로 활용한다.
• 가장 널리 사용하는 해시 함수는 나눗셈 함수이다. 이는 키를 소수 M으로 나눈 뒤, 그 나머지를 해시 값으로 사용하는 함수이다.
• h(key) = key % M
• M을 소수로 사용하는 이유는 나눗셈 연산을 했을 때, 소수가 키들을 균등하게 인덱스로 변환하기 때문이다.

 

 

해시 값은 이러한 해시 함수가 계산한 값을 말하고(혹은 해시 주소)

 

해시 테이블은 항목이 해시 값에 따라 저장되는 배열을 의미한다.

 

※ 자바의 hashCode()
- 자바의 모든 클래스는 signed 32비트 int를 반환하는 hashCode()를 포함한다.
- 자바를 이용하여 해시 테이블을 구현 할 때엔 일반적으로 hashCode()을 override하여 해시 함수를 구현한다.

 

 

 

그렇다면, 속도도 빠르고 메모리 면에서도 성능이 뛰어난 해시 테이블은 충돌이 없이 완벽할까?

 

그건 아니다.

아무리 뛰어난 해시 테이블이라고 하더라도 항상 충돌이 발생할 수 밖에 없다.

(여기서 충돌이란 서로 다른 키들이 동일한 해시 값을 가지는 경우를 말한다.)

 

그래서 해시 테이블은 정확히 두 가지 방법에 의거하여 충돌을 해결한다.

 

 

 

---

 

 

1. 폐쇄 주소 방식

 

가장 대표적인 방법으로 체이닝 방법이 있다.

 

간단하게 말해 같은 인덱스를 가지는 키들에 대해 서로 연결을 시켜준다.

마치 사슬로 연결하듯이 같은 키들에 대한 엔트리들을 이어주는 것이다.

 

 

---

 

 

2. 개방 주소법(open Adressing)

개방 주소 방식은 해시 테이블 전체를 열린 공간으로 가정하고, 충돌된 키를 일정한 방식에 따라 찾아낸 empty 원소에 저장한다.

 

즉, 비어있는 곳에 키를 저장하겠다 이말인데, 비어있는 곳을 찾아내는 방식에 따라 방법이 또 나뉜다.

 

 

 

 

 

선형 조사(Linear Probing)

충돌이 일어난 원소로부터 순차적으로 검색하여 빈 공간을 처음으로 발견할 때, 키 값을 저장하는 방법이다.

예를 들어 key를 해싱한 해시 값이 i라면, a[i], a[i+1], ... a[i+j] 차례로 검색하여 처음으로 빈 값에 저장한다.

 

선형 조사는 순차 탐색을 통해 충돌된 키를 찾아 저장하기 때문에 키들이 빈틈없이 뭉쳐지는 현상이 발생하기 쉽다. 이러한 현상을 군집화라고 하는데, 군집화는 탐색, 삽입, 삭제 연산 시 군집된 키들을 순차적으로 방문해야 한다는 문제점이 있다.

 

 

 

 

 

이차 조사(Quadratic Probing)

선형 조사와 근본적으로 동일한 충돌 해결 방법이나, 빈 공간을 찾는 방법에서 차이점을 보인다.

 

충돌 후, 배열 a에서 (h(key) + j^2) % M, j=0, 1, 2, 3...와 같이 작동하는데

 

쉽게 말해 선형 조사는 하나씩 늘어나며 검색했다면, 이차 조사는 제곱 단위로 검색을 실시한다.

예를 들어 제일 처음에는 충돌 다음 지점(1)을 검사하고, 그 이후에는 4만큼 떨어진 지점, 이후에는 9만큼...

 

 

즉, 이차 조사는 1차 군집화 문제를 해결하기 위해 등장한 것이다.(띄엄 띄엄 찾아 저장하니까..!)

 

하지만 이차 조사에도 치명적인 단점이 존재하는데, 바로 실패할 가능성이 있다는 것이다.

제곱 단위로 검색하므로 빈자리를 찾아낼 가능성이 줄어들기 때문이다.

뿐만 아니라 같은 해시 값을 가지는 동의어의 경우 또다른 형태의 군집화인 2차 군집화 현상도 발생할 수 있다.

(동의어 끼리 모이는 현상)

 

좌: 선형 조사, 우: 이차 조사

 

 

 

이중 해싱(Double Hashing)

 

이중 해싱은 2개의 해시 함수를 사용하는 방법이다.

즉, h(key)를 통해 키를 해시 테이블의 인덱스로 변환하고 만약 충돌이 발생한다면 다음 위치를 위한 점프 크기를 정하기 위해 d(key)라는 새로운 해시 함수를 적용시킨다.

 

이렇게 한다면 동의어들이 저마다 제 2의 해시 함수를 갖기 때문에 점프 시퀀스가 일정하지 않게 되고, 모든 종류의 군집화를 해결할 수 있다.

 

• 제 2의 함수 d(key)는 점프 크기를 정하는 함수이므로 0을 반환하면 안된다.
• d(key)의 값과 해시 테이블의 크기 M과 서로소 관계일 때, 좋은 성능을 보인다.(M을 소수로 선택 시 조건 만족)

 

 

 

 

 

 

재해시와 동적 해싱

 

어떠한 경우라도 해시 테이블이 비어있는 부분이 거의 없다면, 성능은 저하될 수 밖에 없다.

값을 저장하려면, 빈 자리를 찾아야 하는데 애초에 테이블에 빈자리가 없기 때문이다.

 

이러한 상황에서, 재해시(Rehash)라는 해시 테이블을 확장시키고 새로운 해시 함수를 사용하여 모든 키를 새 해시 테이블에 다시 저장하는 함수를 사용할 수 있다.

 

이는 오프라인에서 수행되며 모든 키를 다시 저장해야 하므로 O(n)의 시간이 소요된다.

 

재해시는 그러면 언제 수행되는 것일까?

 

키의 수를 테이블 크기로 나눈 것을 적재율이라고 하는데, 재해시의 수행 여부는 이 적재율에 의해 결정된다.

 

이 적재율이 0.75보다 크다면(초과) 해시 테이블을 2배로 확장하고,

적재율이 0.25보다 작다면(미만) 해시 테이블은 1/2배로 축소하는 것이 일반적이다.

 

 

---

 

동적 해싱(Dynamic Hashing)

 

위 재해싱을 수행하지 않고, 마치 c언어의 malloc 처럼 동적으로 해시 테이블의 크기를 조절하는 방법이다.

 

이는 주로 대용량의 데이터베이스를 위한 해시 방법이다.

 

주 기법은 확장 해싱과 선형 해싱이 있다.

 

 

🤔 해싱을 또 다른 말로?

해싱은 탐색 키의 산술적인 연산으로 버킷의 주소를 계산하는 것을 말한다.

즉, 해시 함수가 탐색 키 집합을 어떤 버킷에 저장될 지 알려준다.

(버킷 : 데이터를 저장하는 곳의 단위)

 

 

1. 확장 해싱

 

확장 해싱은 디렉터리를 통해 버킷에 접근한다.

 

아래 그림을 보면 알 수 있듯이, 모조키에 부합하는 탐색 키들끼리 모아둔 곳을 버킷이라고 하는 듯하다.

(모조키 : 탐색 키 값을 해시 함수로 일정 길이의 비트 스트링으로 변환한 키)

 

 

 

이러한 확장성 해싱의 분할은 오버플로우가 나온다면 디렉터리를 분할해 줄 수 있다.

 

즉, 새로운 값이 삽입되어 버킷이 가득 차면 버킷을 하나 더 생성하여 기존의 버킷 내부 값을 나누고, 디렉터리를 확장한다.

 

 

2. 선형 해싱

선형 해싱은 디렉터리 없이 삽입할 때, 버킷을 순서대로 추가해주는 것을 의미한다.

 

이는 순차적으로 버킷이 추가되며, 삽입되는 버킷에 저장 공간이 없으면 overflow 체인에 새 키를 임시로 삽입하고,

체인은 나중에 버킷이 추가되면 overflow 체인의 키들을 버킷으로 이동시킨다.

 

---

 

 

해시 방법의 성능 비교

해시 방법의 성능은 탐색이나 삽입 연산을 수행할 때, 성공과 실패한 경우를 각각 분석하여 측정한다.

 

선형 조사는 적재율이 너무 작다면, 해시 테이블에 빈 자리가 너무 많고, 적재율이 너무 크다면 군집화가 심화된다는 문제가 있다.

 

개방 주소 방식의 해싱은 적재율이 0.5 언저리, M은 2n인 경우에 O(1) 시간이다.

 

체이닝은 적재율이 너무 작다면, 대부분의 연결 리스트들이 빈 자리가 되고, 적재율이 너무 크다면 연결 리스트들의 길이가 너무 길어져 해시의 성능이 매우 저하된다.

 

일반적으로 M이 소수이고, 적재율이 10정도이면 O(1)의 성능을 보인다.

 

 

 

 

 

java.util.Map 인터페이스

 

java.util.HashMap이 java.util.Map 인터페이스를 구현한다.

디폴트 초기 용량은 101이며, 최대 적재율이 0.75인 폐쇄 주소법을 사용한다.

 

 

 

 

---

 

References

https://forgottenknowledge.tistory.com/entry/%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%B2%A0%EC%9D%B4%EC%8A%A4-11%EA%B0%95-%ED%95%B4%EC%8B%B1-%EC%A0%95%EC%A0%81-%ED%95%B4%EC%8B%B1-%EB%8F%99%EC%A0%81-%ED%95%B4%EC%8B%B1-%EB%B9%84%ED%8A%B8%EB%A7%B5-%EC%9D%B8%EB%8D%B1%EC%8A%A4

https://mangkyu.tistory.com/102