뻐꾸기 해싱

쿠쿠 해싱(Cuckoo hashing)은 컴퓨터 프로그래밍에서 해시 함수 값의 해시 충돌을 해결하기 위한 방법으로 최악의 경우 일정한 룩업 시간을 사용합니다. 이 이름은 일부 뻐꾸기 종의 행동에서 유래되었는데, 뻐꾸기 병아리가 번식 기생이라 불리는 행동의 변형으로 부화할 때 다른 알이나 어린 아기를 둥지 밖으로 밀어내는 것입니다. 유사하게, 뻐꾸기 해싱 테이블에 새로운 키를 삽입하면 오래된 키가 테이블의 다른 위치로 이동할 수 있습니다.

역사

쿠쿠 해싱은 라스무스 파그와 플레밍 프리체 로들러가 2001년 학회 논문에서 처음 기술했습니다.^[1] 이 논문은 2020년 유럽 알고리즘 테스트 심포지엄 상을 수상했습니다.^{[2]: 122}

오퍼레이션스

쿠쿠 해싱은 해시 테이블의 비어 있지 않은 각 셀이 키 또는 키-값 쌍을 포함하는 오픈 어드레싱의 한 형태입니다. 해시 함수는 각 키의 위치를 결정하는 데 사용되며, 테이블의 셀을 조사하여 테이블 내 존재 여부(또는 관련 값)를 확인할 수 있습니다. 그러나 열린 주소 지정은 둘 이상의 키가 동일한 셀에 매핑될 때 발생하는 충돌로 인해 발생합니다. 쿠쿠 해싱의 기본적인 아이디어는 하나의 해시 함수가 아닌 두 개의 해시 함수를 사용하여 충돌을 해결하는 것입니다. 이것은 각 키에 대해 해시 테이블에서 두 가지 가능한 위치를 제공합니다. 일반적으로 사용되는 알고리즘의 변형 중 하나에서 해시 테이블은 크기가 동일한 두 개의 더 작은 테이블로 분할되고 각 해시 함수는 이 두 개의 테이블 중 하나로 인덱스를 제공합니다. 두 해시 함수 모두 인덱스를 하나의 테이블로 제공하는 것도 가능합니다.^{[1]: 121-122}

찾다

쿠쿠 해싱은 $T$ ${\displaystyle 1_{}}$ ${\displaystyle T_{1}}$ 및 ${\displaystyle T_{}}$ 2 ${\displaystyle T_{2}}$의 두 해시 테이블을 사용합니다$.$ $r$ ${\displaystyle$ r$}$을 각 테이블의 길이라고 가정하면 두 테이블에 대한 해시 함수는 $h$ 1${\displaystyle {}_{}}$ ${\displaystyle \text{h}}$ ${\displaystyle 2}$:${\displaystyle }$∪ →${\displaystyle }${${\displaystyle }$0${\displaystyle ,}$ ${\displaystyle ...,}$ ${\displaystyle r}$ - $1$} {\$displaystyle h_{1},\$h_${2}\:\cup$ \$rightarrow$\{0$,$$..,r-1\}}$ and ${\displaystyle \forall x\in S}$ where ${\displaystyle x}$ be the key and ${\displaystyle S}$ be the set whose keys are stored in ${\displaystyle h_{1}(x)}$ of ${\displaystyle T_{1}}$ or ${\displaystyle h_{2}(x)}$ of ${\displaystyle$$T_{2$ 룩업 작업은 다음과 같습니다.^{[1]: 124}

 함수 조회(x)는 반환 ${\displaystyle T_{}}$ $1{\displaystyle {}_{}}$[ ${\displaystyle h_{}}$ ${\displaystyle {}_{}}$( x${\displaystyle }$) ]${\displaystyle }$= x ∨ ${\displaystyle T}$ $2$ [ h 2 ( x ) ] = x {\displaystyle T_{1}[h_{1}(x)]\ =\ x\vee T_{2}[h_{2}(${\displaystyle x}$)] = x} 종료 함수입니다. 

The logical or (${\displaystyle \vee }$) denotes that, the value of the key ${\displaystyle x}$ is found in either ${\displaystyle T_{1}}$ or ${\displaystyle T_{2}}$, which is ${\displaystyle O(1)}$ in worst case.^{[1]: 123}

삭제

$O{\displaystyle (1)}$ ${\displaystyle$ O$(1)}$에서 삭제가 수행되는 이유는 프로빙의 관여가 없기 때문입니다$$. 테이블이 너무 희박한 경우 축소 작업 비용을 고려하지 않습니다.^{[1]: 124-125}

삽입

새로운 아이템을 삽입하는 단계는, 테이블 ${\displaystyle {T1\mathrm{}}_{}}$ {\$displaystyle T_{$1}}의$$ 슬롯 ${\displaystyle {h\mathrm{}}_{}}$ 1$($${\displaystyle x)}$ {\$displaystyle h_{1$}(x$)}$이 점유되어 있는지 여부를 검사하고, 점유되어 있지 않은 경우 해당 셀에 아이템을 삽입하는 단계를 포함합니다. 그러나 슬롯이 점유되어 있으면 사용 중인 항목이 제거됩니다$'$ {\$displaystyle x'}$인 경우$).$ $x{\displaystyle }$ ${\displaystyle$ x$}$은(는) ${\displaystyle {T1\mathrm{}}_{}}$[${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$(${\displaystyle x)]}$ ${\displaystyle T_{1}[h_{1}(x)]}$에 삽입됩니다$.$ 제거된 항목 $x{\displaystyle {}^{\text{'}}}$ ${\$은 동일한 절차에 따라$$ 테이블 ${\displaystyle {T2\mathrm{}}_{}}$ ${\$에 삽입되며, 키를 삽입할 빈 위치가 발견될 때까지 프로세스가 계속됩니다.^{[1]: 124-125} 프로세스 루프에서 발생할 수 있는 무한 반복을 방지하기 위해 ${\displaystyle \text{Max-Loop}}$ ${\$을(를) 지정하여 반복이 고정 임계값을 초과하는 경우, ${\displaystyle {해시\mathrm{}}_{}}$ 테이블($T$$1$ {\$displaystyle$T_{$1}}$ ${\displaystyle {및\mathrm{}}_{}}$T 2 {\$displaystyle$T_$\{$$2}})$은 새로운 해시 함수로 다시 해시되고 삽입 절차가 반복됩니다. 다음은 삽입을 위한 의사 코드입니다.^{[1]: 125}

Lookup(x)이면 1 함수 삽입기(x)가 2이고 T ${\displaystyle 1_{}}$[${\displaystyle {}_{}}$ ${\displaystyle 1_{}x))]}$ ${\$$displaystyle$ $T_{1}[h_{1}(x)]}$ = ⊥ ${\displaystyle$\bot} 다음 7 T 1 [h 1(x)] {\displaystyle T_{1}[h_{1}(x)] : = x 8이 9를 반환하면 10       x ${\displaystyle \leftrightarrow T_{1}[h_{1}(x)]}$ 11       if ${\displaystyle T_{2}[h_{2}(x)]}$ = ${\displaystyle \bot }$ then 12         ${\displaystyle T_{2}[h_{2}(x)]}$ := x 13         return 14       end if 15       x ${\displaystyle \leftrightarrow T_{}}$${\displaystyle 2_{}}$[ ${\displaystyle h}$ ${\displaystyle {2\mathrm{}}_{}}$( x${\displaystyle }$)${\displaystyle }$] ${\displaystyle \leftrightarrow T_{2}[h_{2}(x))}$ 16$$ end loop 17 rehash() 18 insert(x) 19 end function 

10행과 15행에서는 $T{\displaystyle {}_{}}$ ${\displaystyle {1,}_{}}$ 2${\displaystyle {}_{}}$[${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{},}_{}}$ 2 ${\displaystyle {}_{}x}$)${\displaystyle }$] ${\displaystyle T_{1, 2}[h_{1, 2}(x$에 선점되어 있던 다른 키를 발로 차는 "cuckoo 접근 방식"이 모든 키가 자신의 "둥지" 즉, 자신의 "둥지"를 가질 때까지 발생합니다. $항목$ x ${\displaystyle x}$이(가) 두 테이블 중 하나의 지점에 삽입됩니다. 표기 ↔ {\$displaystyle \leftrightarrow}$는 스왑 프로세스를 표현합니다.

이론.

키 수가 해시 테이블 용량의 절반 이하, 즉 부하 계수가 50% 이하로 유지되는 한, 테이블을 재구축해야 할 가능성을 ^[1]고려하더라도 삽입은 예상되는 일정 시간에 성공합니다.

이를 증명하는 한 가지 방법은 랜덤 그래프 이론을 사용합니다: 각 해시 테이블 위치에 대한 정점과 각 해시 값에 대한 에지가 있는 "쿠쿠 그래프"라고 하는 무방향 그래프를 형성할 수 있으며, 에지의 끝점은 값의 두 가지 가능한 위치입니다. 그런 다음 값 집합을 쿠쿠 해시 테이블에 추가하기 위한 그리디 삽입 알고리즘은 이 값 집합에 대한 쿠쿠 그래프가 연결된 각 구성 요소에서 최대 한 주기를 갖는 그래프인 의사 포리스트인 경우에만 성공합니다. 모서리가 정점보다 많은 정점 유도 부분그래프는 해시 테이블에 슬롯 수가 부족한 키 집합에 해당합니다. 해시 함수를 임의로 선택하면 쿠쿠 그래프는 Erd ős-Rennyi 모델에서 임의의 그래프입니다. 확률이 높은 로드 팩터가 1/2 미만인 경우(가장자리 수 대 정점 수의 비율이 1/2 미만인 랜덤 그래프에 해당), 그래프는 의사 숲이며 쿠쿠 해싱 알고리즘은 모든 키를 배치하는 데 성공합니다. 같은 이론은 또한 뻐꾸기 그래프의 연결된 구성 요소의 예상 크기가 작다는 것을 증명하므로 각 삽입에 일정한 예상 시간이 소요됩니다. 그러나 확률이 높은 경우에도 부하 계수가 1/2을 초과할 경우 두 개 이상의 사이클을 가진 거대한 구성 요소가 발생하여 데이터 구조에 장애가 발생하고 크기를 조정해야 합니다.^[3]

이론적 무작위 해시 함수는 실제 사용을 위해 너무 많은 공간을 필요로 하기 때문에, 중요한 이론적 문제는 어떤 실제 해시 함수가 쿠쿠 해시에 충분한지입니다. 한 가지 접근 방식은 k-독립 해시를 사용하는 것입니다. 2009년에는 $O{\displaystyle (\log }$ ⁡$n$) ${\displaystyle$ O$(\$log n)} -독립성으로 충분하며 적어도 6-독립성이 필요하다는 것을 보여주었습니다. 또 다른 접근법은 6-독립적이지는 않지만 2012년에^[5] 쿠쿠 해싱에 충분한 다른 속성을 갖는 것으로 나타난 타블레이션 해싱을 사용하는 것입니다. 2014년의^[6] 세 번째 접근 방식은 소위 스테이시로 쿠쿠 해시 테이블을 약간 수정하는 것인데, 이를 통해 2-독립 해시 함수만 사용할 수 있습니다.

연습

실제로 뻐꾸기 해싱은 선형 탐사보다 약 20~30% 느리며, 이는 일반적인 접근법 중 가장 빠릅니다.^[1] 그 이유는 쿠쿠 해싱은 종종 검색당 2개의 캐시 미스를 야기하고 키가 저장될 수 있는 두 위치를 확인하는 반면 선형 프로빙은 일반적으로 검색당 1개의 캐시 미스만을 야기하기 때문입니다. 그러나 검색 시간에 최악의 경우가 보장되기 때문에 실시간 응답률이 필요할 때 쿠쿠 해싱은 여전히 가치가 있습니다. 쿠쿠 해싱의 한 가지 장점은 GPU 처리에 잘 맞는 링크 리스트 자유 속성입니다.

예

다음 해시 함수가 제공됩니다.

${\displaystyle h\left(k\right)=k{\bmod {1}}$
${\displaystyle h'\left(k\right)=\left\lfloor {\frac {k}{11}\rfloor {\bmod {1}}$

다음 두 표는 몇 가지 예제 요소의 삽입을 보여줍니다. 각 열은 시간 경과에 따른 두 해시 테이블의 상태에 해당합니다. 각 새 값에 대해 가능한 삽입 위치가 강조 표시됩니다.

사이클

지금 원소 6을 삽입하려고 하면 사이클이 시작되고 실패합니다. 표의 마지막 행에서 우리는 다시 처음과 같은 초기 상황을 발견합니다.

${\displaystyle h\left(6\right)=6{\bmod {1}}1=6}$
${\displaystyle h'\left(6\right)=\left\lfloor {\frac {6}{11}\rfloor {\bmod {1}}1=0}$

변주곡

쿠쿠 해싱의 여러 가지 변형이 연구되었으며, 주로 기본 알고리즘의 50% 임계값보다 높은 수치로 허용 가능한 부하 계수를 증가시켜 공간 사용을 개선하는 것을 목표로 합니다. 이러한 방법 중 일부는 쿠쿠 해싱의 실패율을 줄이는 데에도 사용될 수 있어 데이터 구조의 재구축 빈도가 훨씬 적습니다.

두 개 이상의 대체 해시 함수를 사용하는 쿠쿠 해시의 일반화는 일부 룩업 및 삽입 속도를 희생시키면서 해시 테이블의 용량의 더 큰 부분을 효율적으로 활용할 것으로 예상할 수 있습니다. 3개의 해시 함수만 사용하면 부하가 91%^[7]로 증가합니다.

차단된 뻐꾸기 해싱이라고 불리는 뻐꾸기 해싱의 또 다른 일반화는 버킷당 하나 이상의 키와 균형 잡힌 할당 체계를 사용합니다. 버킷당 2개의 키만 사용하면 80%^[8] 이상의 부하 계수를 얻을 수 있습니다.

연구된 뻐꾸기 해싱의 또 다른 변형은 주머니를 이용한 뻐꾸기 해싱입니다. 이 데이터 구조에서 stash는 구조의 주 해시 테이블에 성공적으로 삽입할 수 없는 키를 저장하는 데 사용되는 일정한 수의 키 배열입니다. 이 수정은 저장 크기를 증가시켜 임의로 크게 만들 수 있는 지수를 갖는 역다항 함수로 쿠쿠 해싱의 실패율을 줄입니다. 그러나 stash가 크다는 것은 stash에 없거나 stash에 있는 키의 검색 속도가 느려진다는 것을 의미하기도 합니다. 스테이시는 두 개 이상의 해시 함수와 결합하거나 차단된 쿠쿠 해싱과 함께 사용하여 높은 부하 계수와 작은 고장률을 모두 달성할 수 있습니다.^[9] 캐시를 사용한 쿠쿠 해싱의 분석은 해싱의 이론적 분석에 일반적으로 사용되는 랜덤 해싱 함수 모델에 그치지 않고 실용적인 해싱 함수로 확장됩니다.^[10]

어떤 사람들은 일부 CPU 캐시에서 왜곡된 연관 캐시라고 불리는 쿠쿠 해싱의 단순한 일반화를 권장합니다.^[11]

쿠쿠 필터라고 불리는 쿠쿠 해시 테이블의 또 다른 변형은 키에 다른 해시 함수를 적용하여 계산된 훨씬 짧은 지문으로 쿠쿠 해시 테이블의 저장된 키를 대체합니다. 이러한 지문들이 뻐꾸기 필터 내에서 이동될 수 있도록 하기 위해, 그것들이 온 키들을 알지 못한 채, 각각의 지문의 두 위치들은 지문과 함께, 또는 지문의 해시(hash)에 의해 서로 계산될 수 있습니다. 이 데이터 구조는 Bloom 필터와 거의 동일한 속성을 가진 대략적인 집합 멤버쉽 데이터 구조를 형성합니다. 이 구조는 키 집합의 멤버를 저장하고 쿼리 키가 멤버인지 여부를 테스트할 수 있으며 거짓 양성(세트의 일부로 잘못 보고된 쿼리)의 가능성이 있지만 거짓 음성은 없습니다. 그러나 Bloom 필터에서는 메모리 사용량이 상수 요인에 의해 더 작고, 참조 로컬리티가 더 좋으며, Bloom 필터와 달리 추가 스토리지 패널티 없이 세트 요소를 빠르게 삭제할 수 있습니다.^[12]

관련 구조물과의 비교

Zukowski et al. 의 연구.^[13] 는 최신 프로세서의 작은 캐시 상주 해시 테이블에 대해서는 쿠쿠 해시가 체인 해시보다 훨씬 빠르다는 것을 보여주었습니다. Kenneth Ross는^[14] 공간 활용도가 높은 대형 해시 테이블의 경우에도 버킷화된 버전의 뻐꾸기 해싱(두 개 이상의 키를 포함하는 버킷을 사용하는 변형)이 기존 방식보다 더 빠르다는 것을 보여주었습니다. 버킷화된 뻐꾸기 해시 테이블의 성능은 Askitis에 의해 추가로 조사되었으며,^[15] 대체 해시 체계와 비교했을 때의 성능입니다.

Mitzenmacher의^[7] 조사는 2009년 현재 뻐꾸기 해싱과 관련된 미해결 문제를 제시합니다.

적용들

Cuckoo Hashing은 TikTok의 추천 시스템에 사용되어 "테이블 충돌 내장" 문제를 해결하고, 이로 인해 모델 품질이 저하될 수 있습니다. 틱톡 추천 시스템 '모놀리스(Monolith)'는 쿠쿠 해싱의 충돌 해상도를 활용해 서로 다른 개념이 동일한 벡터에 매핑되는 것을 방지합니다.^[16]

참고 항목

• 퍼펙트 해싱
• 더블해싱
• 이차 프로빙
• 홉스캐치해싱

참고문헌

외부 링크

• 전통적인 해시 테이블에 대한 멋지고 실용적인 대안, U. Erlingson, M. Manasse, F. Mscherry, 2006.
• 학부생을 위한 쿠쿠 해싱, 2006, R. Pagh, 2006.
• 쿠쿠 해싱, 이론과 실천 (1부, 2부, 3부), Michael Mitzenmacher, 2007.
• Naor, Moni; Segev, Gil; Wieder, Udi (2008). "History-Independent Cuckoo Hashing". International Colloquium on Automata, Languages and Programming (ICALP). Reykjavik, Iceland. Retrieved 2008-07-21.
• 빠른 동시 쿠쿠 해싱을 위한 알고리즘 개선, X. Li, D. 안데르센, M. 카민스키, M. 프리드먼. 유로시스 2014.

예

• C++로 작성된 동시 고성능 Cuckoo 해시 테이블
• C++로 작성된 쿠쿠 해시 맵
• C/C++에 대한 정적 쿠쿠 해쉬테이블 생성기
• 하스켈로 쓰여진 쿠쿠 해쉬 테이블
• 바둑을 향한 뻐꾸기 해싱