title: fast, large-width, non-cryptographic string hashing in python
body: <p>I have a need for a high-performance string hashing function in python that produces integers with at least <strong>34</strong> bits of output (64 bits would make sense, but 32 is too few). There are several other questions like this one on Stack Overflow, but of those every accepted/upvoted answer I could find fell in to one of a few categories, which don't apply (for the given reason.)</p>
  
  <ul>
  <li><strong>Use the built-in <code>hash()</code> function.</strong> This function, at least on the machine I'm developing for (with python 2.7, and a 64-bit cpu) produces an integer that fits within 32 bits - not large enough for my purposes.</li>
  <li><strong>Use hashlib.</strong> hashlib provides cryptographic hash routines, which are <em>far</em> slower than they need to be for non-cryptographic purposes. I find this self-evident, but if you require benchmarks and citations to convince you of this fact then I can provide that.</li>
  <li><strong>Use the <code>string.__hash__()</code> function as a prototype to write your own function.</strong> I suspect this will be the correct way to go, except that this particular function's efficiency lies in its use of the c_mul function, which wraps around 32 bits - again, too small for my use! Very frustrating, it's so close to perfect!</li>
  </ul>
  
  <p>An ideal solution would have the following properties, in a relative, loose order of importance.</p>
  
  <ol>
  <li>Have an output range extending at least 34 bits long, likely 64 bits, while preserving <em>consistent</em> avalanche properties over <em>all</em> bits. (Concatenating 32-bit hashes tends to violate the avalanche properties, at least with my dumb examples.)</li>
  <li>Portable. Given the same input string on two different machines, I should get the same result both times. These values will be stored in a file for later re-use.</li>
  <li>High-performance. The faster the better as this function will get called roughly  20 billion times during the execution of the program I'm running (it is the performance-critical code at the moment.) It doesn't need to be written in C, it really just needs to outperform md5 (somewhere in the realm of the built-in hash() for strings).</li>
  <li>Accept a 'perturbation' (what's the better word to use here?) integer as input to modify the output. I put an example below (the list formatting rules wouldn't let me place it nearer.) I suppose this isn't 100% necessary since it can be simulated by perturbing the output of the function manually, but having it as input gives me a nice warm feeling.</li>
  <li>Written entirely in Python. If it absolutely, positively <em>needs</em> to be written in C then I guess that can be done, but I'd take a 20% slower function written in python over the faster one in C, just due to project coordination headache of using two different languages. Yes, this is a cop-out, but this is a wish list here.</li>
  </ol>
  
  <p>'Perturbed' hash example, where the hash value is changed drastically by a small integer value n</p>
  
  <pre><code>def perturb_hash(key,n):
      return hash((key,n))
  </code></pre>
  
  <p>Finally, if you're curious as to what the heck I'm doing that I need such a specific hash function, I'm doing a complete re-write of the pybloom module to enhance its performance considerably. I succeeded at that (it now runs about 4x faster and uses about 50% of the space) but I noticed that sometimes if the filter got large enough it was suddenly spiking in false-positive rates. I realized it was because the hash function wasn't addressing enough bits. 32 bits can only address 4 billion bits (mind you, the filter addresses bits and not bytes) and some of the filters I'm using for genomic data double that or more (hence 34 bit minimum.)</p>
  
  <p>Thanks!</p>