cuckoo-hash : 검색시간이 O(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 번 테이블에 원소를 넣는다. 
만약 2번 테이블이 비어있을 경우 기존 원소를 빼버리고 
그 원소에 대해 위 과정을 반복한다.
위 전체 과정을 안정 될 때 까지 반복한다.

뻐꾸기 해시라는 이름이랑 딱 맞게 동작한다. 
작명센스 good 

검색의 경우 두 테이블의 한 엔트리만 확인 하면 되므로 O (1) 


* cycle 발생
위 삽입 과정에서 서로 넣고 빼고를 반복하는 cycle이 생길 수 있다. 
이 경우 h1, h2 해시를 바꿔 리해시. 
(cycle이 안생기는 리해시를 찾는 데 여러번 시도해야 할 수도 있음.)


cuckoo graph를 그려서 cycle 발생 여부를 알 수 있다. 
cuckoo graph는 두 해시테이블 상 해당 값의 위치를 연결한 edge를 그린 것이다. 
이 edge들이 한 개 이하의 cycle 생성시 cuckoo hash의 cycle은 생기지 않는다. 

insert 는 O(1)이 아니다. 
실제론 bucket size를 크게하거나, 테이블 수를 늘리거나, 삽입 시 움직이는 횟수를 제한하는 
꼼수를 두면 실제 사용에서는 매우 효과적으로 동작한다.