해시 테이블에 대한 부하 요인에 대해 혼란스러워합니다.
로드 펙터를 계산하기 위해서는 엔트리 수를 우리가 가지고있는 슬롯 수로 나눌 필요가 있고 부하율이 0.75에 이르면 다시 해쉬해야한다는 것을 알고 있습니다.충돌이있는 해시 테이블의 부하 요인에 대해 혼동했습니다.
그래서이 해시 테이블의 "엔트리 수"는 얼마입니까? 이 키가 차지하는 총 키 수 또는 인덱스 수입니다.
총 키 수인 경우 다시 해싱하는 것이 무엇이겠습니까? 그것은 단지 공간과 시간을 낭비 할뿐입니다.
그리고 인덱스의 총 개수가 차지하는 경우 부하 계수는 2/5 = 0.4입니까? 대안 적으로, Set
요소의 수가 https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#entrySet--
이 일치하여 리턴 https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#size-- 또는 의해 반환 항목
항목 수는 모든 키가 하나의 연관된 값을 가지며 항목이 키/값 쌍인 키의 수입니다 (예). 그러한 맵을 재 강조한 포인트는 정확하게 맵의 성능에 해를 끼치는 긴 링크리스트를 피하고 더 나은 방법으로 버킷 사이에 엔트리를 분배하는 것입니다. 이상적인 분포는 각 버킷에 0 또는 1 개의 항목 만있는 경우입니다. –
그런 충돌이 일어 났을 때, rehashing은 도움이되지 않을 것입니다, 그렇죠? hashFunction 만 변경하면됩니까? – Nicky
아니요 간단한 예를 들어 봅시다.지도에 3 개의 버킷이 있고 해시 코드의 간단한 모듈을 사용하여 버킷을 선택합니다.지도에 0, 3 및 6이 있다고 가정 해 봅시다. 0 % 3 == 0, 3 % 3 == 0 및 6 % 3 == 0이기 때문에 모두 버킷 0에 포함됩니다. 이제 다시 해시하고 대신 7 개의 버킷을 사용하십시오. 이제 0 % 7 == 0이므로 첫 번째 키는 버킷 0으로 이동합니다. 3 % 7 == 3이므로 버킷 3에서 끝납니다. 6 % 7 == 6이므로 키 6은 버킷 6으로 이동합니다 이제 키가 버킷 사이에 이상적으로 배포됩니다. –