repor

#+begin_src c static inline uint32_t bitcnt(uint32_t v) { uint32_t n; for(n=0; v!=0; v&=v-1, n++) ; return (n); }#+end_src v&=v-1, n++ 가 핵심인데 2진수를 v&=v-1 하면, 제일 끝의 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 번 테이블에 원소를 넣는다. 만약..