Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Hash tables with O(1) worst-case lookup and space efficiency [pdf]

ru.is

Post reply on HN
Print view View original

21–30 of 45 posts

Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]

#21

Post by ckuehne »

pmjordan wrote: post #17
ot wrote: post #13

Earlier quoted context omitted.

The linear time behavior of cuckoo hashing is not triggered only when the table has to be enlarged, like standard containers (say, std::vector or python list): a linear numbers of keys can be "cuckooed" out of their slots for an insertion even when the load factor is under the capacity threshold. In standard containers if you pre-define the capacity (say with std::vector::reserve) all the insertions are guaranteed to…

I'm unaware of any hash table implementations which successfully insert elements in absolute constant time in the event of collisions.

Well, there is perfect hashing [1]. Of course it does only work under several assumptions. And you pay for it in terms of time it takes to construct the hash function or in terms of space.

[1] http://en.wikipedia.org/wiki/Perfect_hash_function

Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]

#22

Post by chwahoo »

sambeau wrote: post #2

"WHY ELSE IS THIS COOL?" seems a very casual heading for an academic article.

I like it when academic papers include some personality or touches of informality (in headings or examples for example), as long as the required rigor is not sacrificed elsewhere. Now "why else is his cool?" is probably a bit further than I go.

Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]

#23

Post by silentbicycle »

pmjordan wrote: post #19
ot wrote: post #18

Earlier quoted context omitted.

Chained hash tables have constant time insertion, but I'm not sure about the amortized lookup time (the worst case is linear)

Chaining requires a memory allocation and list insertion on collisions - is it fair to call that absolute constant time? Probability of this happening depends on the number of elements in the container.

Pooling memory for allocating links turns the allocation into amortized constant time.

List insertion is O(1) if you insert it at the head, and while moving the most-recently-accessed link to the head of the chain doesn't change the worst case behavior, it greatly improves the average in practice (and is dead easy).

Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]

#25

Post by ot »

pmjordan wrote: post #19
ot wrote: post #18

Earlier quoted context omitted.

Chained hash tables have constant time insertion, but I'm not sure about the amortized lookup time (the worst case is linear)

Chaining requires a memory allocation and list insertion on collisions - is it fair to call that absolute constant time? Probability of this happening depends on the number of elements in the container.

As silentbycicle said, list insertion at the head is constant time.

About allocation, I agree with you that it is "slow", but all reasonable computation models count a memory allocation as a constant time operation. If we want to go down that road and measure also memory operations, even random memory access would not be worst-case constant time: the MMU has to map the page to the physical location, and this is usually a logarithmic or amortized constant time operation.

Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]

#26

Post by brg »

Mitzenmacher, the author of Probability and Computing, has an interesting survey on cookoo hashing. In it there are a number of open research problems that, for those of you with interest, a worth looking over. The 7th is very interesting to me, regarding optimal ways to maintain a hash table in a parallel computing environment.

http://www.eecs.harvard.edu/~michaelm/postscripts/esa2009.pd...

Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]

#28

Post by jchonphoenix »

I coded a cuckoo hashed hashtable for a class once, and recently had a lecture on cuckoo hashing given to my class by Rasmus Pagh himself (inventor of cuckoo hashing). Its really surprising actually how complex the probability behind cuckoo hashing really is (and how tied to graph theory/bipartite matchings it is).

The amazing part is, not only is access O(1), the expected insertion time whenever there is no rehashing is also O(1) and rehashing occurs infrequently.

Re: Hash tables with O(1) worst-case lookup and space efficiency [pdf]

#30

Post by ComputerGuru »

I'd just like to point out that the worse your hash algorithm is, the better Cuckoo Hashing compares to traditional hashing...... therefore, study your hash functions!

The ones that come with most languages or libraries by default quite simply aren't optimized for use on anything. There's hash functions that work better on strings and hash functions that work better on numbers (length bias). In the perfect world, this wouldn't be true, but in the real world, yes it is.

That said, may I recommend MurmurHash3: code.google.com/p/smhasher/wiki/MurmurHash3

Switch your hash tables to this. The performance difference is incredible.

Post reply on HN