해시 테이블의 크기가 커지면 충돌 횟수가 감소하는 이유는 무엇입니까?</li> </ol> <p>나는 이해할 수</p> <ol> <li>이 해시 테이블의 크기를 늘 더 나은 해시 함수</li> <li>를 사용 : 나는 온라인 읽은 내용에서

Question

, 충돌의 수를 감소의 두 가지 방법이있다 첫 번째 이유가 있지만 두 번째 주위에서 머리를 맞출 수없는 것 같습니다.

만약 내가 5 키가 모두 있다고 해봅시다. 충돌 해결을 위해 체인을 사용한다고 가정 해 봅시다. 5 개의 키는 모두 해시 값과 동일한 인덱스부터 체인을 형성합니다. 자, 테이블의 크기를 두 배로하고 5 개의 키를 모두 다시 말해 보겠습니다. 5 개의 키는 여전히 이고은 동일한 인덱스로 해시되며 여전히 크기가 변경됩니다. 5. 해시 테이블의 크기를 늘리면 충돌이 줄어 듭니다.

Answer 1

해시를 계산하는 동안 배열 크기도 고려해야하기 때문입니다. 따라서 배열 크기가 클 경우 해시를 계산하는 동안 더 큰 모듈로 값을 취합니다.

예 :
배열 크기가 3 인 경우 가정 및 값 2 다음 5
2 3 %, 5 % 3 5
후 2 % 배열 크기의 일례를 수행하기 동일한 장소, 즉 1

걸릴이다 전달할 5와 5 % 5는 각각 다른 장소, 즉 2와 0을 취합니다.

따라서 해시 테이블 크기가 증가하면 충돌 횟수가 줄어 듭니다.
희망 설명이 도움이됩니다.

Answer 2

알아 냈습니다.

해싱은 해시 함수와 압축 함수의 두 부분으로 구성됩니다. 해시 테이블의 크기를 변경하면 압축 기능이 변경되므로 키가 다른 버킷에 할당됩니다.