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

21–30 of 62 posts

Re: Simplest Hash Functions

#21

Post by kro »

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.

It's very very unlikely to get collisions there, but still not impossible. Whenever you map data of arbitrary length (infinite possibilities) to a limited length collisions are possible.

Re: Simplest Hash Functions

#22

Post by SkiFire13 »

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 older processors used to have a slower implementation for shifts, which made this slower.

Nowadays swisstable and other similar hashtables use the top bits and simd/swar techniques to quickly filter out collisions after determining the starting bucket.

Re: Simplest Hash Functions

#23

Post by teo_zero »

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?

Re: Simplest Hash Functions

#24

Post by zimpenfish »

Sharlin wrote: post #20

def hash(str): len(str) O(1), baby!

O(1) only if you're working in a language with length-stored strings (like Pascal[0]), right?

In something like C with its generic strings[1], it would surely have to be O(n) since you have to scan the entire string to calculate its length?

(I have always been terrible at big-O, mind.)

[0] There's probably more of them by now.

[1] ie. not a specific length-stored string type.

Re: Simplest Hash Functions

#25

Post by eru »

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 bad example. For a good example: consider rmlint and other file system deduplicators.

These deduplicators scan your filesystem for duplicates (amongst other things). You don't want to compare every file against every other file. So as a first optimisation, you compare files only by some hash. But conventional hashes like sha256 or crc take O(n) to compute. So you compute cheaper hashes first, even if they are weaker. Truncation, ie only looking at the first few bytes is very cheap. Determining the length of a file is even cheaper.

Re: Simplest Hash Functions

#26

Post by eru »

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

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.

Re: Simplest Hash Functions

#27

Post by eru »

Sharlin wrote: post #20

def hash(str): len(str) O(1), baby!

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: Simplest Hash Functions

#28

Post by eru »

kro wrote: post #21
bryanrasmussen wrote: post #14

Earlier quoted context omitted.

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.

It's very very unlikely to get collisions there, but still not impossible. Whenever you map data of arbitrary length (infinite possibilities) to a limited length collisions are possible.

Doesn't even have to be arbitrary length.

Whenever you map into a smaller space, you get collisions. The bigger space doesn't have to be infinite.

Re: Simplest Hash Functions

#29

Post by tux3 »

phinnaeus wrote: post #3
bryanrasmussen wrote: post #2

a hash function that produce hashes that are already in the hash table should, IMO, not be called a hash function. I get why technically it is a hash function, but still, no.

Here is a hash function that does not have hash collisions: fn hash(data): return data

That is a function, but not a hash function!

Re: Simplest Hash Functions

#30

Post by [deleted] »

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.

[deleted]
Post reply on HN