다이내믹 퍼펙트 해싱

Dynamic perfect hashing

컴퓨터 과학에서 동적 완전 해시는 해시 테이블 데이터 [1][2][3]구조에서 충돌을 해결하기 위한 프로그래밍 기술입니다.이 기술은 [citation needed]해시 테이블보다 메모리를 많이 사용하지만 대량의 요소에 대해 빠른 쿼리, 삽입 및 삭제를 수행해야 하는 경우에 유용합니다.

세부 사항

정적 케이스

FKS 스킴

최적의 정적 해싱 문제는 Fredman, Komlos 및 Szemerédi에 [4]의해 일반적으로 해결되었습니다.1984년 [1]논문에서 이들은 (1단계) 해시 테이블의 각 버킷이 별도의 2단계 해시 테이블에 대응하는 2단계 해시 테이블 방식을 자세히 설명합니다.키는 두 번 해시됩니다.첫 번째 해시 값은 첫 번째 수준 해시 테이블의 특정 버킷에 매핑됩니다.두 번째 해시 값은 해당 버킷의 두 번째 수준 해시 테이블에서 해당 엔트리의 위치를 나타냅니다.두 번째 레벨 테이블은 시공 시 충돌 없는 상태(, 완벽한 해싱)가 보장됩니다.이것에 의해, 최악의 경우,[2] 룩업 코스트는 O(1)가 보증된다.

스태틱한 경우 사전에 총 x개의 엔트리가 각각 고유한 키를 가진 세트가 제공됩니다.Fredman, Komlos 및 Szemerédi는 가 s (x - ){ ( [2]버킷인 1단계 해시 테이블을 선택합니다.

구성하기 위해 x 엔트리는 최상위 해시 함수에 의해 s 버킷으로 됩니다. 서 s 2 ( - ){ s (그런 다음 k개의 엔트리가 있는 각 버킷에 대해 두 번째 레벨 테이블에는 k의 슬롯이 할당되고 해당 해시 함수는 충돌이 발생하지 않도록 유니버설 해시 함수 세트에서 랜덤하게 선택되며(즉, 완전한 해시 함수) 해시 테이블과 함께 저장됩니다.랜덤으로 선택된 해시함수가 콜리젼이 있는 테이블을 생성하면 콜리젼이 없는 테이블을 보장할 수 있을 때까지 새로운 해시함수가 랜덤으로 선택된다.마지막으로 충돌 없는 해시를 사용하여 k개의 엔트리가 두 번째 레벨 테이블로 해시됩니다.

의 2차 크기 k^{2는 충돌이 있는 테이블을 무작위로 생성하는 경우가 드물고 k의 크기와 무관하여 선형 상각된 시공 시간을 제공합니다.각 2차 레벨 테이블에는 2차 공간이 필요하지만 1차 레벨 해시 테이블에 삽입된 키가 균일하게 분포되어 있으면 버킷 크기가 작고 확률이 [1]높기 때문에 구조 전체가 O O 공간을 차지합니다.

그래서, x독특한 키 값의 특정 지었지만 T모든 이급 해시 테이블에서 사용하는 전체 면적 O(n){O(n)\displaystyle}공간으로 예상됨에 따라 그 일차적인 해시 함수 특별히고 구체적으로 T<>의+4⋅){\displaystyle T<, s+4\cdot)}. Fredman, Komlós과 Szemerédi 준 것으로 나타났다 선택된다.는 꿈이기 때 문데 내versal 해싱 패밀리 해시 함수에 해당 함수의 절반 이상이 해당 [2]속성을 가집니다.

동적 케이스

Dietzfelbinger 등은 사전에 n개의 항목이 증분 추가되면 멤버십 쿼리가 항상 일정한 시간에 되므로O() 경우 필요한 총 저장공간은 O)\ O(n)\displaystyle O( Odisplay 1O((는) 상각된 삽입 및 삭제 시간(변환된 상수 시간)이 필요합니다.

동적 케이스에서는 키가 해시 테이블에 삽입되었을 때 각 서브테이블 내의 엔트리가 점유되었을 경우 충돌이 발생했다고 간주되며, 새로운 총 엔트리 수 및 랜덤하게 선택된 해시 함수에 기초하여 서브테이블이 재구축된다.제2레벨 테이블의 부하계수가 1(\1/ 유지되기 때문에 재구축은 거의 이루어지지 않으며, 삽입의 상각예상비용은(1O([2] 마찬가지로 에 따른 상각예상비용은O(O(1[2]입니다.

또한 다이내믹 케이스에서는 최상위 테이블 또는 하위 테이블의 최종 크기를 알 수 없습니다.테이블의 O () \ O ( )스페이스를 유지하는 방법 중 하나는 충분한 수의 삽입 및 삭제가 발생했을 때 완전한 재구성을 요구하는 것입니다.Dietzfelbinger 등에 의한 결과에 따르면, 전체 삽입 또는 삭제 건수가 마지막 시공 시점의 요소 수를 초과하는 한 상각된 삽입 및 삭제 예상 비용은 완전한 재분사를 고려하여 (1O(로 유지됩니다.[2]

Dietzfelbinger 등에 의한 동적 완전 해시의 구현.는, 이러한 개념과 지연 삭제를 사용하고 있습니다.다음은 의사 코드로 나타내고 있습니다.

의사 코드의 실장

위치하다

하위 테이블j T의 위치 h(x)에j x(삭제되지 않음)가 포함되어 있으면 함수 Locate(x)는 j:= h(x)입니다. 그렇지 않으면 반환(x는 S에 없음)이 이고 그렇지 않으면 끝입니다.

삽입

j에서 새 엔트리 x 삽입 중 글로벌 연산 카운터인 카운트가 증가합니다.

x가 j에 존재하지만 삭제된 것으로 표시된 경우 마크는 제거됩니다.

x가 j 또는 서브테이블j T에 존재하며 삭제 마크가 붙어 있지 않으면 충돌이 발생하고 j 버킷th 제2레벨 테이블j T가 랜덤으로 선택된 다른 해시함수j h로 재구축된다.

기능 Insert())은 상속 수+1;만약 FullRehash())(카운트>M), 끝나면 다른 j)h()),(위치 hj())의subtable Tj가 들어 있x)만약(x삭제되는 것이 특징이다)을 제거해 delete마커, 끝 끝나면 만약 다른bj=bj+1;만약(bj<>)mj)위치 h.Tj의 j())은빈 가게 Tj의 위치 hj())에 x;끝 만약 다른 하다 모든 표시가 없는 요소의 Tj에 목록 Lj, 열기 탭기 Lj, bj= 길이의 Lj, 반복 hj)중 무작위로 선정된 기능에 Hsj 때까지, hj은injective에 elem.Lj의 ents.목록j L의 모든 y에 대해 y를 T의 위치jj h(y)에 저장합니다. 그렇지 않으면j m = 2 * max{1, mj}, sj = 2 * mj * (mj - 1)입니다. 모든j s의 합계가 32 * M2 / s(M) + 4 * M Allocatej s cells forj T의 경우, 모든 el 표시를 하지 않음.Tj 목록 Lj에 첨부하다)의 Ements;목록에 모두 어두워져서에 Tj의 위치 hj(y)에 Hsj에 반복 hj)중 무작위로 선정된 함수까지 hj Lj의 요소에injective다;Lj 가게는 y;Lj Lj의 bj= 길이를 나열할 권한입니다.                  전기 내내d 그렇지 않으면 FullRehash(x), 그렇지 않으면 end else end else else else end else else end else 

삭제

x를 삭제하면 제거 없이 x가 삭제됨으로 플래그가 표시되고 증분 카운트가 계산됩니다.삽입 및 삭제의 경우 카운트가 임계값 M에 도달하면 테이블 전체가 재구축됩니다.여기서 M은 새로운 페이즈 시작 시 S 사이즈의 일정한 배수입니다.단계에서는 완전 재구축 사이의 시간을 나타냅니다.여기서 "Delete(x)"의 -1은 가능한 모든 요소 U의 집합이 아닌 요소를 나타냅니다.

함수 Delete(x)는 카운트 = 카운트 + 1이고, 하위 테이블 Tj의 위치j h(x)에 x 마크 x가 포함된 경우 삭제됨, 그렇지 않으면 종료(x는 S의 멤버가 아님), 그렇지 않으면 종료(count > = M) FullRehash(-1)인 경우 종료, 종료(count > = FullRehash(-1)인 경우 종료됨

완전 재구축

S 테이블의 완전한 재구축은 먼저 삭제된 것으로 표시된 모든 요소를 제거한 후 다음 임계값 M을 S 크기의 일정한 배수로 설정합니다.s를 s(M) 서브셋으로 분할하는j 해시함수는 다음과 같이 반복하여 랜덤하게 선택된다.

마지막으로 각 서브테이블j T에 대해 해시함수j h가 Tj 원소에 주입될 까지j H에서sj 랜덤으로 반복 선택된다.크기가 n인 S 테이블의 완전한 재구축 예상 시간은 O(n)[2]입니다.

나는 만약(xU에 있) 달다 x에 기능 FullRehash())목록 L에 끝나면 목록 L의 상속 기간, M)(1+c)*max{수, 4}, Hs(M)에 반복 h)중 무작위로 선정된 기능은 모두 j개체, s(M), h()))j에 대한 리스트 Lj Lj의 bj= 길이를&T의 모든 표시가 없는 요소다 있다.      mj를 위해=2*bj, sj x2*mj*(mj-1);끝까지 이 금액의 모든 sj ≤ 32*M2/s(M)+4*M은 모든 j개체, s(M)비로 편성하다 우주 sj에subtable Tj, 반복 hj)중 무작위로 선정된 기능에 Hsj 때까지, hj은injective에 요소를 목록 Lj, 끝의 모든 x에 목록 Lj 가게 exinterest이자락 posi.Tj의tion hj()).과 끝을 잇다

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c Fredman, M. L., Komlos, J. 및 Szemerédi, E. 1984.Worst Case Access Time이 0(1)인 스파스 테이블 저장J. ACM 31, 3(1984년 6월), 538-544 http://portal.acm.org/citation.cfm?id=1884#
  2. ^ a b c d e f g h Dietzfelbinger, M., Carlin, A., Melhorn, K., Meyer auf der Heide, F., R. H. 및 Tarjan, 1994."Dynamic Perfect Hashing: Upper and Lower Bounds" Wayback Machine에 2016-03-04 아카이브되었습니다.SIAM J. Comput. 23, 4(1994년 8월), 738-761.http://portal.acm.org/citation.cfm?id=182370 doi:10.1137/S0097539791194094
  3. ^ Erik Demain, Jeff Lind. 6.897: Advanced Data Structures.MIT 컴퓨터 과학 및 인공지능 연구소.2003년 봄.
  4. ^ Yap, Chee. "Universal Construction for the FKS Scheme". New York University. New York University. Retrieved 15 February 2015.[영구 데드링크]