스태틱 해시

Static hashing

정적 해싱은 사용자가 최종 사전 세트에 대해 검색을 수행할 수 있는 해싱 문제의 또 다른 형태입니다(사전 내의 모든 개체는 최종 개체이며 변경되지 않음).

사용법

어플

정적 해시는 데이터베이스, 해당 개체 및 참조를 동일하게 유지해야 하므로 애플리케이션이 제한됩니다.드물게 전체 데이터베이스의 전체 재해시만 필요하므로 정보가 거의 변경되지 않는 데이터베이스도 적합합니다.예를 들어 특정 언어의 단어와 정의, 조직의 직원을 위한 중요한 데이터 세트 등이 있습니다.

완벽한 해싱

완전 해시는 n개의 요소 세트를 동일한 크기의 해시 테이블에 저장할 수 있으며 일정한 시간에 룩업을 수행할 수 있는 해시 모델입니다.Fredman, Komlos, Szemerdi(1984)에 의해 특별히 발견되고 논의되었으며, 그래서 "FKS Hashing"[2]이라는 별명이 붙여졌다.

FKS 해시

FKS 해싱은 상위 레벨에 각각 자체 해시 테이블을 포함하는 n개의 버킷이 포함된 2개의 레벨을 가진 해시 테이블을 사용합니다.FKS 해시는 충돌이 발생할 경우 상위 레벨에서만 충돌해야 합니다.

실행

최상위 수준에는 임의로 생성된 해시 함수 h(x)가 포함되어 있으며, 이는 범용 해시에 나타나는 Carter 및 Wegman 해시 함수의 제약 조건 내에 들어맞습니다.이렇게 하면 최상위 레벨에는 k, k2, k3, ..., k라는n 라벨이1 붙은 버킷이 n개 포함됩니다.이 패턴에 따라 모든 버킷에는 s 크기의i 해시 테이블과 각각의 해시 함수 h(x)가i 포함됩니다.해시 함수는 s를 k로 설정하고ii2 충돌이 없을 때까지 함수를 랜덤으로 처리함으로써 결정됩니다.이것은 일정한 시간에 실행할 수 있습니다.

성능

( 2 n 2)쌍의 요소가 존재하며 그 중 충돌 확률이 1/n이므로 FKS 해시는 충돌 횟수가 n/2 미만일 것으로 예상됩니다.이 사실과 충돌 횟수가 최대 n/2가 되도록 각 h(x)를 선택했다는 사실에 기초하여 낮은 수준의 각 테이블의 크기는 2n 이하가 될 것이다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Daniel Roche (2013). SI486D: Randomness in Computing, Hashing Unit. United States Naval Academy, Computer Science Department.
  2. ^ Michael Fredman; János Komlós; Endre Szemerédi (1984). Storing a Sparse Table with O(1) Worst Case Access Time. Journal of the ACM (Volume 31, Issue 3).