https://stackoverflow.com/questions/231438
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
누구든지 구현이 있습니까? 뻐꾸기 해싱 C에서? 오픈 소스가 있다면 GPL이 아닌 버전이 완벽 할 것입니다!
Adam이 자신의 의견에 대해 언급 한 이후로, 왜 그것이 많이 사용되지 않았는지 아는 사람이 있습니까? 그것은 단지 구현의 문제일까요, 아니면 좋은 이론적 특성이 실제로 실현되지 않습니까?
다른 팁
다른 답변이 지적했듯이, 가장 간단한 뻐꾸기 해시 테이블은 테이블을 반으로 비워야한다는 것이 사실입니다. 그러나이 개념은 일반화되었습니다 디-각 키가 가지고있는 뻐꾸기 해싱 디 간단한 버전의 2 개의 장소와 달리 둥지를 둥글게 할 수있는 장소.
허용 가능한 하중 계수는 다음과 같이 빠르게 증가합니다 디 증가합니다. 만 디= 3, 이미 75% 전체 테이블을 사용할 수 있습니다. 단점은 당신이 필요하다는 것입니다 디 독립 해시 함수. 나는이 목적을위한 Bob Jenkins의 해시 기능의 팬입니다 (참조 http://burtleburtle.net/bob/c/lookup3.c), 뻐꾸기 해싱 구현에서 유용 할 수 있습니다.
Cuckoo Hashing은 학계 이외의 외부에서 비교적 사용되지 않습니다 (때로는 아이디어를 빌려 주지만 실제로 완전히 구현되지는 않는 하드웨어 캐시 제외). 삽입에 좋은 시간을 얻으려면 매우 드문 해시 테이블이 필요합니다. 테이블의 51%가 우수한 성능을 얻으려면 정말로 비어 있어야합니다. 따라서 빠르고 많은 공간을 차지하거나 느리게하고 공간을 효율적으로 사용합니다. 다른 알고리즘은 시간과 공간 만 효율적이지만 시간이나 공간 만 고려할 때 뻐꾸기보다 나쁩니다.
여기에 있습니다 뻐꾸기 해시 테이블 용 코드 생성기. 출력이 GPL이 아닌지 확인하려면 생성기의 라이센스를 확인하십시오. 어쨌든 확인하십시오.
-아담
오래된 질문이지만 누군가가 여전히 관심이있을 수 있습니다 :)
이 종이 GPU (CUDA/OpenCL)에서 병렬 D- 아리 뻐꾸기 해시의 구현을 설명합니다. 그것은 매우 잘 설명되어 있으며 설명을 기반으로 구현하는 것은 매우 쉽습니다. 이 주제에 관심이 있다면 일반적으로 읽을 가치가 있습니다. (그래도 ACM 로그인이 필요합니다.)
IO 언어에는 Phash.c에 하나가 있습니다. 당신은 찾을 수 있습니다 IO 코드 Github에서. IO는 BSD 라이센스가 부여되었습니다.
나는 활용에 대한 요점을 보았지만 이것은이 특정 해싱 체계를 시도한 나의 추론이었습니다. 내가 뭔가를 놓친 지 알게 해주세요.
내가 아는 한, 동적 사전을 만들기 위해 해시 타이블에 대한 가능한 대안은 (균형) 이진 트리와 건너 뛰기입니다. 토론을 위해서는 키와 가치 유형에서 추상화하고 우리가 void *.
이진 트리의 경우 다음을 가질 것입니다.
struct node {
void *key;
void *value;
struct node *left;
struct node *right;
}
따라서 포인터가 모두 같은 크기를 가지고 있다고 가정합니다 에스, 저장 N 아이템이 필요합니다 에스 바이트.
건너 뛰기리스트는 노드의 평균 포인터 수가 2와 거의 동일합니다.
해시 테이블에서는 다음과 같습니다.
struct slot {
void *key;
void *value;
}
따라서 각 항목은 2 만 requre입니다 에스 저장 될 바이트. 하중 계수가 50%인 경우 저장 N 아이템이 필요합니다 에스 나무로 바이트.
Cuckoo Hashtable은 이진 트리와 거의 같은 양의 기억력을 차지하지만 O (log n)가 아닌 O (1) 액세스 시간을 줄 것입니다.
트리의 균형을 유지하는 복잡성과 노드에 균형 정보를 저장하는 데 필요한 추가 정보를 계산하지 않습니다.
다른 해싱 체계는 최악의 사례 액세스 시간 (O (N) 일 수도 있음)에 대한 보장없이 더 나은 하중 계수 (75% 또는 80%)를 달성 할 수 있습니다.
그런데, D-Ary Cuckoo 해싱 그리고 "숨겨진 뻐꾸기 해싱"일정한 액세스 시간을 유지하면서로드 계수를 늘릴 수있는 것 같습니다.
Cuckoo Hashing은 나에게 귀중한 기술 인 것처럼 보이며 나는 그것이 이미 탐구되었다고 생각했습니다. 그것이 내 질문의 이유입니다.
나는 소프트웨어에 대해서는 말할 수 없지만 뻐꾸기 해싱은 확실히 하드웨어에 사용되며 매우 인기가 있습니다. 네트워킹 장비의 주요 공급 업체는 뻐꾸기 해싱을 조사하고 있으며 일부는 이미 사용하고 있습니다. Cuckoo Hashing에 대한 매력은 물론 지속적인 조회 시간뿐만 아니라 거의 일정한 삽입 시간에서 비롯됩니다.
삽입은 이론적으로 무한할 수 있지만 실제로는 테이블의 행 수의 O (log n)로 제한 될 수 있으며 측정시 삽입 시간은 평균적으로 약 1.1*d 메모리 액세스입니다. 그것은 절대 최소값보다 10% 더 높습니다! 메모리 액세스는 종종 네트워킹 장비의 제한 요소입니다.
독립 해시 함수는 필수이며 제대로 선택하는 것은 어렵습니다. 행운을 빕니다.
"OneByone"의 의견에 따라 실제 메모리 요구 사항을 결정하기 위해 몇 가지 버전의 Cuckoo Hashing을 구현하고 테스트했습니다.
일부 실험 후, 테이블이 거의 50%가 가득 차있을 때까지 다시 할 필요가 없다는 주장은 사실 인 것처럼 보입니다.숨기는 장소"트릭은 이식됩니다.
문제는 테이블을 확대 할 때입니다. 일반적인 접근 방식은 크기를 두 배로 늘리는 것이지만 새로운 테이블은 25%에 불과합니다!
실제로, 해시 테이블에 16 개의 슬롯이 있다고 가정하면, 8 번째 요소 번호를 삽입하면 좋은 슬롯이 떨어지고리스가되게됩니다. 나는 그것을 두 배로 늘릴 것이고 이제 테이블은 32 개의 슬롯으로, 그 중 8 명만 점유되어 75% 폐기물입니다!
이것은 "일정한"검색 시간을 갖기 위해 지불하는 가격입니다 (액세스/비교 수에 대한 상한 측면에서).
그래도 다른 스키마를 고안했습니다. 1보다 큰 2의 전력에서 시작하여 테이블에 N 슬롯이 있고 N이 2의 전원이면 N/2 슬롯을 추가하여 N/3 슬롯을 추가합니다.
+--+--+
| | | 2 slots
+--+--+
+--+--+--+
| | | | 3 slots
+--+--+--+
+--+--+--+--+
| | | | | 4 slots
+--+--+--+--+
+--+--+--+--+--+--+
| | | | | | | 6 slots
+--+--+--+--+--+--+
+--+--+--+--+--+--+--+--+
| | | | | | | | | 8 slots
+--+--+--+--+--+--+--+--+
등.
테이블이 50% 가득한 경우에만 다시 발생한다는 가정과 함께 테이블은 리아스 후 (1/3)가 아닌 66% 비어 있음 (1/3)이라는 사실로 이어집니다. 즉, 최악의 경우).
또한 SQRT (N)에 의해 매번 확대되는 공간이 50%에 이르는 공간이 50%에 이르는 것을 알아 냈습니다 (그러나 여전히 수학을 확인해야합니다).
물론 메모리 소비를 줄이기 위해 지불하는 가격은 결국 필요한리스 수의 증가입니다. 아아, 무료로 나오는 것은 없습니다.
누군가 관심이 있다면 더 조사 할 것입니다.
