표 해싱

컴퓨터 공학에서 표 해싱은 테이블 룩업을 배타적 또는 연산과 결합하여 해시함수의 보편적 패밀리를 구성하는 방법이다.그것은 처음에 컴퓨터 게임을 위한 조브리스트 해싱의 형태로 연구되었다. 후에 카터와 웨그먼의 연구는 이 방법을 임의의 고정 길이 키로 확장시켰다.텍스트 문자열과 같은 가변 길이 키를 처리할 수 있는 표 계산 해싱의 일반화도 개발되었다.

단순함에도 불구하고, 표집 해싱은 다른 해시함수와 구별되는 강력한 이론적 특성을 가지고 있다.특히, 3개의 독립적이다. 모든 3개의 키들은 3개의 해시 값에 매핑될 가능성이 동등하다.그러나, 4개의 독립된 것은 아니다.보다 정교하지만 느린 표 해싱의 변형들은 그 방법을 더 높은 독립도로 확장시킨다.

표 해싱은 독립성이 높아 홉스코치 해싱, 뻐꾸기 해싱 등 고품질 해시함수가 필요한 해싱 방식과 세트 교차로 크기 추정을 위한 민해시 기법으로 사용할 수 있다.

방법

기본적인 생각은 다음과 같다.

첫째, 해시할 키를 선택한 길이의 더 작은 "블록"으로 나눈다.그런 다음 각 블록에 하나씩 룩업 테이블 세트를 만들고 랜덤 값으로 채우십시오.마지막으로 표를 사용하여 각 블록에 대한 해시 값을 계산하고 이러한 해시를 모두 비트 배타적 또는 연산을 사용하여 최종 해시 값으로 결합하십시오.^[1]

좀 더 공식적으로:

p를 해시할 키의 비트 수로 하고, q를 출력 해시함수에서 원하는 비트 수로 한다.블록 크기 r ≤ p를 선택하십시오. 블록 크기의 선택은 시간과 메모리 사용 사이의 절충을 제어하므로 테이블이 너무 크지 않도록(예: 테이블이 컴퓨터의 캐시 메모리에 맞도록) 만들어야 한다.^[2]블록이 작을수록 메모리는 적게 쓰지만 해시함수는 느려진다.계산 t = ceil(p/r), 키를 나타내는 데 필요한 r비트 블록 수입니다.

2차원 2^r × t 배열, T를 만들어 무작위 q비트 숫자로 채운다.이제 T는 주어진 키 x의 해시 값 h(x)를 계산하는 데 사용될 수 있다. 그렇게 하기 위해 x를 r비트 값으로 분할한다. 여기서₀ x는 x의 최저 r비트로, x는₁ 다음 r비트로 구성된다.예를 들어, r = 8이면 x는_i x의 iH 바이트일 뿐이다.그런 다음 이러한 r-비트를 사용하여 T에 인덱스로 배치하고 배타적 또는 연산을 사용하여 결과를 결합하십시오.^[1]

h(x) = T[0][x₀] ⊕ T[1][x₁] ⊕ T[2][x₂] ... … ⊕ T[t-1][x_t-1].

동일한 테이블을 사용하는 것은 유효하지 않다는 점에 유의하십시오(예:각 x에_i 대해 T[0], 그 이후 해시함수는 xs가_i 같은 문자열을 구별할 수 없지만, 다른 방식으로 순열할 수 있을 것이다.

r = t = 8 및 q = p = 64를 사용하는 일반적인 예에 대한 코드는 다음과 같다.

// 임의 번호의 비밀 표 uint64_t T[8][256]; 을 위해 (인트로 i = 0; i < 8; i++)    을 위해 (인트로 j = 0; j < 256; j++)       T[i][j] = getRandomUInt64();  // 단순표 계산 해시 함수 uint64_t 해시하다(uint64_t x) {    uint64_t 재방송하다 = 0;    을 위해 (인트로 i = 0; i < 8; i++)       재방송하다 ^= T[i][(마를 뜨다)(x >> 8*i)];    돌아오다 재방송하다; } 

역사

표 해싱의 첫 번째 예는 조브리스트 해싱으로, 1970년에 그것을 출판한 알버트 린지 조브리스트의 이름을 딴 체스 같은 추상 보드 게임에서 해싱 포지션을 위한 방법이다.^[3]이 방법에서는 체스 조각과 체스판의 사각형의 조합과 같은 각 게임 특징에 대해 무작위 비트 스트링이 생성된다.그런 다음, 어떤 게임 포지션을 해싱하기 위해, 그 포지션의 특징에 대한 비트 스트링이 약간 배타적으로 결합된다.그런 다음 결과 해시 값은 전이 테이블의 인덱스로 사용될 수 있다.각 이동은 일반적으로 적은 수의 게임 기능만 변경하기 때문에 이동 전 위치의 값에서 위치의 조브리스트 값을 빠르게 업데이트할 수 있으며, 위치의 모든 기능을 반복할 필요가 없다.^[4]

임의의 2진수 값에 대해 표 해싱은 더 큰 일반성으로 해싱되었고, 나중에 카터 & 웨그만(1979)에 의해 재발견되었고, Pătracucu & Thorup(2012)에 의해 더 자세히 연구되었다.

보편성

Carter & Wegman(1979)은 해시함수가 충돌할 확률(즉, 서로 동일한 값으로 매핑됨)이 1/m인 경우 해시함수를 보편적으로 생성하기 위한 무작위화된 체계를 정의한다. 여기서 m은 키가 취할 수 있는 값의 수입니다.그들은 후속 종이 Wegman은 & 경우의 열쇠를 모든 k-tuple 그리고 가치의 각각 가능한 k-tuple에 확률은 해당 키를 이러한 값에 매핑 되어 있지는 않다 1/mk.2-independent 해싱 계획 자동으로 보편적이라고 카터는(1981년):해시 함수를 생성하는 임의적인 음모,k-independent 더 강한 속성 정의했다.조금도범용 해싱 체계는 알고리즘의 초기화 단계의 일부로 무작위 숫자 x를 저장하고 각 해시 값에 x를 추가함으로써 2개의 독립적인 체계로 변환될 수 있다.그러므로 보편성은 본질적으로 2독립과 같다.그러나 더 큰 k 값에 대한 k-독립성은 해싱 알고리즘의 수가 더 적은 더 강한 특성이다.

Pătraşcu & Thorup(2012)에서 관찰한 바와 같이, 표 해싱은 3개 독립적이지만 4개 독립적이지는 않다.어떤 단일 키 x에 대해서도 T[x₀,0]가 해시 값을 차지할 가능성이 같으며, 나머지 테이블 값이 있는 T[x₀,0]의 배타적 또는 T[x,0]는 이 속성을 변경하지 않는다.어떤 두 개의 키 x와 y에 대해서도 x는 이전과 같은 해시 값에 매핑될 가능성이 있으며, x_i y_i y에 최소한 하나의 위치 i가 있다; 테이블 값 T[y_i,i]는 h(x)의 계산에는 사용되지만 h(x)의 계산에는 사용되지 않기 때문에 h(x)의 값이 결정된 후에도 h(y)는 유효한 해시 값이 될 가능성이 동등하다.마찬가지로, 어떤 세 개의 키 x, y, z에 대해, 적어도 세 개의 키 중 하나는 그 값 z가_i 다른 두 개와 다른 위치 i를 가지고 있으므로, h(x)와 h(y)의 값이 결정된 후에도 h(z)는 모든 유효한 해시 값이 될 가능성이 동등하다.^[5]

그러나 이 추론은 4개의 키에 대해 분해되는데, 4개의 키 중 어느 것도 다른 키 하나와 공유하지 않는 바이트 값을 가진 키가 없기 때문이다.예를 들어, 키가 각각 2바이트이고 w, x, y, z가 바이트 값으로 0 또는 1을 갖는 4개의 키라면, 각 위치의 각 바이트 값은 4개의 키 중 정확히 2개로 공유된다.이 네 개의 키에 대해, 표 계산 해싱에 의해 계산된 해시 값은 항상 h(w) ⊕ h(x) ⊕ h(y) ⊕ h(z) = 0 등식을 만족하는 반면, 4개의 독립 해싱 체계의 경우 동일한 등식은 확률 1/m에서만 충족된다.따라서 표 해싱은 4개 독립적이지 않다.^[5]

적용

표 해싱은 범용 해싱 방식이기 때문에 보편성이 충분한 해싱 기반 알고리즘에서 사용할 수 있다.예를 들어, 해시 체인의 경우, 연산당 예상 시간은 충돌 확률의 합계에 비례하며, 이는 모든 범용 체계에서 실제 랜덤 해시 함수와 동일하며, 해시 테이블의 부하 계수가 일정할 때마다 일정하다.따라서 표집 해싱은 연산당 일정한 예상 시간을 이론적으로 보장하여 해시 체인을 위한 해시함수를 계산하는 데 사용할 수 있다.^[6]

그러나 유니버설 해싱은 일부 다른 해싱 알고리즘의 성능을 보장하기에 충분하지 않다.예를 들어, 선형 프로빙의 경우 5개의 독립 해시함수가 일정 시간 연산을 보장할 만큼 강하지만, 실패하는 독립 해시함수는 4개가 있다.^[7]그럼에도 불구하고, 표 해싱은 3개 독립적임에도 불구하고 선형 탐색을 위해 동일한 일정 시간 보증을 제공한다.^[8]

해시 테이블을 구현하는 또 다른 기술인 뻐꾸기 해싱은 (해시함수와 무관하게) 조회당 일정한 시간을 보장한다.뻐꾸기 해시 테이블의 삽입이 실패하여 전체 테이블이 재구축될 수 있지만, 이러한 실패는 삽입당 예상 시간(정확히 랜덤 해시함수 또는 로그 독립성이 있는 해시함수 사용)이 일정할 가능성은 충분히 낮다.반면, 표 해싱의 경우, 고장 확률에 대해 알려진 최선의 경계는 더 높으며, 삽입이 일정한 예상 시간을 소요한다고 보장할 수 없을 정도로 높다.그럼에도 불구하고 표 해싱은 테이블을 사용할 때 변경되지 않는 정적 키 집합에 대한 뻐꾸기 해시 테이블의 선형 예상 시간 구성을 보장하기에 충분하다.^[8]

확장

위에서 설명한 표 해싱("단순표 해싱")은 3개 독립적일 뿐이지만, 이 방법의 변형을 사용해 독립성이 훨씬 높은 해시함수를 얻을 수 있다.Siegel(2004)은 키비트를 테이블 지수로 변환하기 위한 확장자 그래프를 기반으로 한 보다 복잡한 알고리즘을 사용하여 배타적 또는 표의 무작위 값을 결합하는 것과 동일한 아이디어를 사용하여 k의 상수 또는 심지어 로그 값에 대해 k-독립적인 해싱 체계를 정의한다.그러나 시겔의 표집 해싱의 변동을 이용하여 각 해시 값을 계산하는 데 필요한 테이블 룩업의 수는 일정하지만, 여전히 너무 커서 실용적이지 못하며, 시겔의 기법에 익스팬더를 사용하는 것 역시 완전히 건설적이지는 않다.Thorup(2013년)은 표 해싱을 기반으로 하여 독립성이 높은 정도에 보다 빠르게, 보다 건설적인 방식으로 계획을 제공한다.그는 단순표 해싱 1라운드를 사용하여 입력 키를 원래 길이의 6배까지 확장한 다음, 2라운드의 단순표 해싱은 확장된 키에 대해 해싱(hashing) 방식으로 생성되며, 이러한 해싱(parameter r)의 독립성 번호가 매개 변수 r에서 지수적이며, 키 파티션에서 블록당 비트 수(bits)가 입력 키의 원래 길이의 6배까지 확장된 것을 관찰한다.블록들

단순 표는 일정한 길이의 키로 제한되는데, 이는 키에서 블록의 각 위치에 대해 서로 다른 랜덤 값의 표를 초기화해야 하기 때문이다.Lemire(2012)는 문자열과 같은 가변 길이 키에 적합한 표 해싱의 변형을 연구한다.Lemire가 연구한 일반적인 유형의 해싱 체계는 키 내의 위치에 관계없이 블록 값에 의해 색인화된 단일 테이블 T를 사용한다.그러나 이 표의 값은 비트 배타적 함수보다 더 복잡한 함수에 의해 결합될 수 있다.Lemire는 이러한 유형의 어떤 계획도 3개 독립적일 수 없다는 것을 보여준다.그럼에도 불구하고 그는 2독립을 달성하는 것이 여전히 가능하다는 것을 보여준다.특히 T[x_i] 값(여기서 x는_i 이전과 같이 입력의 ih 블록)을 유한장에 대한 다항식의 계수로 해석한 후, 그 결과 다항식의 나머지 부분을 또 다른 다항식으로 취함으로써 2개의 독립적인 해시함수를 갖는 표 체계도 있다.

혼합표

혼합표 해싱(및 덜 일반적인 비틀림표 해싱)은 거의 동일한 성능을 유지하면서 표 해싱의 특성을 강화하는 방법으로 달가르드와 토럽에^[9] 의해 도입되었다.혼합표계는 단순표표표 해시함수를 가진 xor'ing "Double Tabulation" Thorup(2013) 해시함수로 볼 수 있다.이것은 혼합표를 이중표보다^[10] 훨씬 빨리 만들기 위해 매개변수를 선택해도 좋은 특성을 많이 가진 것으로 밝혀졌다.

${\displaystyle {단순히}^{}}$ $2q{\displaystyle }$ ${\$가 아닌 ${\displaystyle {\mathrm{2r}}^{}}$d +$q$ {\$displaystyle$ 2^{rd$+q}$비트에$$ d ${\displaystyle d}$을(를) 선택하여 해시함수로 해시되며 $두{\displaystyle }$ 값이 함께 xor'로 표시된다$.$Formally we have ${\displaystyle h_{1}:[2^{p}]\to [2^{rd}]\times [2^{q}]}$ and ${\displaystyle h_{2}:[2^{rd}]\to [2^{q}]}$, both simple tabulation functions.$({\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{v\mathrm{}}_{}}$ ${\displaystyle {}_{}}$)${\displaystyle }$= h ${\displaystyle {1\mathrm{}}_{}}$ (${\displaystyle {}_{}}$x${\displaystyle }$) ${\displaystyle (v_{1},v_{2}=h_{1}(x$인 경우 혼합표 해시는 h${\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle {h\mathrm{}}_{}}$ 2 ( v ${\displaystyle {1\mathrm{}}_{}}$ )${\displaystyle {}_{}{}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ . ${\displaysty h(x)=h_{1$}($v_{1})\plus v_{$2}.$}$

다음 예제는${\displaystyle }p{\displaystyle }$ =${\displaystyle q}$ = ${\displaystyle 64}$ ${\displaystyle p=q=$64$\},$ $r{\displaystyle }$= ${\displaystyle 8}$ ${\displaystyle r=8}$ 및$$ $d{\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle d=2}$을(를) 사용하는 알고리즘을 보여준다$.$

인트로 D = 2; uint128_t T1[8][256]; uint64_t T2[D][256];  // 랜덤 값으로 표 채우기 을 위해 (인트로 j = 0; j < 256; j++) {    을 위해 (인트로 i = 0; i < 8; i++)       T1[i][j] = getRandomUInt128();    을 위해 (인트로 i = 0; i < D; i++)       T2[i][j] = getRandomUInt64(); }  // D 파생 문자를 포함한 x의 혼합 표 계산 uint64_t 해시하다(uint64_t x) {    uint128_t v1v2 = 0;    을 위해 (인트로 i = 0; i < 8; i++)       v1v2 ^= T1[i][(마를 뜨다)(x >> 8*i)];    uint64_t v1 = v1v2 >> 64;     // 로우비트에서 v1 가져오기    uint64_t h = (uint64_t) v1v2; // 하이비트에서 v2 가져오기    을 위해 (인트로 i = 0; i < D; i++)       h ^= T2[i][(마를 뜨다)(v1 >> 8*i)];    돌아오다 h; } 

혼합표계는 플라졸레와 마틴의 고전적 방법 등 구별되는 요소들을 계산하는 알고리즘에 유용한 k-파티션에 대해 집중력이 강한 것으로 2016년에^[11] 나타났다.

메모들

참조

이차 출처

• Morin, Pat (February 22, 2014), "Section 5.2.3: Tabulation hashing", Open Data Structures (in pseudocode) (0.1Gβ ed.), pp. 115–116, retrieved 2016-01-08.
• Mitzenmacher, 마이클 Upfal, 엘리(2014년),"어떤 실용적인 임의적인 알고리즘 및 데이터 구조", 터커 형, 앨런에, 곤잘레스, Teofilo, Diaz-Herrera, 호르헤(eds.), 컴퓨팅 핸드 북:.전산 소프트웨어 공학(3판), CRC출판부를 대신하여 서명함. 11-1에는 – 11-23, 아이 에스비엔 9781439898529.특정 섹션 11.1.1:Tabulation 해시,를 대신하여 서명함에 11-3– 11-4참조하십시오.

일차 출처