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

Fast Perfect Hashing

jandrewrogers.com

Post reply on HN
Print view View original

31–40 of 43 posts

Re: Fast Perfect Hashing

#31

Post by jnwatson »

derefr wrote: post #25
munificent wrote: post #18

This article is interesting but... weird. It seems to assume a bunch of things, and then states some conclusions based on that, but then also assumes the value of the conclusions is obvious. > A perfect hash function is one that is collision-free. By implication, the hash must be at least as many bytes as the key and the function is theoretically reversible, though not always tractably so. This is true because of the…

> The author assumes the reader knows the value of randomizing your integer keys. I'm not sure what that value is in cases where you know you don't have collisions anyway. If you're going to be doing writes of your data in order of an integer sequence number, and you're writing to a multi-node storage system that partitions/shards by primary-key range, then you're going to get worst-case performance if you use your i…

It is trivial to generate a mostly-randomized bijective mapping of small integers to small integers with an xor and a little byte swapping, which is what the author does with a built-in AES instruction.

The OP's point is that this isn't a particularly interesting problem. The interesting problem is generating efficient bijective mappings of large integers to very small integers.

Re: Fast Perfect Hashing

#32

Post by inciampati »

Coincidentally, I was just testing an actual perfect hash function generator https://github.com/rizkg/BBHash. It requires 2-3 bits per entry irrespective of key or table size. They show that they can build the table for 10^12 entries.

One problem is that identifying keys that aren't in the table can be as expensive as storing all the keys. I was thinking that it would be interesting to build two tables with different hash functions for the same set of keys and then record the mapping between them. This would double the table size and add n log n bits to record the relationship, but it would let you make probabilistic (but pretty confident) estimates of what keys weren't in the table, all with a fixed number of bits per key.

To clarify, if you map a key into the table with both functions, by construction it will map to a position in each table that are linked together. If a key maps to unlinked positions in each table then we know with probability ~(1-1/n) that the key isn't in the input to the table. When keys are big and n is big you could be very confident in this estimate and save a huge amount of space over typical structures to do this.

Re: Fast Perfect Hashing

#33

Post by gumby »

da_chicken wrote: post #24
gumby wrote: post #8

> A perfect hash function is one that is collision-free. By implication, the hash must be at least as many bytes as the key I don't understand this lemma. An indexed array is a degenerate example in which the "hash" (pointer) is presumably a lot smaller than the key (index). BTW for those not familiar with a perfect hash function they are great for things like symbol tables that are immutable at runtime. You can make…

> An indexed array is a degenerate example in which the "hash" (pointer) is presumably a lot smaller than the key (index). No, it isn't. The "0" in arr[0] is (in most cases) a 32-bit signed integer. If you're using a signed 32-bit int to index your array, you're using a hash length of 32-bits. You won't be able to index more than 2.1 billion unique items without changing your data type. Even if you're not using all t…

It's the lemma I challenge, not the common case on certain of today's architectures. The use of the word "must" implies ∀, which is plainly not the case.

Re: Fast Perfect Hashing

#34

Post by Terr_ »

gumby wrote: post #8

> A perfect hash function is one that is collision-free. By implication, the hash must be at least as many bytes as the key I don't understand this lemma. An indexed array is a degenerate example in which the "hash" (pointer) is presumably a lot smaller than the key (index). BTW for those not familiar with a perfect hash function they are great for things like symbol tables that are immutable at runtime. You can make…

OP just needs to change "key" to "key domain".

I mean, you can perfect hash the keys ["foo", "supercalifragilisticexpialidocious"] into a single bit, the string-lengths are irrelevant.

Re: Fast Perfect Hashing

#35

Post by norswap »

And to think I was excited to finally get a good explanation of what people usually mean when they say "perfect hashing" (i.e, given a set of keys, construct a hashing function that will assign each key a unique hash so as to avoid collision, with a hash-range that has typically little overhead over the number of keys).

If someone has good resources on that, I'm still interested. I found it hard to fully internalize the stuff I've found when looking a while back. In particular, I'm confused about the (complexity, time) bounds of such a hash construction process.

Re: Fast Perfect Hashing

#36

Post by norswap »

norswap wrote: post #35

And to think I was excited to finally get a good explanation of what people usually mean when they say "perfect hashing" (i.e, given a set of keys, construct a hashing function that will assign each key a unique hash so as to avoid collision, with a hash-range that has typically little overhead over the number of keys). If someone has good resources on that, I'm still interested. I found it hard to fully internalize…

Well, it looks like I found something that could qualify: https://www.cs.cmu.edu/~avrim/451f11/lectures/lect1004.pdf

Re: Fast Perfect Hashing

#37

Post by derefr »

jnwatson wrote: post #31
derefr wrote: post #25

Earlier quoted context omitted.

> The author assumes the reader knows the value of randomizing your integer keys. I'm not sure what that value is in cases where you know you don't have collisions anyway. If you're going to be doing writes of your data in order of an integer sequence number, and you're writing to a multi-node storage system that partitions/shards by primary-key range, then you're going to get worst-case performance if you use your i…

It is trivial to generate a mostly-randomized bijective mapping of small integers to small integers with an xor and a little byte swapping, which is what the author does with a built-in AES instruction. The OP's point is that this isn't a particularly interesting problem. The interesting problem is generating efficient bijective mappings of large integers to very small integers.

I wasn't attempting to argue the OP's point, merely answering the question posed: "what [is the] value [of randomizing your integer keys] in cases where you know you don't have collisions."

Re: Fast Perfect Hashing

#38

Post by bialpio »

gumby wrote: post #20
bialpio wrote: post #13

Earlier quoted context omitted.

Actually, I might have misunderstood you. In your example, the index in the array is treated like the hash of the item you've put in there, why are we suddenly considering pointers?

In this degenerate case the "hash function" is base_address+(index*sizeof(memory_address))

Not really, the function is still f(key) = , the rest is just taking the number and mapping it to the hardware that you're on.

Re: Fast Perfect Hashing

#39

Post by da_chicken »

gumby wrote: post #33
da_chicken wrote: post #24

Earlier quoted context omitted.

> An indexed array is a degenerate example in which the "hash" (pointer) is presumably a lot smaller than the key (index). No, it isn't. The "0" in arr[0] is (in most cases) a 32-bit signed integer. If you're using a signed 32-bit int to index your array, you're using a hash length of 32-bits. You won't be able to index more than 2.1 billion unique items without changing your data type. Even if you're not using all t…

It's the lemma I challenge, not the common case on certain of today's architectures. The use of the word "must" implies ∀, which is plainly not the case.

You're not explaining yourself at all. How do you propose to put 10 pounds of shit in a 5 pound bag?

Re: Fast Perfect Hashing

#40

Post by munificent »

derefr wrote: post #25
munificent wrote: post #18

This article is interesting but... weird. It seems to assume a bunch of things, and then states some conclusions based on that, but then also assumes the value of the conclusions is obvious. > A perfect hash function is one that is collision-free. By implication, the hash must be at least as many bytes as the key and the function is theoretically reversible, though not always tractably so. This is true because of the…

> The author assumes the reader knows the value of randomizing your integer keys. I'm not sure what that value is in cases where you know you don't have collisions anyway. If you're going to be doing writes of your data in order of an integer sequence number, and you're writing to a multi-node storage system that partitions/shards by primary-key range, then you're going to get worst-case performance if you use your i…

Thanks, that's an interesting one I'm not familiar with.
Post reply on HN