[알고리즘] Hash Table 구현하기

leetcode.com/problems/design-hashmap/

Design HashMap - LeetCode

 

Hash Table은 검색에 O(1) 의 시간복잡도를 가져서 다른 Search 문제에도 많이 쓰이는 Data Structure 이다.

Hash Table을 이용한 Hash Set, Hash Map의 Big O 참고

 

출저 - https://stackoverflow.com/questions/559839/big-o-summary-for-java-collections-framework-implementations

 

Hash Table이 Solution 으로 쓰인 문제 예시

leetcode.com/problems/two-sum/

leetcode.com/problems/two-sum-ii-input-array-is-sorted/

 

문제를 풀기 위해서는 먼저 Hash Table의 원리를 이해해야 한다.

참고로 위 리트코드 문제는 key와 value의 값이 숫자이고 0~1,000,000 으로 범위가 정해져 있기 때문에 

Array[1000000] 을 이용해서 간단하게 만들 수도 있다.

 

만약 HashMap에 key 234, value 11 을 put 한다고 했을 때,

array[234] 에 11 을 입력해주면 끝이다.

 

그렇지만 HashTable의 원리와 구조를 이해하고 구조 중 하나인 Bucket 을 Linked list 로 구현해보면서 숫자가 아닌 문제가 주어졌을 때도 풀 수 있도록 공부를 해보려고 한다.

 

key는 hash function을 통해 hash로 변경이 되며 value와 매칭되어 bucket에 저장이 된다.

Bucket은 저장소이다.

출저 - 위키백과

매칭 되는 과정에서 서로 다른 키가 같은 hash를 가질 경우가 있는데 이를 Hash Collision (해시 충돌) 이라고 한다. 시간복잡도도 O(1)이 지만 Hash Collision이 일어나면 O(n)이 걸릴 수도 있다.

이런 Hash Collision 을 보완하기 위해 linked list 가 쓰인다.

 

 

아래 그림 처럼, Key - John Smith 와 Key - Sandra Dee 가 같은 hash 152를 가지는 경우가 Hash Collision 이다. Hash 152에 연결된 Bucket에 John Smith key 와 value가 연결되어있고 그 다음으로 Sandra Dee key와 value 가 연이어 연결되어 있는 것을 볼 수 있다. Hash가 같아도 bucket 안에서 Linked list로 다른 key를 가진체 연결되어 있기 때문에 문제가 되지 않는다.

 

다시 말해 key를 찾을 때, 먼저 맞는 hash를 찾고 그 hash에 연결된 linked list 들 중에 맞는 key를 찾는 순서이다.

Java로 구현해보면 다음과 같다.

 

Bucket의 Capacity를 100이라고 정하면 

 

Bucket1은 key를 0-99까지 가지고 있고 (bucket 1 holds key-value pairs for keys '0' to '99')

Bucket2는 key를 100-199까지 가지고 있고

Bucket3은 key를 200-299까지 가지고 있다.

 

Linked list로 이루어진 Bucket class를 inner class로 선언해주고 bucket 의 capacity가 100이기 때문에 대략 10000개가 필요하므로 여러 Bucket 을 선언해주기 위해 Array를 이용한다.

 

 

put, get, remove 는 key / BUCKET_CAPACITY 로 index를 알아내어

bucket[index] 에 접근한 후 연결된 linked list (node) 를 탐색하면서 각각 put/get/remove에 맞는 action 을 해준다.

 

 

 

 

Note
put method 에
if(buckets[index] == null || buckets[index].node == null) 대신에
if(buckets[index] == null) 만 있었다가 case 1개에서 에러가 났다.

LinkedList 가 1개만 있던 Bucket을 remove 할 경우
remove 한 다음 비어진 Bucket에 새로 put 할 때 
buckets[index] 은 null 이 아니지만 buckets[index].node 는 null 이여서
put method가 제대로 작동되지 않고 있었다.