- 객관식 해싱은 다중 해시 함수의 구현을 사용하기 때문에 명명되었습니다.
- 높은 수준에서 여러 해시 함수가 있는 경우 각 항목은 여러 버킷에 매핑되므로 Algorithmdesigner는 항목이 상주할 항목을 자유롭게 선택할 수 있습니다.
- 이 자유는 단일 해시 함수를 구현함으로써 얻을 수 있는 것보다 훨씬 더 균형 잡힌 할당을 얻는 알고리즘을 허용합니다.
- 우리는 이러한 알고리즘이 생성하는 할당의 한계를 증명하기 위해 구현된 주요 알고리즘 아이디어와 주요 수학적 도구를 제시할 것입니다.
- 분석이 실제 적용에서 이러한 알고리즘의 효율성을 설명하는 기본 모델의 변형을 견딜 수 있을 만큼 충분히 강력하다는 것을 알게 될 것입니다.
객관식 해싱 알고리즘은 공-통-통 모델의 예를 인용하여 설명됩니다.
- 로드 밸런싱 프로세스에 대한 추론을 위한 일반적인 프레임워크는 수요(키, 프로세스, 파일 등)가 '볼'과 리소스 공급(테이블 슬롯, 서버, 저장 장치 등)은 'bin'으로 표시됩니다.
- 이 설정에서 m no. 일부 할당 규칙을 구현하여 n개의 빈에 의 공을 순차적으로 던집니다.
- 목표는 프로세스 완료 후 빈에 볼 할당을 이해하는 것이며, 일반적으로 최대 로드된 빈의 부하(=볼 수)를 제한합니다.
- 이 모델에 따르면 볼 할당은 하나 이상의 해시 함수를 적용하여 빈에 수행됩니다.
- 이러한 해시 함수는 공의 고유 ID(일반적으로 모델에 암시적)를 일반적으로 1...n으로 번호가 지정된 빈 집합에 매핑하는 역할을 합니다.
- 단지 무작위로 빈을 그리는 대신 해시 함수를 구현하여 빈을 볼에 매핑하는 것은 이후에 볼의 위치를 ID에서 복구해야 하는 일반적인 경우에 유용합니다.