Simplest Hash Functions
purplesyringa.moe
Simplest Hash Functions
1–10 of 62 posts
Re: Simplest Hash Functions
#2a 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.
Re: Simplest Hash Functions
#3a 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 dataRe: Simplest Hash Functions
#4a 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.
A perfect hash function
https://en.wikipedia.org/wiki/Perfect_hash_function has to be specially constructed for each desired set of inputs. Generic hash functions cannot be 'perfect'.
Re: Simplest Hash Functions
#5a 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
Well it no longer constrains the data in a fixed output length.
Re: Simplest Hash Functions
#6> Like addition
I'm perplexed to the claim that addition is cheaper than XOR, especially since addition is built upon XOR, am I missing anything? Is it javascript specific?
Re: Simplest Hash Functions
#7a 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.
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
Re: Simplest Hash Functions
#8This is a excellent article for anyone looking for some more in-depth analysis of tabulation based hashing methods:
https://arxiv.org/abs/1505.01523
Re: Simplest Hash Functions
#9Earlier quoted context omitted.
Here is a hash function that does not have hash collisions: fn hash(data): return data
Well it no longer constrains the data in a fixed output length.
Sure, but if you constrain to fixed output length, you will definitely have collisions (Pigeon Hole Principle). There's no way around that.
Re: Simplest Hash Functions
#10A “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 hash functions are commonly used for requires at least four algorithms if you care about performance and optimality. It is disconcertingly common to see developers using hash algorithms in contexts where they are not fit for purpose. Gotta pick the right tool for the job.