Cuckoo hashing

http://en.wikipedia.org/wiki/Cuckoo_hashing

왜 들어본적도 없는걸까요 OTL. lookup이 worst case에 O(1). insertion은 rehash 해도 테이블 크기만 적당하면 worst case로 O(1).

Similar Posts:

Comments 4

  1. Rica wrote:

    시간복잡도만 보고 ‘수행시간에 constant 성분이 많은 거 아냐?’ 하고 지레짐작했으나, 실제로 알고리즘을 읽어보니 의외로 매우 간단하군요. 상당히 매력적입니다. 덕분에 좋은 것을 알게 되었습니다. 감사합니다.

    그런데 혹시 insertion 시간 worst case O(1)은 expected O(1) 을 잘못 쓰신 것이 아닌지요?

    Posted 25 Feb 2007 at 2:20 am
  2. MKSeo wrote:

    아!!! 그렇군요;; expected 입니다.

    Posted 25 Feb 2007 at 11:29 pm
  3. 최종욱 wrote:

    직접 짜서 돌려본 바로는 자바 기본 Hash랑 큰 차이를 못 느끼고 있습니다. ; 내가 잘못 짠건가;;;

    Posted 11 Jun 2007 at 9:13 pm
  4. MKSeo wrote:

    역시 구현이나 성능 테스트나 정말 쉽지 않은 일입니다…

    Posted 12 Jun 2007 at 4:40 pm

Post a Comment

Your email is never published nor shared.