일반적인 해시 테이블을 봅시다. 저장해야 할 모든 키는 해시 테이블의 각 항목에 들어갑니다. 해시 테이블 안 항목 개수는 변동될 수 있으며, 각 항목은 해시 함수가 리턴한 값 하나에 대응합니다.

▲ 그림 10-10 일반적인 해시 테이블

 

문제의 핵심을 다시 봅시다. 우리가 원하는 것은 해시 항목의 개수가 달라지더라도 리해시를 하지 않는 것입니다. 항목 개수를 추상적으로 엄청나게 많게 하고 “이 이상의 항목은 있을 수 없다!”라고 명시하면 어떨까요? 그림 10-11과 같을 것입니다.

▲ 그림 10-11 매우 많은 해시 항목

 

그러나 실제로는 해시 항목의 개수가 저렇게 많을 수는 없습니다. 이제 샤드가 한 항목을 담당하는 것이 아니라 앞 항목의 특정 범위를 담당하게 합시다.

뭔가 보이나요? 바로 역발상입니다. 해시 테이블은 항목 개수가 유동적이고 해시 함수 반환 값이 항목 하나에 대응합니다. 우리는 여기서 항목 개수를 고정시키는 대신, 해시 함수 반환 값이 항목 하나에 대응하지 않게 하겠습니다. 한 항목을 해시 함수의 여러 반환 값에 대응하게 하겠습니다. 이것이 일관된 해시입니다. 샤드가 하나밖에 없다면 이렇게 하면 됩니다.

▲ 그림 10-12 한 샤드가 모든 해시 항목을 가짐