Hash tables with O(1) worst-case lookup and space efficiency [pdf]
1–10 of 45 posts
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#2"WHY ELSE IS THIS COOL?" seems a very casual heading for an academic article.
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#3Cuckoo hashing is not only optimal in theory, it is also very fast in practice. The only downside, though, is that the insert time has linear-time worst case. Thus it may be not the best solution if latency is an issue.
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#4"WHY ELSE IS THIS COOL?" seems a very casual heading for an academic article.
thought exactly the same. define a "cool" way of doing things
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#5An interesting algorithm, and an engaging presentation. If only more academic writing was this accessible!
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#6Cuckoo hashing is not only optimal in theory, it is also very fast in practice. The only downside, though, is that the insert time has linear-time worst case. Thus it may be not the best solution if latency is an issue.
"Linear-time worst case" is different from "amortized constant time", which is what cuckoo hashing provides.
Almost all the containers we use on a regular basis provide only amortized constant time inserts.
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#7Cuckoo hashing is not only optimal in theory, it is also very fast in practice. The only downside, though, is that the insert time has linear-time worst case. Thus it may be not the best solution if latency is an issue.
"Linear-time worst case" is different from "amortized constant time", which is what cuckoo hashing provides. Almost all the containers we use on a regular basis provide only amortized constant time inserts.
Linear time worst case and amortized constant time are not mutually exclusive. You are right that most containers that we use have amortized constant time complexity, but they also have linear worst case complexity. Most times this is because an internal array has to be resized and the contents have to be copied over to the new enlarged array.
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#8It's been my experience that the O(1) was on average, not worst case.
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#9Is open-source implementation of this data structure available somewhere?
Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]
#10"WHY ELSE IS THIS COOL?" seems a very casual heading for an academic article.
It looks like it was a workshop paper, from the 7th Workshop on Distributed Data and Structures. I don't know much about that particular workshop, but workshops often aim for a more informal atmosphere, since one of their main roles is fostering discussion (incl. of works in progress) and bringing communities of researchers together to discuss things.