2

I have a 24 character long id which is guaranteed to be unique. I would like to shorten that to 7-10 (or even shorter) characters long. If I generate an short id randomly then I would have to check every time if that shortid is available. Is there an one-way hash algorithm that could return back 7-10 character hash from passing in the 24 character id.

Are there any other ways to guarantee that the generated short id is unique without checking?

  • 1
    "24 character long id" - what characters are in this character set? You might be able to shorten it just by re-encoding it in something that allows for a larger character set. – user40980 Jul 17 '14 at 14:39
  • 0-9,a-z no uppercases or symbols. – ed1t Jul 17 '14 at 14:41
  • Then you can cut it down to half its size by adding in symbols (shifted number) and upper case. – user40980 Jul 17 '14 at 14:59
  • 2
    I think most people would be smart enough to realize you cannot hash a big set into a small set without having collision, so can I ask that: do you have a guarantee that the cardinality of the set of 24-char ids is less than the number of possible combinations one can make from 7-10 char Id? – InformedA Jul 17 '14 at 15:29
  • 1
    TL;DR It can't be done. – Kuba Ober Jul 17 '14 at 19:19
2

You cannot guarantee that a shortened ID is unique, because there are much fewer 10-character strings than 24-character strings. Sooner or later, values will be reused.

Depending on how your IDs are generated, there are different things you could do in practice. If you get consecutive numbers, taking their last 10 characters will work for a while, but then wrap around after X^10 values. If the ID is itself totally random, you can take any 10 of its digits to get another value that is probably unique, but sooner or later will lead to collisions unpredictably. But the problem as posed is not solvable.

  • What's the shortest id I could get if not 7-10? Which hashing algorithm can I use? – ed1t Jul 17 '14 at 14:37
  • The shortest ID is 24 characters. Any shorter than that and it cannot possibly be unique per the Pigeonhole Principle. – Jörg W Mittag Jul 17 '14 at 14:45
  • 2
    Sorry I haven't made myself clear enough. Hashing can try to distribute the inevitable collisions evenly, but it cannot prevent them. If you really do need guaranteed unique IDs, you must require that restriction in the step where you generate IDs, e.g. reprogram the ID generator to use only 10 characters in the first place. – Kilian Foth Jul 17 '14 at 14:47
0

If other conditions are favorable, assign your short ids serially. First string that needs an Id gets 1, second get 2 etc. Guaranteed to be unique and no checking is needed.

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.