0
연쇄 해시 테이블에 삽입 할 때 언제 다시 하시겠습니까? alpha = 1 일 때 다시 해쉬하는 것이 더 좋을까요? (알파 = 저장된 요소 수/해시 테이블의 크기)언제 연쇄 해시 테이블을 다시 해시겠습니까?
A
답변
0
체인을 사용하면 일반적으로 버킷에 설정된 수보다 많은 항목이 포함되어 있으면 크기를 조정할 수 있습니다. 예를 들어 양동이에 최대 5 개의 항목을 포함하는 것이 좋다고 결정할 수 있습니다. 첫 번째로 여섯 번째 항목을 버킷에 삽입하면 테이블의 크기를 조정합니다.
또는 이상적인 숫자가 10 또는 3이라고 결정할 수도 있습니다. 검색 성능과 크기 조정 시간의 균형을 어떻게 유지할 것인가는 당신에게 달려 있습니다. 버킷 크기가 작을수록 평균 조회가 빠르지 만 표의 크기를 더 자주 조정해야합니다. 더 큰 버킷 크기를 사용하면 자주 크기를 조정할 필요가 없지만 평균 조회 시간은 더 길어집니다.
버킷 크기가 10 인 최악의 검색 시간은 버킷 크기가 2 인 경우보다 5 배 느립니다. 그러나 목록의 순차 검색보다 훨씬 빠르며 5 배 당신이 다시 해쉬해야하는 횟수의 감소. 애플리케이션의 최적 버킷 크기를 실험해야합니다.
더 큰 버킷 크기로 조회 시간을 향상시키기 위해 할 수있는 일은 조회시 방금 참조 된 항목을 해당 버킷의 목록 헤드로 이동하는 것입니다. 이 이론은 일부 항목이 다른 항목보다 훨씬 자주 조회된다는 이론입니다. 따라서 가장 최근에 참조 된 항목을 항상 목록의 맨 앞으로 이동하면 더 빨리 찾을 수 있습니다. 아이템이 균일하게 참조되면이 최적화는 아무런 효과가 없습니다.
체인을 사용하면 종종 부하율 150 % 또는 200 %로 양호한 성능을 얻을 수 있습니다. 때때로 더 높다. re-hashing과 비교하면로드 팩터 또는 70 % 또는 75 %에서 빠르게 저하되기 시작합니다.