Chapter 7. Dictionary
Dictinary란 임의의 Key를 삽입/삭제/탐색하는 자료구조이다. 아이템들은 Pair [Key, Value]를 가진다.
예를 들어, 사전에서 단어 정의, DNS Mapping Table 등 검색을 할 때 사용된다.
구현방식에 따라 설명을 진행 한다.
1. List-based Dictinary
= Log File = Sequence Unsort List
데이터가 들어오는대로 저장한다.
삽입 : 들어오는대로 저장하면 되므로 O(1)이다.
삭제 : 배열의 경우 원소들을 transfer 하기 때문에, 리스트의 경우 탐색하기 때문에 O(n)이 소요된다.
탐색 : Unsort 돼있어 모든 노드를 탐색하며 O(n)이다.
Example) 기록, 로그 파일과 같이 삽입 연산이 자주 일어나는 경우 사용된다.
2. Search Table
= Look Up Table = Sequence Sort Array
Array로 구현되며 탐색시 분할정복을 이용한 Binary Search를 이용한다.
삽입 : O(n)
삭제 : O(n)
탐색 : Binary Search이므로 O(log n)이 소요된다.
Example) 탐색이 잦은 경우 유용하며 DNS Mapping 탐색, 신용카드 조회에서 이용된다.
3. Hash Table
= Hashing
"John Smith"의 Key가 Hash Function을 거쳐서 02로 바뀌어지고 "521-1234"의 Value를 Bucket에 저장한다.
내부적으로 배열로 구현하여 캐싱능력이 좋다. 또한 삽입, 삭제, 탐색의 기대치가 모두 O(1)으로 매우 빠르다. 드문 경우지만 모든 Key 값이 같은 Hash Value를 가질 때 Worst case로 O(n)이 소요된다.
Hash Value란? Hash Function에 의해 Key값이 Bucket의 index로 맵핑 된다.
Hash Function이란?
정수, 음수, 문자열 등 다양한 데이터 타입을 가질 수 있는 Key를 배열의 index로 맵핑시켜주는 역할을 한다. 하지만, 서로 다른 Key가 같은 Hash Value를 가질 수 있다. 이를 Collision이라고 부른다. 이때 충돌을 없애는것은 불가능하지만, 충돌을 일으키는 확률을 최대한 줄이는것이 중요하다. 충돌을 줄일수록 연산 속도가 빨라지며, 충돌을 줄이기 위해 배열의 크기를 크게 잡는 경우가 많다. 이때 충돌을 줄이기 위해 Hash Function은 Hash Value들을 최대한 분산 시켜야한다.
이때, 데이터들을 최대한 분산시키기 위해 Modulus 하는 수를 소수로 한다.
좋은 Hash Function은 Key와 버킷을 1:1로 대응 하는것이 아니라 [거의 불가능하며 배열과 다를점이 없고 메모리를 많이 사용하기도 한다.] Key 일부가 아닌, Key 전체를 참조하여 해시 값을 만들어 Collision의 횟수를 최소화 하고, Collision Handling이 중요하다.
Load Factor란 원소 갯수 / 버킷 갯수 로 이 값이 작을 수록 충돌이 덜 일어난다. 따라서 해싱은 속도를 위해 공간을 사용한다. 만약 Load Factor가 0.75가 넘으면 ReHash가 일어난다. 즉, 공간을 2배로 하여 재 할당 후 element들을 Hash 조건에 맞게 Transfer한다. 이는 O(n)이 소요된다.
Hash Code : 다양한 데이터 타입의 key -> Integer
Compression function : integers -> [0~N-1] 으로 Mapping [Array Index안에 맵핑]
2번째 단계에서 Hash Code mod N을 통해 수행하기도 하며 [이때 N이 소수일수록 분산이 잘 일어난다고 알려져있다. 혹은 (a * Hash Code +b) mod N을 통해 수행하기도 한다. [더욱 분산이 잘 일어난다고 알려져 있다.]
위의 2단계를 통해 Hash Function은 수행된다.
4. Collision Handling
1. Chaining by Closed Address
배열에는 링크드 리스트의 헤더 주소가 들어가져있으며 위 그림에서 "451-229-0004"와 "981-101-0004"는 같은 Hash Value를 메다는 형태를 가진다. 이렇게 다른 Key 값을 가지지만 같은 Hash Value를 가지는 Collision이 발생 했을 때 Chaining 형태로 메다는 방법이다.
낮은 확률이지만 최악의 경우 모두 같은 Hash Value를 가져 일렬로 노드를 메달 경우 O(n)이 소요된다.
또한 각 노드는 배열이 아닌 포인터 형식으로 매달아 캐싱 성능이 안좋을 수도 있다.
또한 배열 이외에 추가적인 메모리를 필요로 하는 단점이 있다.
일반적으로 메모리가 중요 하지 않는 이상 체이닝 기법을 많이 이용한다고 한다. 왜냐하면 Open Addressing은 버킷의 밀도가 높을 수록 Worst Case가 생길 빈도 수가 높아지기 떄문이다. 따라서 JAVA 7 에서는 Separate Chaining 방식을 사용하여 HashMap 을 구현하고 있다.
Channing은 같은 Hash Value를 가진 노드들에게 영향을 줘 버킷 밀도에 Open Addressing보다 덜 민감하다.
위에 나온 방식은 링크드리스트지만 레드 블랙 트리를 이용하기도 한다. 하나의 해시 버킷에 할당 된 Key-Value 쌍의 갯수가 [6-8]개보다 크다면 트리로, 작다면 링크드리스트로 사용하는것이 좋다. 레드 블랙 트리는 삽입/삭제/탐색 연산 모두 O(log n)에 수행되지만 메모리가 좀 더 필요하다.
리스트와 트리의 변경 소요 시간을 줄이기 위해 하나의 값을 기준으로 변환이 이루어지지 않는다. 만약 변경 기준이 7로 고정하면 Switching 비용이 자주 소요된다. 따라서, 데이터의 갯수가 6-7로 증가했을 때는 링크드 리스트의 자료구조를 취하고, 8-7로 감소할 때 트리의 자료구조를 취한다.
2. Linear Probing by Open Addressing
내 자리에 누군가 있으면 다음 자리로 가는 방법이다.
하지만 위 그림처럼 데이터들이 특정 영역에 모이는 Cluster가 발생한다면 이는 삽입/삭제/탐색 연산 모두 성능저하가 일어난다. 왜냐하면 특정 영역 근처에서 연산을 진행할 경우 무조건 그영역 모두를 탐색하기 때문이다.
또한 데이터 삭제 시 이 곳은 데이터가 있었던 곳이라고 표시를해야 된다. 삽입 시 빈 공간 or 데이터 있던 곳에 삽입을 해야된다.
3. Double Hashing
위의 Linear 방식의 경우 Cluster 문제가 발생하였다. 이 현상을 줄이고자 Collision이 발생 했을 때 한 칸 옆에 데이터를 넣는것이 아닌 일정 구간만큼 점프를 수행하며 진행한다.
{ h(key) + j*d(key) } mod N
해당 자리에 누군가 있으면 j++ 해서 반복을 한다.
d(k)는 보통 q- (key mod q)로 많이 사용한다. 이때 N은 소수, q는 N보다 작은 소수로 설정을 한다.
데이터의 갯수가 적다면 캐싱 능력도 좋고, 버킷 밀도가 그리 크지 않아 Cluster 현상이 줄어들어 Open Addressing이 좋다. 그 외에는 메모리를 좀 더 사용해서 체이닝 기법이 좋다.
Dictionary를 구현하는 또다른 방법은 Binary Search Tree가 있다. 이 내용은 다음장에서 설명한다.