1

I have list of unique variable length strings composed of letters, numbers and special characters(email addresses). Each email address in the list is unique.

I need a one way hash function(I do not need to be able to retrieve the original value from the generated number) that will hash the string with a salt and generate a 12 digit number.

I want to ensure uniqueness so I will check the list of previously generated values to detect collisions and then generate a new number if there is a collision. Predictability is not an issue.

Ideally I would like this function to be written in Groovy, but Java would also be fine.

5
  • You are looking for a perfect hash, which always exists so long as there are fewer input strings than possible output strings (10^12 in your case). However, the resulting hash function is specific to that particular data-set; you can't use it on a different data-set and still guarantee uniqueness. May 16, 2012 at 17:23
  • I have changed the requirement that generated values do not have to be guaranteed to be unique. I will check for collisions in generated values by checking the list of already created values. Is there anything else I need to correct in my request?
    – anataliocs
    May 16, 2012 at 17:40
  • Or can I just append a portion of the original input(the email) to the generated id to make it unique?
    – anataliocs
    May 16, 2012 at 17:43
  • @anataliocs The problem with checking for collisions is that at that point it is too late to do anything without throwing out the hash and starting over, and it requires recording the original values (barring additional input restrictions). It can tell there is a problem, but likely isn't what is required.. what is the end purpose of such a mapping? Hashing is great because it is repeatable given only the input. However, if such a mapping is maintained in a database (the "output" needs not be [entirely] dependent upon the input), then that is an entirely different ballgame...
    – user166390
    May 16, 2012 at 18:02
  • Of course, 12 [hex] digits is still a "pretty darn big value" so, given a "relatively small number" of inputs, there is a very good chance that a well-distributed hash (say, the top 12 digits of a SHA1) will yield a unique mapping. The guarantee that this is so is not there, however. Increasing the target space greatly reduces the likelihood of such a [random] collision. Compare the "short node ID" (12 hex digits = 60 bits, very low chance of collision) and "node ID" (160 bits, assumed to be unique and would kill an Hg repo if not) used in Mercucial/Hg (and Git).
    – user166390
    May 16, 2012 at 18:13

1 Answer 1

6

I need to guarantee that each generated number will be unique.

Well that's clearly going to be a problem. There are more possible input strings than possible output values. In particular, every possible output value (a 12-digit string) is a possible input value. Therefore if all of those get unique output values, there can't possibly be any output values left for any other input values.

Of course you could always record each email address you encounter (so the first one ends up with 000000000000, the second gets 000000000001 etc) but that's a storage matter rather than hashing as such. You can't get to the output from just the input, without the backing store.

3
  • There would be conflict problem for the outputs. May 16, 2012 at 17:24
  • @BhavikAmbani: Exactly - you can't generate unique numbers when there are more possible inputs than outputs.
    – Jon Skeet
    May 16, 2012 at 17:25
  • @OliCharlesworth: If you know the list beforehand, yes. If the function has to just accept a string, with no other reference data or storage, you're in trouble...
    – Jon Skeet
    May 18, 2012 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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