title: A good hashing function for a non-uniform sequence of uniformly distributed 4 bits values?
body: <p>I have a very specific problem:</p>
  
  <p>I have uniformly random values spread on a 15x50 grid and the sample I want to hash corresponds to a square of 5x5 cells centered around any possible grid position. </p>
  
  <p>The number of samples can thus vary from 25 (away from borders, most cases) to 20, 15 (near a border) down to a minimum of 9 (in a corner).</p>
  
  <p>So even though the cell values are random, the location introduces a deterministic variation in the sequence length.</p>
  
  <p>The hash table size is a small number, typically between 50 and 20.</p>
  
  <p>The function will operate on a large set of randomly generated grids (a few hundreds/thousands), and might be called a few thousands times per grid. The positions on the grid can be considered random.</p>
  
  <p>I would like a function that could spread the 15x50 possible samples as evenly as possible.</p>
  
  <p>I have tried the following pseudo-code:</p>
  
  <pre><code>int32 hash = 0;
  int i = 0; // I guess i could take any initial value and even be left uninitialized, but fixing one makes the function deterministic
  foreach (value in block)
  {
      hash ^= (value &lt;&lt; (i%28))
      i++
  }
  hash %= table_size
  </code></pre>
  
  <p>but the results, though not grossly imbalanced, do not seem very smooth to me. Maybe it's because the sample is too small, but the circumstances make it difficult to run the code on a bigger sample, and I would rather not have to write a complete test harness if some computer savvy has an answer ready for me :).</p>
  
  <p>I am not sure pairing the values two by two and using a general purpose byte hashing strategy would be the best solution, especially since the number of values might be odd.</p>
  
  <p>I have tought of using a 17th value to represent off-grid cells, but that seems to introduce a bias (the sequences from cells near a border will have a lot of "off grid" values).</p>
  
  <p>I am not sure either what would be the best way to test the efficiency of various solutions (how many grids shall I generate to have an idea of the performances, for instance).</p>