consistent hash는 bucket이 추가되더라도, 추가된 버킷으로 이동한 엘리먼트를 뺀 나머지 엘리먼트는 버킷의 변화가 없는 해시를 말한다. 가장 대표적인 게 링에 버킷 구역을 끼워 넣는 karger hash... 근데 대부분의 해시는 버킷 밸런스가 매우 안 좋은 편이다. jump consistent hashgoogle에서 jump consistent hash를 만들었다.버킷이 n개일 때 1개가 추가되면 1(n+1)의 확률로 새로 추가 된 버킷으로 옮겨간다. 이 아이디어를 그대로 옮기면 다음이 된다. ---------------------------------------------------------------------- int ch(int key, int num_buckets) { rand..
The rule to map a key to its bucket can simply be to use the key signature (modulo the number of table buckets) as the table bucket ID: bucket_id = f_hash(key) % n_buckets; By selecting the number of buckets to be a power of two, the modulo operator can be replaced by a bitwise AND logical operation: bucket_id = f_hash(key) & (n_buckets - 1);
* 일반 해시테이블의 한계 일반 해시테이블의 경우 검색이 O (1 + a)인데, 리사이징을 하지 않는 경우, a의 바운더리에 대한 보장이 없다. 이 문제를 해결하는 해시테이블 형태가 있는데 robinhood hash O(log n) , cuckoo hashing O (1), FKS hashing O (1)이 있다. cuckoo hashing은 검색이 O (1)이다! dpdk에서 지원하는 해시 라이브러리기도 하다. dpdk 라이브러리를 보다가 cuckoo hashing이 나와서 찾아봤다. 스탠포드 cs166datat structure렉처 노트를 참고했다. * 동작 해시 테이블은 두 개를 준비하고, 1 번 테이블에 원소를 넣는다. . 만약 해당 엔트리가 차 있을 경우에는 2 번 테이블에 원소를 넣는다. 만약..