Boost의 hash_combine 함수가 '마법 상수'를 사용하는 이유는 무엇입니까?

Boost의 hash_combine: 매직 상수로 해시 품질 향상

부스트::hash_combine 함수는 해시 테이블과 함께 사용할 때 중요한 역할을 합니다. 가치를 효율적으로 분배하고 충돌 시나리오를 줄이는 데 있습니다. 결정론적 특성이 일관성을 보장하지만 "마법 상수"를 포함하면 그 의미에 대한 의문이 제기됩니다.

마법 상수 공개

마법 상수는 0x9e3779b9로 표시됩니다. 는 고유한 속성을 가지고 있습니다. 이는 32개의 무작위 비트로 구성되며 각 비트는 0 또는 1이 될 동일한 확률을 갖습니다. 직관적인 가정과 달리 이 상수는 우연히 선택되지 않고 오히려 무리수(의 역수)에서 파생됩니다. 황금 비율.

구체적으로 상수는 2^32/phi의 이진 확장의 처음 32비트로 계산됩니다. 여기서 phi는 황금 비율을 나타냅니다. 이렇게 하면 시드의 각 비트가 상수와 결합될 때 무작위 변환이 수행됩니다.

비트 조작의 이점

상수를 통합함으로써 함수는 두 가지 필수 기능을 달성합니다. 목표:

1. 넓은 분포: 상수가 시드의 모든 부분을 무작위로 변경하므로 유사한 값은 상당히 떨어져 매핑됩니다. 이렇게 하면 인접한 해시 테이블 인덱스에 연속 키가 있을 가능성이 줄어들어 검색 작업의 효율성이 향상됩니다.
2. 향상된 분산: 이전 시드의 이동된 버전을 추가하면 차이점을 전체에 분산시키는 데 도움이 됩니다. hash_value()가 제한된 범위의 값을 생성하는 상황의 모든 비트. 이 단계에서는 시드에 델타를 도입함으로써 입력 값의 작은 편차가 결합된 해시의 더 큰 변화로 이어지도록 보장합니다.

위 내용은 Boost의 hash_combine 함수가 '마법 상수'를 사용하는 이유는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!