4
$\begingroup$

The goal is to distribute approximately 100 million variable length strings, average length 100 characters, uniformly among 100 million buckets. Perfection not required, just no egregious clumping. The strings are URLs. They tend to begin much the same way and end much the same way (e.g. h t t p:// or w w w. and ".c o m", ".e d u", "a s p x" and so forth) and show their greatest variation in the latter half of the string, except for the final few characters.

What's a good algorithm that would accept the string and the number of slots as inputs, and return a number between 0 and SlotCount-1, and satisfy the uniform-distribution requirement?

$\endgroup$
  • 1
    $\begingroup$ Since you mention no other requirement (such as quick checks for existence etc.), why not just go in a cyclic fashion, putting the incoming string in the next slot and so on? $\endgroup$ – Paresh Mar 16 '13 at 20:04
  • $\begingroup$ Sorry, I did not make a quick test for existence explicit. It is indeed a requirement. $\endgroup$ – mrblint Mar 16 '13 at 22:59
2
$\begingroup$

Any string hashing algorithm designed for ASCII text should work fine. Take a look at the Wikipedia article, consider if the set could be manipulated by an adversary to create pile-ups (algoritmic vulnerabilities). If that isn't an issue, at strchr and partow several "classical" hash algorithms are given and compared. Get a subset of your data and use the parameters suggested there for your own comparison. And please tell us the results.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.