테이블과 해시 함수

테이블은 무엇인가?

---

딕셔너리는 Key, Value 형식으로 주어진 자료형을 이야기한다. 우리 주변에는 이런 형식을 아주 흔하게 찾을 수 있는데, 예를 들면 아래 표와 같은 것이다.

사번	이름
20160829	김영희
20160830	김철수
20160840	김선생

우리가 엑셀에서 흔히 보는 데이터 테이블인데, 이런 형식으로 주어지는 자료를 차곡차곡 모은 것을 딕셔너리라고 한다. 유사한 말로는 테이블, 맵이 있을 수 있다. 이런 자료구조 형식의 장점은 O(1)의 시간복잡도로 자료를 찾고, 추가할 수 있다는 점이다.

 

테이블은 어떻게 만들까?

---

기본적으로 테이블은 배열을 기반으로 구현하는 것으로 알고 있다. 배열을 기반으로 구현한다면, 당연히 배열 범위는 필요한만큼만 선언이 되어야 메모리의 최소화가 가능하다. 이런 이유 때문에 Key로 들어오는 값은 무궁무진할 수 있지만, 이 Key가 가리키는 값은 무궁무진하면 안된다. 왜냐하면 무궁무진하다면, 그만큼의 배열을 선언해야하기 때문이다.

사번	이름
20160829	김영희
20160830	김철수
20160840	김선생

위의 표를 다시 한번 예로 들자. 20160829를 전부 Key로 사용한다고 해보자. 이럴 경우, 3명의 값을 저장하는데 배열의 사이즈가 20160840만큼 늘어나야 할 수 있다. 심각한 메모리 낭비다. 이를 해결하기 위해서 Key로 들어온 값의 특정 부분만 선택해서 특수하게 처리해서 새로운 값을 만들 수 있다. 이를 Hash라고 한다. Hash는 큰 범위의 Key를 특수한 처리를 통해 좀 더 작은 범위의 Key로 만든 것을 뜻한다.

 

Hash Collision(Hash 충돌)

---

사번	이름
20160829	김영희
20160830	김철수
20160840	김선생
22222229	박선생

아무리 특정 값을 특정하게 처리해서 Hash를 만든다고 해도, Hash 값이 같아지는 경우가 있다. 예를 들어 Key(사번)를 Hash로 바꿀 때, 가장 마지막 자리에 있는 숫자로 Hash로 바꾼다고 가정해보자. 이 경우, 김영희씨와 박선생씨는 사번이 다른데, Hash값은 동일하게 9가 된다. 서로 다른 Key로 Hash를 만들었는데, Hash가 같은 경우가 있다. 이것을 Hash Collision(Hash 충돌)이라고 한다.

 

Hash 함수 만드는 방법

---

• Hash 함수를 만드는 방법은 큰 틀은 아래와 같다고 한다.
• Digit Selection : 전체 Key중 특정 부분만 선택함
• Digit Folding : 전체 Key를 몇 토막을 낸 후, 그 토막의 값에 같은 연산을 반복함 (2043 → 20 + 43 = 63)
• Division : Key값을 배열의 크기로 나눈 나머지로 Hash로 구함.

 

 

 

Open Addressing(Hash 충돌 해결) 

---

Hash 충돌을 해결하는 방법 중 하나는 Open Addressing이다. Open Addressing은 Hash값이 주소에 자유롭다고 이해를 하면 좋을 것 같다. 예를 들어 아래 그림을 보면 바로 이해가 가능하다.

위와 같은 배열이 있다고 가정해보자. 특정한 값을 Hash로 만들었을 때, 그 값이 1이라고 가정하자. Hash Table을 살펴보니, Index 1에는 이미 다른 Key에 의한 값이 들어가있다고 한다. 그래서 Index 2, Index 3을 살펴봤는데 모두 이미 다른 Hash가 점거하고 있다고 한다. Index 4로 왔을 때, Empty 상태이기 때문에 여기에 현재 Key값에 대한 것들을 저장해둔다. 

즉, Open Addressing은 Hash Collision이 발생했을 때, 그 Hash를 기준으로 Index를 변경해가며 Empty가 있는 곳을 찾아, 그곳에 값을 저장하는 방식이다. 이처럼 Index를 하나만 고집하지 않고, 넓게 사용하기 때문에 Open Addressing이 아닌가 싶다.

 

Open Addressing 방법

---

• Linear Probing : Hash Collision 발생 시, Index를 한 칸씩 늘려가며 살펴보는 방법
• Quadratic Probing : Hash Collision 발생 시, Index를 Square만큼 늘려가며 살펴보는 방법
• Double Hahs : Collision 발생 시, 2차 Hash 함수를 사용해 Randomic하게 구간을 만드는 방법

Open Addressing에는 위의 세 방법이 있다. Linear Probing과 Quadratic Probing은 구현하기 쉽지만, 치명적인 단점이 있다. 바로 Hash에 Cluestring 현상이 발생할 수 있고, 이 Clustering이 발생하면 Hash Collision이 증가할 가능성이 더욱 높아진다는 점이다.

위의 이미지를 보면 직관적으로 알 수 있다. 위에 있는 막대는 메모리 공간을 Hash가 넓게 사용할 때를 보여주고, 아래 막대는 메모리 공간의 특정 영역에 Hash 값이 많이 분포하고 있는 것을 보여준다. Quadratic Probing, Linear Probing으로 Hash Collision을 처리할 경우, 이동하는 방식이 일정하기 때문에 특정 영역에 Hash값이 몰릴 가능성이 매우 높다.

즉, 아래 그림처럼 Hash가 Clustering을 형성할 가능성이 높으며, 저 영역에 Hash가 빠져들면 십중팔구 추가 Hash Collision이 발생할 가능성이 더 높아진다. 이 Clustering 현상은 Probing 방법의 규칙적인 이동때문에 발생하기 때문에, Hash Collision 발생 후 이동하는 방식을 Randomic하게 바꾸어준다면 Hash Clustering 개선에 도움이 된다. 

 

Double Hash 

---

Hash Collision 시, 이동하는 방법을 Randomic하게 만들어 주기 위해 도입된 것이 Double Hash다. Hash 함수를 두 개 만들어 사용하겠다는 것이다. 1차 Hash 함수는 Hash 값 자체를 만드는 것으로 사용하고, 2차 Hash 함수는 Hash Collision이 발생했을 때, Key 값을 바탕으로 이동해야할 구간을 Randomic 하게 만들어주기 위해 사용된다.

한 예로, 1차 Hash 함수와 2차 Hash 함수를 아래처럼 구성할 수 있다.

1차 함수 : H(K) = K % C1, 2차 함수 : H(K) = 1 + K % C2(단, C1과 C2는 서로소) 

값을 넣어서 한번 확인해보면 다음과 같다.

1차 함수 H(K) = K % 12, 2차함수 : H(K) = 1 + K % C2

K = 11, 23이라고 가정하면 각각의 Key에 대한 1차 Hash 결과는 11로 동일하다. 그런데 Collision이 발생했으니, 2차 함수로 이동하는 구간을 바꾸는 것까지 계산을 해보자. 1 + 11 % 7, 1 + 22 % 7로 예시를 들어볼 수 있고, 2차 함수 처리결과는 5, 2가 된다. 즉 다른 Key가 들어왔을 때 동일한 Hash 값이 생성되지만, Hash 충돌 시 이동하는 영역이 다르기 때문에 Hash 충돌이 좀 더 줄어들 수 있다는 것이다.

이 때, 서로소를 이야기한 것은 서로소가 될 경우 확률통계적으로 Clustering 현상이 줄어들 가능성이 있다고 하기 때문이다(믿거나 말거나)

 

Open Addresing의 상태(Empty, In Use, Deleted)

---

Open Addresing으로 Hash Collision을 해결할 때, 각 배열은 세 가지 상태(Empty, InUse, Deleted) 중 하나를 가지고 있어야 한다.  

왼쪽 상황이 오른쪽 상황처럼 변경되었다고 가정해보자. 1번 인덱스의 값이 사라진 상황이다. 이 때, 또 다른 Key로 Hash가 1이 나왔다고 가정을 해보자. 이 경우, Empty인 상황이라면 바로 값이 1번 인덱스에 저장되게 된다. 그렇지만 이는 Hash Collision이 없는 것처럼 된 것이기 때문에 틀린 접근이다. 

Hash가 이미 저장되었다가 지워진 곳이라면, Deleted 상태를 도입한다. 그리고 Deleted 상태라면 여기에 값은 저장되어있지 않지만 Hash Collision이 발생한 곳이기 때문에 좀 더 탐색을 해봐야 하는 것으로 이해하고 추가 탐색을 한다. 그리고 Empty로 되어있던 4번 인덱스에 값을 저장하면 된다. 

 

 

Chaining (Closed Addresing)

---

Chaining은 Hash Collision을 해결하기 위한 방법인데 Closed Addresing이라고 불린다. Closed에서도 알 수 있듯이, 어떤 일이 있어도 주어진 Hash에 값을 저장하겠다는 이야기다. 이는 배열과 Linked List로 구현할 수 있는데, 메모리 관점에서 Linked List로 구현한다고 한다. 그림으로 표현하면 다음과 같다.

예를 들어 왼쪽 그림처럼 김철수라는 입력이 들어왔는데, Hash값이 1이고, 그 Hash 값에 김선생이 저장되어있다고 하자. Chaining은 Hash Collision이 발생했을 때, 오른쪽 그림처럼 이미 들어가있는 Hash값 뒷쪽에 붙이는 방식으로 자료를 계속 저장한다. 동일한 Hash값에 Linked List로 계속 자료를 연결시켜주게 된다면, Hash Collision이 발생했을 때 뒷쪽에 또 다른 노드가 있는지 확인하는 방식으로 접근하면 되기 때문에 Open Addresing에서 하던 것들을 고려할 필요는 없다.

그렇지만 최악의 경우, 위 그림처럼 모든 Key가 하나의 Hash로 만들어지는 경우가 있을 수 있다. 위 상황이라면, Hash Table로 특정 Key에 대한 Value를 찾는데 필요한 시간복잡도는 O(n)이 될 수 있다. 

덧붙이자면, 정확하게는 Hash의 Linked List의 각 노드는 Value값이 저장된 주소값과 다음 연결된 노드를 가리키는 것으로 이해를 하는 것이 편한다. 각 Node가 Value와 다음 노드를 가지는 방식으로도 구현이 가능하지만, 이 경우 새로운 구조체 선언이 필요하기 때문에 Node가 주소를 가리키는 방식으로 구현을 주로 한다고 한다. 

 

 

Hash Table의 시간복잡도 O(1)

---

Hash Table은 특정 Key를 고유한 Index인 Hash로 바꿔주고, 이 Hash로 바로 Value에 접근할 수 있기 때문에 O(1)로 바로 데이터를 접근하고 쓸 수 있다.. 그렇지만 Hash Collision이 심각하게 많이 발생하는 상황이라면, 특정 값을 찾고 쓰는데 O(n)의 시간이 필요하다.

 

Hash Table의 성능 개선

---

자주 사용하는 Hash 값을 Cache에 저장해두고, 그 Key가 들어오면 바로 값을 찾아주는 방식으로 Hash Table의 개선이 가능하다고 한다. 아직까지 Cache 개념이 없는 나는 이해가 잘 안되는데, 나중에 공부해서 이해를 하게 되면 업데이트를 다시 한번 해야겠다.