자료구조 해시 테이블 : 직접 구현해 봅시다.

 저번에 비둘기 집의 원리에 대해서 잠깐 언급을 했었습니다. 거기서, hash에 대해서 잠깐 언급을 했었는데요. 오늘은 이 hash를 STL 없이 직접 구현을 해 봅시다. 다음 시간에 String의 hashCode를 직접 구현해 보고, 백준의 듣보잡 문제를 풀어 봅시다. 사실 Hash는 크게 보면 딱 1가지만 주목하면 됩니다.

 

 

 <Key,Value>가 있을 때, 우리는 Key에 대응이 되는 bucket 값을 b(key)라 할 거에요. 예를 들자면, Key 값이 10101010입니다. b(10101010)의 값이 10이라면, 우리는 10번 버킷에 Value를 넣는 것입니다. Key가 정수인 경우, 함수 b는 Key 값에다가 버킷 갯수를 나눈 모듈러를 취하는데요.

 

 예를 들어서, Key의 값이 2058370이고, 버킷 수가 100만인 경우, 2058370을 100만으로 나눈 모듈러 값인 58370을 버킷 번호로 삼습니다. 58370번 바구니에 V를 저장하는 것입니다. 그러면 문자열의 경우는 어떻게 할까요?

 

 

 당연하게도 문자열은 한 번 Compress를 합니다. 문자열을 숫자 하나로요. 혹은 모듈러 값을 2개 정도 둬서 압축을 하거나. 그렇게 해서 정수 하나로 압축한다면, 나머지 과정은 똑같을 겁니다. 보통, 데이터 크기의 2배에서 3배 정도를 버킷 갯수로 두는데요. 이는 평균 복잡도를 상수로 떨구기 위함입니다.

 

---

 B형 시험을 보신다면, STL 없이 스스로의 힘으로 구현을 하셔야 합니다. 같은 버킷에 두 개 이상 데이터가 들어가는 경우에, 충돌이 났다고 이야기를 하는데요. 그림으로 그리면 이런 상황입니다.

 

 

 이걸 어떻게 처리할 것인가? 이게 관건이 될 수 있어요. 제일 쉬운 방법은 버킷도 array나 List로 선언을 하는 것인데요. 이들은, 체이닝을 위해서 쓰입니다. 같은 버킷에 있는 친구들을 이어주기 위한 역할을 합니다. 그런데 보통, 구현하실 때 정적 배열로 하는데요. 이는 List에 비해서 array는 지역성이 상대적으로 더 좋기 때문입니다.

 

 이는 Trie를 구현할 때에도 마찬가지입니다. 그렇다면 만약에 배열로 구현한다면 뭐가 필요할까요?

 

 

 일단 bucket[sz][10]을 봅시다. 이것은, 버킷 하나 당 10개의 원소를 저장할 수 있다는 것입니다. 최악의 경우가 거의 발생하지 않는다는 전제가 깔려 있다면, 버킷 하나 당 저장할 수 있는 원소의 갯수를 5개에서 20개 사이로 두어도 무난합니다. 이는 랜덤하게 돌리는 경우, 충돌이 10번 이상 날 확률이 손에 꼽을 정도이기 때문입니다.

 

 그러면, 우리는 추가 작업을 어떻게 해야 하느냐가 문제가 될 수 있겠군요. count[x]는 x번 버킷에 원소가 몇 개 들어있는지를 나타냅니다. 예를 들어서, 2번 버킷에만 1, 3, 5가 들어갔다고 해 봅시다.

 

 

 그러면, count는 위와 같을 거에요. 그 다음에 <b,k>을 추가한다고 해 봅시다. 그러면 Key에 대응되는 b의 값이 0이고, Key가 7인 것을 추가하는데요. 이 때 count[0]의 값은 0입니다. 따라서, bucket[0][0]에 실제 값인 7이 들어갑니다.

 

 

그 다음에 무슨 값을 증가시켜야 하나요? 0번에 있는 원소의 갯수가 0개에서 1개로 늘어났으니까, count[0]의 값을 하나 증가시키면 됩니다. 계속 뒤에다 추가시키면 됩니다. 레퍼런스에서는, 동적 배열이나 List를 사용해서 구현하는데요. 만약에 List를 사용한다면 어떻게 하면 좋겠나요?

 

 head나 tail의 값을 안다면, 앞에다 추가하거나 뒤에다 추가하는 것은 상수 시간만에 할 수 있어요. 즉, 이 두 값만 잘 알면 무난하게 하실 수 있어요. 그러면, 다음에 Key 값이 15가 들어왔어요. 그런데 이것이 들어가야 하는 버킷 값이 3입니다. 어떻게 하면 좋겠나요? 똑같이 하면 됩니다. count[3]은 0이니까, bucket[3][0]에 15를 넣고 count[3]의 값을 하나 증가시키면 됩니다.

 

 

 그러면 요렇게 될 거에요. 이 때 count 배열은 아래와 같이 될 거에요.

 

 

 이해가 가시리라 생각하고 다음으로 넘어가겠습니다.

 

 

---

 삽입은 그리 어렵지 않으니, 찾기와 삭제를 보도록 하겠습니다. 사실 찾기만 잘 하면 삭제도 무난하게 됩니다. 해시 테이블에서, 5는 어떻게 찾으면 될까요? 일단 버킷함수(5)는 2입니다. 따라서 2번 버켓에서 찾아야 할 겁니다. 2번에서 쭉 탐색을 했는데, 5가 나오지 않았아요. 그러면 5가 없는 것입니다. 이 때에는 -1을 리턴해 줍니다.

 

 

 그렇지만, 2번에서 탐색을 했는데 5가 있어요. 그러면, 5가 있는 것입니다. 이 때에 어떤 값을 리턴해 주느냐가 문제인데요. 보통, 버킷에서 몇 번째 위치에서 찾았는지 리턴을 해 줍니다. 예를 들어서 find(5)를 호출하면, 2를 리턴해 주는 식입니다.

 

 

 그러면 5를 삭제할 때, 버킷 번호가 2였고, 2번째에서 찾았다는 정보를 빠르게 가져올 수 있어요.

 

 

 그러면 이 함수에서 K와 V는 어떤 것일까요? K는 당연하게도 Key에 대응되는 버킷 번호가 될 거고요. V는 키 값이 될 거에요. 여기서, 문제의 키 값을 찾으면 그 위치를 리턴하고, 그렇지 않으면 -1을 리턴하게 만들면 됩니다. 그러면 삭제는 어떻게 구현하면 될까요?

 

 

 만약에 K번 바구니에서 lo번째 위치에 실제 값인 Key를 찾았다고 해 봅시다. 예를 들자면 위 그림에서, 3을 찾으라고 한 경우에는 K = 2이고 lo = 1일 겁니다. 그러면 우리는 연두색으로 표시한 부분을 앞으로 1칸씩만 당기면 됩니다.

 

 

 그러면, 1칸씩 앞으로 당기고 나서는 아래와 같이 될 겁니다.

 

 다음에, count[2]의 값을 하나 감소시켜주면 됩니다.

 

 

 이를 코드로 구현하면 다음과 같습니다.

 

 

 앞으로 당기는 연산하고 lo값이 -1일 때만 주의하면 크게 어려울 것은 없습니다. 키 값을 삭제하는 연산까지 배웠습니다. 대략 30줄 정도. 40 ~ 50줄 정도면 hash table은 쉽게 구현할 수 있습니다. 물론, 충돌이 매우 많이 나는 경우에 선형 복잡도인 것은 피해갈 수 없지만, 랜덤하게 인풋이 들어오고, 확률에 어느 정도 의존을 할 수 있는 경우에는 정적 배열로 선언해 두고, 간단하게 구현하는 것도 좋은 선택입니다.