Simplest Hash Functions

3 comments

• johanvts 14 minutes ago
  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
• Charon77 46 minutes ago
  > 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?
• bryanrasmussen 1 hour ago
  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.

  [-]
  • baruch 21 minutes ago
    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
  • ahazred8ta 1 hour ago
    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'.
  • phinnaeus 1 hour ago
    Here is a hash function that does not have hash collisions:

      fn hash(data):
        return data

    [-]
    • Charon77 47 minutes ago
      Well it no longer constrains the data in a fixed output length.
      [-]
      • dbdr 12 minutes ago
        Sure, but if you constrain to fixed output length, you will definitely have collisions (Pigeon Hole Principle). There's no way around that.