Simplest Hash Functions (purplesyringa.moe)

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.

> 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?

This is a excellent article for anyone looking for some more in-depth analysis of tabulation based hashing methods: https://arxiv.org/abs/1505.01523

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 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.

While I generally like to reinvent the wheel, for hash functions I strongly recommend to use a proved good one. Djb2 by the venerable Daniel Bernstein satisfies all the requirements of TFA.

  h = 5381
  while still has data:
    h = h * 33 + next_byte()
  return h

PS of course if you think the multiplication is overkill, consider that it is nothing more than a shift and an addition.

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 just realized that a hash function is nothing less than the output of a deterministic random number generator xored with some data

  def hash(str):
    len(str)

O(1), baby!