해시의 "품질"은 임의의 해시에 필요한 예상 수를 기준으로 모든 요소에 한 번 액세스하는 데 필요한 총 비교 수로 정의됩니다. 값은 100 %를 초과 할 수 있습니다.해시의 품질을 누구나 이해할 수 있습니까?
총 비교 수는 각 버킷에있는 항목 수의 제곱의 합계와 같습니다. "< K"> 버킷으로 "< N"> 키 랜덤 해시를 들어, 기대 값은 다음과 정확하게 해시의 품질이 무엇
n + n (n - 1)/2 * k
??
해시가 "균등하게 분산 된"방법에 대한 척도입니다. 이상적으로, 해시 함수는 모든 것을 자체 버켓에 넣을 수 있지만 많은 버킷을 가질 수 없으므로 발생하지 않습니다 (심지어 해시 충돌이 있어도 고유 한 값이 같은 버킷으로 끝납니다).
많은 요소가 포함 된 버킷을 사용하면 해시 성능이 향상됩니다 (이상적으로는 버킷을 올려 놓고 단일 요소를 살펴 보는 것이 이상적입니다). 그런 경우에는 모든 요소를 선형 적으로 처리해야합니다 .
100 % 품질은 무작위 데이터로 채워진 해시에 대해 기대하는 것입니다. 이 경우 모든 양동이가 똑같이 가득해야합니다. 100 % 이상인 경우 데이터가 고르지 않게 해시되고 조회에 더 많은 시간이 소요됩니다.
공식은 어떻게 생깁니 까? –
모든 해시 구현에서 충돌이 동일한 버킷에서 끝나는 것은 아닙니다. * 해시 값 *의 충돌은 연결 (일반적으로 어떤 형태의 프로브 및 버킷 가용성 보장)없이 해결 될 수 있습니다. –
그 공식은 어디에서 왔습니까? Is는 'k'버킷으로 모든 'n'키를 찾는 데 얼마나 많은 비교가 필요한지 나타낼 예정입니까? 그렇다면 최대 460 개를 추가합니다. 이는 최악의 경우 단순 배열보다 약 450 번의 반복이 더 나쁘고 배열의 평균 경우보다 455 번의 반복이 더 나 빠릅니다. 뭔가 잘못됐다고 생각해. – DavidO
그것은'perldoc Devel :: Peek'에서 나온 것입니다. –
아, 그건 의미가 있습니다. 문서에서'n + n (n - 1)/2k'로 쓰여졌습니다. 이것은'n + n * (n-1)/(2 * k)'와 비슷합니다. – DavidO