"일꾼이 일을 잘하려면 먼저 도구를 갈고 닦아야 한다." - 공자, 『논어』.
첫 장 > 프로그램 작성 > 부하율 및 재해싱

부하율 및 재해싱

2024-08-02에 게시됨
검색:435

Load Factor and Rehashing

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

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

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

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

릴리스 선언문 이 글은 https://dev.to/paulike/load-factor-and-rehashing-28mm?1 에서 복제되었습니다.1 침해 내용이 있는 경우, [email protected]으로 연락하여 삭제하시기 바랍니다.
최신 튜토리얼 더>

부인 성명: 제공된 모든 리소스는 부분적으로 인터넷에서 가져온 것입니다. 귀하의 저작권이나 기타 권리 및 이익이 침해된 경우 자세한 이유를 설명하고 저작권 또는 권리 및 이익에 대한 증거를 제공한 후 이메일([email protected])로 보내주십시오. 최대한 빨리 처리해 드리겠습니다.

Copyright© 2022 湘ICP备2022001581号-3