부하율 및 재해싱

부하율은 해시 테이블이 얼마나 꽉 차 있는지를 측정합니다. 로드 비율이 초과되면 해시 테이블 크기를 늘리고 더 큰 새 해시 테이블에 항목을 다시 로드합니다. 이것을 재해싱이라고 합니다. 로드 팩터 l(람다)은 해시 테이블이 얼마나 꽉 차 있는지를 측정합니다.
개수의 비율입니다 즉, l = n / N입니다. 여기서 n은 요소 수를 나타내고 N은 해시 테이블의 위치 수를 나타냅니다.

해시 테이블이 비어 있으면 l은 0입니다. 개방형 주소 지정 방식의 경우 l은 0과 1 사이입니다. 해시 테이블이 가득 차면 l은 1입니다. 별도의 연결 방식의 경우 l은 어떤 값이든 가능합니다.

l이 증가할수록 충돌 확률이 높아집니다. 연구에 따르면 개방형 주소 지정 방식의 경우 부하율을 0.5 미만으로, 별도의 연결 방식의 경우 0.9 미만으로 유지해야 합니다.

해싱 성능을 위해서는 로드 팩터를 특정 임계값 미만으로 유지하는 것이 중요합니다. Java API의 java.util.HashMap 클래스 구현에서는 0.75 임계값이 사용됩니다. 로드 비율이 임계값을 초과할 때마다 해시 테이블 크기를 늘리고 맵의 모든 항목을 더 큰 새 해시 테이블로 재해시해야 합니다. 해시 테이블 크기가 변경되었으므로 해시 함수를 변경해야 합니다. 재해싱의 가능성을 줄이려면 비용이 많이 들기 때문에 해시 테이블 크기를 최소한 두 배로 늘려야 합니다. 주기적인 재해싱을 사용하더라도 해싱은 지도에 효율적으로 구현됩니다.

위 내용은 부하율 및 재해싱의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!