tag:blogger.com,1999:blog-8890204.post2982539486251769135..comments2023-02-07T09:21:06.215-05:00Comments on My Biased Coin: Cuckoo Hashing, Theory and Practice: Part 2Michael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-8890204.post-27220802873764661702008-10-21T14:03:00.000-04:002008-10-21T14:03:00.000-04:00martinus, I think you misunderstood the point. The...martinus, I think you misunderstood the point. The loop is certainly detectable. The problem is that it might take a long time to detect, which is unacceptable to some real time applications. <BR/><BR/>--HaoyuHaoyu Songhttps://www.blogger.com/profile/14732307630016381362noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-55947635453592712042007-07-31T01:39:00.000-04:002007-07-31T01:39:00.000-04:00Hi, I am just playing around with cockoo hashing, ...Hi, I am just playing around with cockoo hashing, I think you are missing something in point 2: You are right that cuckoo hashing can get caught in a loop, but this is easy to detect. On insertion, remember the position where the new element is put. Elements are pushed around, and after a while it might be that the inserted element is pushed to another position (count up by 1). Now some more elements are pushed around, and eventually the first inserted element is pushed again, and this is when there has to be a circle.<BR/><BR/>So in practice it should be enough to count the moves of the inserted element. If it is moved 3 times, you have a loop.<BR/><BR/>PS: I am no mathematician so I can't prove this, but it seems to work :-)Martin Ankerlhttps://www.blogger.com/profile/03276855352578119354noreply@blogger.com