http://en.wikipedia.org/wiki/Cuckoo_hashing
왜 들어본적도 없는걸까요 OTL. lookup이 worst case에 O(1). insertion은 rehash 해도 테이블 크기만 적당하면 worst case로 O(1).
Cuckoo hashing
Tags:
Comments
4 responses to “Cuckoo hashing”
-
시간복잡도만 보고 ‘수행시간에 constant 성분이 많은 거 아냐?’ 하고 지레짐작했으나, 실제로 알고리즘을 읽어보니 의외로 매우 간단하군요. 상당히 매력적입니다. 덕분에 좋은 것을 알게 되었습니다. 감사합니다.
그런데 혹시 insertion 시간 worst case O(1)은 expected O(1) 을 잘못 쓰신 것이 아닌지요?
-
아!!! 그렇군요;; expected 입니다.
-
직접 짜서 돌려본 바로는 자바 기본 Hash랑 큰 차이를 못 느끼고 있습니다. ; 내가 잘못 짠건가;;;
-
역시 구현이나 성능 테스트나 정말 쉽지 않은 일입니다…
Leave a Reply