title: What is the best way to cut down a hash to a desired size while retaining the quality of the original hash as much as possible?
body: <p>I have a hash function that takes 64-bit input and outputs 64-bit integer. The hash table's size is <code>2 ^ 16 = 0x10000</code>, so I can't use the whole 64-bit hash. I have to cut down to 16-bits, but I want to keep the quality of the original hash as much as possible, so that it's randomly and equally distributed.</p>
  <p>With a hash function,</p>
  <pre><code>uint64_t hash64(uint64_t);
  </code></pre>
  <p>I can use the lower bits,</p>
  <pre><code>uint16_t hash16_low(uint64_t a) {
      return hash64(a) &amp; 0xffff;
  }
  </code></pre>
  <p>or maybe using higher bits is better,</p>
  <pre><code>uint16_t hash16_high(uint64_t a) {
      return hash64(a) &gt;&gt; 0x30;
  }
  </code></pre>
  <p>or I can split the hash and merge with xor. At least no information is lost completely this way,</p>
  <pre><code>uint16_t hash16_splitXor(uint64_t a) {
      uint16_t b[4];
      memcpy(b, &amp;a, sizeof(uint64_t));
      return *b ^ b[1] ^ b[2] ^ b[3];
  }
  </code></pre>
  <p>or there is a better way. What is the best way to achieve this?</p>
  <hr />
  <p>As a reply to a comment by @dratenik, this is the hash function I'm using, which is a specialization of <a href="https://github.com/ztanml/fast-hash/blob/master/fasthash.c" rel="nofollow noreferrer">fast-hash</a> for 64-bit input with a seed of <code>0x5555555555555555</code>. I'm not sure about its cryptographic qualities, and it's not meant for such use, but at least it's statistically well-tested. Will it be enough to take either higher or lower bits?</p>
  <pre><code>static inline uint64_t xorShift64_(uint64_t a, int sh) {
      return a ^ a &gt;&gt; sh;
  }
  
  static inline uint64_t hash64_mix_(uint64_t a) {
      return xorShift64_(xorShift64_(a, 23) * 0x2127599bf4325c37u, 47);
  }
  
  static inline uint64_t hash64_(uint64_t a) {
      const uint64_t m = 0x880355f21e6d1965u;
      return hash64_mix_((hash64_mix_(a) ^ m * 8 ^ 0x5555555555555555u) * m);
  }
  </code></pre>