완벽한 해싱의 정의
완벽한 해싱은 n개의 요소 집합이 동일한 크기의 해시 테이블에 저장될 수 있고 일정한 시간에 조회가 수행될 수 있는 해싱 모델로 정의됩니다. 이것은 Fredman, Komlos 및 Szemeredi(1984)에 의해 특별히 발명되고 논의되었기 때문에 "FKS 해싱"으로 별명을 붙였습니다.
정적 해싱의 정의
정적 해싱은 사용자가 최종 사전 세트에 대한 조회를 수행할 수 있도록 하는 또 다른 형태의 해싱 문제를 정의합니다(즉, 사전의 모든 개체가 최종적이며 변경되지 않음을 의미합니다).
응용 프로그램
정적 해싱은 데이터베이스를 필요로 하기 때문에 해당 개체와 참조는 동일하게 유지되며 응용 프로그램이 제한됩니다. 드물게 변경되는 정보가 포함된 데이터베이스도 드물게 전체 데이터베이스의 전체 재해시가 필요하므로 적격합니다. 이 해싱 체계의 다양한 예에는 단어 집합 및 특정 언어의 정의, 조직 직원에 대한 중요한 데이터 집합 등이 포함됩니다.
구현
정적 경우에는 각각 고유 키와 연결된 총 p개의 항목이 있는 세트가 미리 제공됩니다. Fredman, Komlós 및 Szemerédi는 크기가 s =2(p-1)인 버킷의 첫 번째 수준 해시 테이블을 선택합니다. 구성하기 위해 p 항목은 최상위 해싱 함수에 의해 q 버킷으로 분리됩니다. 여기서 q =2(p-1)입니다. 그런 다음 r개의 항목이 있는 각 버킷에 대해 2단계 테이블에 r2개의 슬롯이 할당되고 해당 해시 함수는 범용 해시 함수 집합에서 무작위로 선택되어 충돌이 없고 해시 테이블과 함께 저장됩니다. 무작위로 선택된 해시 함수가 충돌이 있는 테이블을 생성하는 경우 충돌 없는 테이블이 보장될 때까지 새로운 해시 함수가 무작위로 선택됩니다. 마침내 충돌 없는 해시를 사용하여 r개의 항목이 두 번째 수준 테이블에 해시되었습니다.