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

Simplest Hash Functions

purplesyringa.moe

Post reply on HN
Print view View original

41–50 of 62 posts

Re: Simplest Hash Functions

#41

Post by purplesyringa »

kuzivaai wrote: post #18

The point about hash tables using top bits instead of bottom bits is the kind of thing that feels obvious once someone says it and yet here we are. Genuine question: have you seen any real-world hash table implementations that actually do this, or is it purely "this is what we should have done 40 years ago"?

I think the reason real-world implementations don't do this is to speed up access when the key is a small integer. Say, if your IDs are spread uniformly between 1 and 1000, taking the bottom 7 bits is a great hash, while the top 7 bits would just be zeros. So it's optimizing for a trivial hash rather than a general-purpose fast hash.

And since most languages require each data type to provide its own hash function, you kind of have to assume that the hash is half-assed and bottom bits are better. I think only Rust could make decisions differently here, since it's parametric over hashers, but I haven't seen that done.

Re: Simplest Hash Functions

#42

Post by adrian_b »

benob wrote: post #19

I just realized that a hash function is nothing less than the output of a deterministic random number generator xored with some data

Hash functions and PRNGs are closely related, they share many properties and they can be built from the same algorithmic components, so for many kinds of PRNGs there are corresponding kinds of hash functions and vice-versa.

Nevertheless, the purposes of hash functions and PRNGs are different and complementary.

A PRNG receives a short fixed-length value (the seed) and it expands it into a long pseudo-random sequence of arbitrary length.

A hash function receives a long input sequence of arbitrary length and it generates a short fixed-length pseudo-random value.

Good PRNGs are injective functions and good hash functions are surjective functions.

Normally the design methods for PRNGs and for hash functions should be presented together, because it is easy to interconvert algorithms for one of them with algorithms for the other. For instance, given a good hash function one could make a PRNG by computing the hashes of a sequence of numbers or the hashes of a sequence of strings of increasing length, and given a good PRNG one could make a hash function by accumulating somehow the input into a PRNG seed and taking the first generated number, or better by using input chunks as seeds and then accumulating the first generated numbers into a single value.

However for a successful conversion between PRNG and hash function algorithms, the source algorithm may have have to be overdesigned, to guarantee good enough properties even after the conversion.

When an algorithm is designed directly as a hash function or as a PRNG, with clearly specified requirements, it can be designed only as good as strictly necessary, enabling thus a better performance.

Re: Simplest Hash Functions

#43

Post by ogogmad »

bryanrasmussen wrote: post #14
baruch wrote: post #7

Earlier quoted context omitted.

It is mathematically impossible for a proper hash function (one with an output range smaller than its input range) to not have collisions. The proof uses the Pigeon Hole Principle https://en.wikipedia.org/wiki/Pigeonhole_principle

ok damn, I did not know this, obviously. Thanks. I guess I've never actually had this problem because was always hashing things that were static, or specialty cases like password hashes where the salt obviously guarantees uniqueness.

Let's consider a hash table with an allocation of 1MB, which is about 2^20 bytes. Assume also that each entry occupies a byte. Assuming that the hash function's values are distributed randomly, the probability of there being a collision with only 1000 entries is approximately 38% = 1-(2^20)!/(2^20 - 1000)!/(2^20)^1000. See the "Birthday Problem".

Re: Simplest Hash Functions

#44

Post by adrian_b »

teo_zero wrote: post #23
kuzivaai wrote: post #18

The point about hash tables using top bits instead of bottom bits is the kind of thing that feels obvious once someone says it and yet here we are. Genuine question: have you seen any real-world hash table implementations that actually do this, or is it purely "this is what we should have done 40 years ago"?

Sorry, I've read and reread TFA but the concept still evades me. Is it that, since it's easier for a hash function to have higher entropy in the higher bits than in the lower ones, it would be more logical for hash tables to discard the lower bits and keep the higher ones?

Higher entropy in the higher bits is a property of addition and multiplication when the result has the same size as the operands (i.e. the result is taken modulo 2^N, which folds back the values exceeding the size of the result).

When other operations are used, there may be other bits with higher entropy. For example, when full-length multiplication is used (i.e. where the length of the result is the sum of the lengths of the operands), the middle bits have the highest entropy, not the top bits. On CPUs like the Intel/AMD x86-64 CPUs, where fast long multiplication instructions are available, this can be exploited in more performant hash functions and PRNGs.

In hash functions, additions and multiplications are frequently used together with rotations, in order to redistribute the entropy from the top bits to the bottom bits, during the following operations.

Re: Simplest Hash Functions

#45

Post by guenthert »

eru wrote: post #25
jandrewrogers wrote: post #10

A “simplest” hash function is completely dependent on what you are using the hash function for and the guarantees you want a hash function to make. An optimal permutation of an integer is different from a small string hash is different from a block checksum. Literally, you are optimizing the algorithm for entirely different properties. No algorithm can satisfy all of them even approximately. The full scope of things…

You are right! For example, when you know that your input is uniformly randomly distributed, then truncation is a perfectly good hash function. (And a special case of truncation is the identity function.) The above condition might sound too strong to be practical, but when you are eg dealing with UUIDs it is satisfied. Another interesting hash function: length. See https://news.ycombinator.com/item?id=6919216 for a b…

Now I'm no expert in that matter, but the fs deduplicators I've seen were block, not file, based. Those can clearly not use the file length as they are blissfully unaware of files (or any structure for that matter). Those use a rather expensive hash function (you really want to avoid hash collisions), but (at least some ten years ago) memory, not processing speed, was the limiting factor.

Re: Simplest Hash Functions

#46

Post by purplesyringa »

adrian_b wrote: post #44
teo_zero wrote: post #23

Earlier quoted context omitted.

Sorry, I've read and reread TFA but the concept still evades me. Is it that, since it's easier for a hash function to have higher entropy in the higher bits than in the lower ones, it would be more logical for hash tables to discard the lower bits and keep the higher ones?

Higher entropy in the higher bits is a property of addition and multiplication when the result has the same size as the operands (i.e. the result is taken modulo 2^N, which folds back the values exceeding the size of the result). When other operations are used, there may be other bits with higher entropy. For example, when full-length multiplication is used (i.e. where the length of the result is the sum of the lengt…

Honorary mention: byte swapping instructions (originally added to CPUs for endianness conversion) can also be used to redistribute entropy, but they're slightly slower than rotations on Intel, which is why I think they aren't utilized much.

Re: Simplest Hash Functions

#47

Post by eru »

andai wrote: post #34
eru wrote: post #27

Earlier quoted context omitted.

You'd probably want 'return len(str)', if this is Python? In any case, for some applications this is indeed a great hash function. Programs like rmlint use it as part of their checks for duplicate files: if files have different lengths, they can't have the same content after all.

Re: missing return keyword Actually, in Python, None is a valid key... (I'm so sorry. JavaScript has ruined me.)

That's why I said "probably".

Re: Simplest Hash Functions

#48

Post by eru »

andai wrote: post #32
eru wrote: post #26

Earlier quoted context omitted.

Sorry, what? That might we one very particular way to write a hash function, but it's far from the only one. Believe it or not, for some purposes taking the first few bytes of a string or even just the length of the string are good hash functions.

Well, that's technically also a deterministic random number generator! (I want to say it's not a great one, but... that's apparently context-dependent!) What are those purposes?

If your input is i.i.d. random, then truncating works great. Eg if your keys are UUIDs then truncating can work well.

Another use:

Suppose you write a tool like rmlint that is looking for duplicate files. Generally, you compute some hash for each file, see if you got any duplicates, and then compare the relevant files directly.

A traditional hash like crc or sha256 takes O(n) to compute. But for files you can start with some cheaper hashes, like file length. After all, files of different length can't have the same content. Taking the first few bytes of your file is another cheap 'hash' you can compute.

Only when these cheap 'hashes' show that you have a potential duplicate, do you go and pay for a more expensive hash.

Re: Simplest Hash Functions

#49

Post by eru »

guenthert wrote: post #45
eru wrote: post #25

Earlier quoted context omitted.

You are right! For example, when you know that your input is uniformly randomly distributed, then truncation is a perfectly good hash function. (And a special case of truncation is the identity function.) The above condition might sound too strong to be practical, but when you are eg dealing with UUIDs it is satisfied. Another interesting hash function: length. See https://news.ycombinator.com/item?id=6919216 for a b…

Now I'm no expert in that matter, but the fs deduplicators I've seen were block, not file, based. Those can clearly not use the file length as they are blissfully unaware of files (or any structure for that matter). Those use a rather expensive hash function (you really want to avoid hash collisions), but (at least some ten years ago) memory, not processing speed, was the limiting factor.

https://github.com/sahib/rmlint is the one I had in mind.

> Those use a rather expensive hash function (you really want to avoid hash collisions), [...]

Then we are clearly not thinking of the same kind of software.

> but (at least some ten years ago) memory, not processing speed, was the limiting factor.

In what I described, IO is the limiting factor. You want to avoid having to read the whole file, if you can.

I think you are thinking of block level online deduplicators that are integrated into the file system?

Re: Simplest Hash Functions

#50

Post by guenthert »

eru wrote: post #49
guenthert wrote: post #45

Earlier quoted context omitted.

Now I'm no expert in that matter, but the fs deduplicators I've seen were block, not file, based. Those can clearly not use the file length as they are blissfully unaware of files (or any structure for that matter). Those use a rather expensive hash function (you really want to avoid hash collisions), but (at least some ten years ago) memory, not processing speed, was the limiting factor.

https://github.com/sahib/rmlint is the one I had in mind. > Those use a rather expensive hash function (you really want to avoid hash collisions), [...] Then we are clearly not thinking of the same kind of software. > but (at least some ten years ago) memory, not processing speed, was the limiting factor. In what I described, IO is the limiting factor. You want to avoid having to read the whole file, if you can. I th…

> https://github.com/sahib/rmlint is the one I had in mind.

Ah, right, thanks. I now dimly recall some old project realizing fs-snapshots using hard links, which one could consider some sort of deduplication as well.

> I think you are thinking of block level online deduplicators that are integrated into the file system?

Indeed, I was.

Post reply on HN