Cuckoo hashing with C

Question

아무도 C에서 Cuckoo hashing의 구현을 가지고 있습니까? GPL 버전이 아닌 오픈 소스가 있다면 완벽 할 것입니다!

아담이 자신의 의견에서 언급했기 때문에 누구도 사용하지 않는 이유를 알고 있습니까? 그것은 단지 구현의 문제입니까 아니면 훌륭한 이론적 속성이 실제로 구현되지 않습니까?

Answer 1

http://www.mpi-inf.mpg.de/~sanders/programs/cuckoo/

HTH

Answer 2

뻐꾸기 해싱은 학계 밖에서 비교적 사용되지 않습니다 (하드웨어 캐시 이외에도 때로는 아이디어를 빌려주지만 실제로는 완벽하게 구현하지는 않습니다). 그것은 삽입에 좋은 시간을 얻으려면 매우 희소 해시 테이블이 필요합니다 - 당신은 정말 좋은 성능을 위해 테이블의 51 %가 비어 있어야합니다. 따라서 속도가 빠르며 많은 공간을 필요로하거나 속도를 늦추고 효율적으로 공간을 사용합니다. 다른 알고리즘은 시간과 공간을 효율적으로 사용할 수 있지만 시간이나 공간 만 고려할 때 뻐꾸기보다 나쁩니다.

여기는 code generator for cuckoo hash tables입니다. 출력이 GPL이 아닌지 확인하려면 발전기의 라이센스를 확인하십시오. 어쨌든 확인해야합니다.

-adam

Answer 3

IO 언어에는 PHash.c에 하나가 있습니다. Github에서 code for IO을 찾을 수 있습니다. IO는 BSD 라이선스입니다.

Answer 4

사용률에 대한 부분이 있지만이 특정 해싱 스키마를 시도한 이유는 제 생각입니다. 내가 뭔가를 놓친다면 ket me know.

제 생각에는 다이나믹 사전을 만들기위한 해시 테이블의 가능한 대안은 (균형 잡힌) 이진 트리와 skiplists입니다. 토론을 위해 키와 값 유형을 추상화하고 void *을 통해 값에 액세스한다고 가정합시다.

이진 트리를 들어 나는 것 :

struct node { 
    void *key; 
    void *value; 
    struct node *left; 
    struct node *right; 
} 

그래서, 가정 포인터가 N 항목을 저장하기 위해 모두 같은 크기 의을 가지고 내가 4 의 바이트가 필요합니다. 노드의 포인터의 평균 수는 해시 테이블에서 2

을 그대로

Skiplists 내가 가진 것 거의 동일합니다

struct slot { 
    void *key; 
    void *value; 
} 

그래서, 각 항목만이 requre 2 의 저장할 바이트 수. 부하율이 50 % 인 경우 n 항목을 저장하려면 같은 4 바이트가 필요합니다.

뻐꾸기 해시 테이블은 이진 트리만큼 많은 양의 메모리를 차지하지만 O (log n) 대신 O (1) 액세스 시간을 제공합니다.

노드 균형 유지 정보를 저장하는 데 필요한 추가 정보와 트리 균형을 유지하는 복잡성을 고려하지 않았습니다.

다른 해싱 스키마는 최악의 액세스 시간 (심지어 O (n) 일 수도 있음)에 대한 보장없이 더 나은로드 요소 (예 : 75 % 또는 80 %)를 달성 할 수 있습니다.

그런데 d-ary cuckoo hashing과 "cuckoo hashing with a stash"은 일정한 액세스 시간을 유지하면서로드 요소를 늘릴 수있는 것처럼 보입니다.

뻐꾸기 해시는 나에게 가치있는 기술인 것처럼 보이고 이미 탐험되었다고 생각했습니다. 그게 내 질문의 이유 야.

Answer 5

"onebyone"의 의견에 따라 실제 메모리 요구 사항을 결정하기 위해 두 가지 버전의 Cuckoo 해시를 구현하고 테스트했습니다.

실험을 마친 후 테이블이 거의 50 %까지 채워질 필요가 없다는 주장은 사실 일 수 있습니다. 특히 "stash"트릭이 구현 된 경우에는 그렇습니다.

문제는 표를 확대 할 때입니다. 일반적인 접근 방식은 크기를 두 배로 늘리는 것이지만 새 테이블이 25 % 만 사용됩니다.

사실, 해시 테이블에 16 개의 슬롯이 있다고 가정합니다. 8 번째 요소 번호를 삽입 할 때 좋은 슬롯이 부족하여 다시 사용해야합니다. 나는 그것을 두 배로 늘릴 것이고, 이제는 테이블이 32 개 슬롯에 불과하며 8 개가 차지하고 75 %는 낭비입니다!

"일정한"검색 시간 (액세스/비교 수에 대한 상한으로)을 지불하는 대가입니다.

비록 내가 2보다 큰 거듭 제곱으로 시작하고 테이블에 n 개의 슬롯이 있고 n이 2의 거듭 제곱 인 경우 n/2 개의 슬롯을 추가합니다 otherwhise에 n/3 개의 슬롯을 추가하십시오. reashing 전용 테이블이 테이블은 단지 66 % 빈 (1/3)가 될 것이라는 사실에 이르게 50 % 풀 때 발생할 것이라는 가정 함께 등

+--+--+ 
| | |        2 slots 
+--+--+ 

+--+--+--+ 
| | | |       3 slots 
+--+--+--+ 

+--+--+--+--+ 
| | | | |      4 slots 
+--+--+--+--+ 

+--+--+--+--+--+--+ 
| | | | | | |     6 slots 
+--+--+--+--+--+--+ 

+--+--+--+--+--+--+--+--+ 
| | | | | | | | |   8 slots 
+--+--+--+--+--+--+--+--+ 

오히려 (즉, 최악의 경우) 75 % 비어있는 (1/4th).

나는 또한 sqrt (n)에 의해 매번 확대되는 낭비 된 공간이 점차적으로 50 %에 접근한다는 것을 알아 냈다.

물론 메모리 사용량이 적게 드는 데 드는 댓가는 결국 필요한 재앙의 횟수가 증가하는 것입니다. 아아, 아무것도 무료로 제공되지 않습니다.

관심있는 사람이 더 있으면 조사 할 것입니다.

Answer 6

다른 답변이 지적한 것처럼, 그것은 단순한 뻐꾸기 해시 테이블은 테이블이 절반 비어있을 것을 요구한다는 사실이다. 그러나이 개념은 d -ary 뻐꾹 해싱으로 일반화되었으므로 각 키는 d 중첩 할 수있는 위치이며 단순 버전에서는 2 개가됩니다.

d이 증가하면 허용 부하율이 빠르게 증가합니다. d = 3 인 경우 이미 전체 테이블의 약 75 %를 사용할 수 있습니다. 단점은 d 독립 해시 함수가 필요하다는 것입니다. 저는이 목적을 위해 Bob Jenkins의 해시 함수 팬입니다 (http://burtleburtle.net/bob/c/lookup3.c 참조). 이것은 뻐꾸기 해시 구현에 유용 할 수 있습니다.

Answer 7

저는 소프트웨어에 대해 말할 수는 없지만 뻐꾸기 해싱은 하드웨어에서 확실히 사용되고 매우 인기가 있습니다. 네트워킹 장비의 주요 공급 업체는 뻐꾸기 해싱을 찾고 있으며 일부는 이미 그것을 사용하고 있습니다. 뻐꾸기 해시 (cuckoo hashing)에 대한 매력은 물론 상시 조회 시간에서 비롯되지만 일정한 삽입 시간에도 가깝습니다.

삽입이 이론적으로 제한 될 수는 없지만 실제로는 테이블의 행 수의 O (log n)에 바운드 될 수 있으며 측정 된 경우 삽입 시간은 평균 약 1.1 * d 메모리 액세스입니다 . 절대 최소값보다 10 % 더 큽니다! 메모리 액세스는 종종 네트워킹 장비의 제한 요소입니다.

독립 해시 함수가 필수이며 올바르게 선택하는 것은 어렵습니다. 행운을 빕니다.

Answer 8

가, 누군가가 여전히

This paper은 GPU를 (CUDA/OpenCL을)에 병렬 디 - 워 뻐꾸기 해시의 구현에 대해 설명합니다 :) 관심이있을 수있는 오래된 질문은 비록. 설명이 잘되어있어 설명을 기반으로 구현하는 것이 매우 쉽습니다. 이 주제에 관심이 있다면 일반적으로 읽을만한 가치가 있습니다. (ACM 로그인이 필요합니다.)