해시테이블 크기를 소수로 하는 이유

친구들끼리 이야기한 오늘의 대화 주제 겸 퀴즈는 '해시테이블 크기를 소수로 하는 이유'에 관한 것이다. 이로 부터 얻은 지식을 짧게 정리하려고 한다.
난 단순히 해시테이블이 key, value를 쌍으로 데이터를 저장하는 자료 구조라는 것만 알뿐 자세히는 기억하고 있지 않았다. 위의 질문에 먼저 결론부터 말하자면 해시충돌을 막기위한 방법 중 하나라는 것이 이유이다.
해시 충돌? 다른 내용의 데이터가 같은 키를 갖는다는 말이다. 즉, 특정 키의 버켓에 데이터가 집중된다는 말과 같다. 이러한 해시 충돌을 막기 위해 해시 테이블 크기를 소수로 해야 한다고? 이해가 가지 않는다.

해시테이블에는 해시 함수가 등장하는데 해시함수는 키값에 데이터의 값을 매핑할 때 쓰인다. 키값 매핑을 할 때 mod(나머지) 연산이 사용되고 그 결과값이 bucket에 들어간다. 나머지 연산식 -> 해시함수반환값 % 테이블크기
만약 테이블의 크기가 6이고 해시함수 반환값이 2의 배수라면? (2의 배수 % 테이블크기)
ex) 2,4,6,8,10,12,14,16...

불균등하게 결과값이 bucket안에 들언간다. 왜죠?
테이블 크기 소수가 아니면, 해시함수 반환값이 Kx이고, 테이블 크키가 Kn일때
나머지 = Kx - Kn몫 = K(x-n몫)
K 배수의 bucket에만 몰리는 현상이 발생할 확률이 높아서 최대공약수가 있기 힘든 소수로 주로 테이블 크기를 지정한다는 것이다. 그래서 전통적으로 소수를 사용하는 면이 크다고 한다.