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?

Improve this question
$\endgroup$
2
  • 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$ Commented Mar 16, 2013 at 20:04
  • $\begingroup$ Sorry, I did not make a quick test for existence explicit. It is indeed a requirement. $\endgroup$ Commented Mar 16, 2013 at 22:59

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.