비둘기집의 원리 : 왜 해시충돌을 피할 수 없는가?

 해시를 하기 전에, 비둘기집의 원리를 간단하게 짚고 넘어가겠습니다.

 

 

---

 집이 k개가 있고 비둘기가 k+1마리가 있습니다. 그리고 비둘기들은 상자들 중 하나에 들어갔을 때, 이들이 2마리 이상 들어가는 집이 최소한 하나 존재합니다.

 

 

 집 k개를 그려보았습니다. 그리고 밑에는 비둘기 k+1마리가 있어요.

 

 

 그러면, 결론을 부정해 봅시다. '2마리 이상 들어가는 집이 최소한 하나 존재한다'는 명제의 부정은, 2마리 이상 들어가는 집이 존재하지 않는다입니다. 그러면 k+1마리가 있고, 집이 k개 있을 때, 많아봤자 1마리가 들어간다가 참이라고 해 봅시다. 즉 ~p가 참이다라고 한 겁니다.

 

 

 그러면 각 상자에는 최대 1마리씩만 들어갈 수 있으니까, k개의 상자에는 최대 k마리가 들어갈 수 있습니다. 그러면 나머지 1마리는 어디에 들어가야 하나요? 전제는, 모든 비둘기들이, 상자, 혹은 집에 들어갔다입니다. 그런데, p를 부정하니까 어떤가요? 전제로 깔아뒀던 조건이 모순이 되어 버립니다.

 

 따라서, 2마리 이상 들어가는 집이 최소한 하나 존재합니다.

 

 

 그림으로 그려보면 다음과 같습니다. prove를 할 때, 최선의 경우에, 그러니까 비둘기의 입장에서 생각했을 때, 각 상자에 1마리씩 들어가는 게 optimal 했습니다. 그럼에도 불구하고 k+1마리가 들어가지 못한다는 것을 보였습니다. 이러한 기법은 후에, 그리디 문제를 풀 때도 많이 이용되기 때문에 알아두시면 좋을 듯 싶습니다.

 

 

---

 이제 일반화를 시켜 봅시다. 상자가 k개 있습니다. 그리고 인형이 n개 있어요. 인형들을 모두 상자에 넣는다고 하였을 때, ceil(n/k)개 이상 들어가 있는 box가 최소한 하나 이상 존재합니다. 이거 조금 까다로워 보이네요.

 

 

 그림으로 그려보면 대략적으로 이런 상황입니다. 그러면, 두 경우로 나눕시다. n = kQ + r (0<r<k)꼴로 나타내어지는 경우와, n = kQ로 나타내어지는 경우.

 

 

 그러면 이 때에는 ceil(n/k)의 값은 Q+1일 겁니다. 그러면, 결론을 부정해 봅시다. Q+1개 이상 들어가는 box가 단 하나도 없다. 그러면, 최대한으로 잘 넣었을 때, 하나의 상자당 Q개씩 들어간다는 이야기입니다. 그러면 Q개씩 넣어 봅시다.

 

 

 그런데 넣을 때, 이렇게 넣읍시다. 1번 상자에는 ...k + 1꼴로 나타내어지는 번호가 적혀져 있는 것들을, 2번 상자에는 ...k + 2꼴로 나타내어 지는 것들을, ... , k번째 상자에는 ...k + k꼴로 나타내어지는 번호가 적혀져 있는 것들을 넣습니다. 그러면, 1번부터 Q(k-1) + k = Qk번까지 넣을 수 있을 겁니다.

 

 

 그런데 보라색 부분은 들어가지 않았습니다. 전제는 무엇인가요? 인형들이 모두 box 안에 들어갔다입니다. 그런데 보라색으로 칠한 것들이 들어가지 않았습니다. 모순이 생겨 버립니다. ~p가 거짓이므로 p는 참입니다.

 

 

 다음에 n = kQ라고 해 봅시다. 이 때 ceil(n/k) = Q인데요. Q개 이상의 인형이 있는 상자가 단 한 개도 없다고 합시다. 그러면 box에는 최대 Q-1개의 doll들만 들어가게 됩니다.

 

 

 마찬가지 방법으로 box에 분배하면 다음과 같이 넣을 수 있습니다. 즉 1번부터 (k-1)Q번까지 상자에 넣을 수 있습니다. 그런데 저는 1번부터 kQ번까지 넣어야 한다고 했어요.

 

 

 그러면, (k-1)Q+1번부터 (k-1)Q+k번까지는 들어가지 못해요. 모든 인형이 들어갔다는 전제가 맞지 않아요. ~p가 거짓이므로 p는 참입니다. 두 case를 모두 보았을 때, n개의 인형을 k개의 상자에 넣을 때 ceil(n/k)개 이상 들어간 상자가 최소 하나 이상 존재합니다.

 

 

---

 아무리 잘 만든 해쉬 함수라도 충돌은 피할 수 없을까요? 상자를 버킷으로, 값들이 나오는 가짓수를 인형이나, 비둘기로 치환해 보시면 간단합니다. 예를 들어서, 문자열을 해싱하는 경우를 생각해 봅시다. 그러면, 문자열들의 가짓수가 인형으로 비유될 수 있어요. 그리고 버킷의 갯수가 box이고요.

 

 그런데, 문자열에 쓸 수 있는 문자 집합이 소문자, 대문자라고 한다면, 길이가 n인, 서로 다른 문자열의 가짓수는 52^n입니다. n의 값이 10만 되어도, 14경이 넘어갑니다. 그에 비해서 버킷 수는 한정이 되어 있어요. 10억개, 20억개의 상자가 있다고 하면, 필요한 공간은 대략 1기가가 넘어갈 수도 있을 겁니다. 비둘기집의 원리에 따르면, 가짓수가 버킷수보다 크면, 2개 이상 들어간 버킷이 최소한 1개 이상 존재합니다. 버킷에 다른 데이터가 둘 이상 있다? 충돌입니다. 따라서 충돌이 불가피합니다.