2

I need a algorithim to generates a unique hash, not necessirily fixed length, for a integer such that it is independent of permutations of digits.

Like, the hash of 123, 321, 312, 213... should be the same. (Ignore the leading zeroes)

What I tried was to raise every digit to itself and sum up. Like,

Hash(321) = 3**3 + 2**2 + 1**1

Now, I am not sure whether it will generate collissions or not and there is, certainly, a performance issue for large numbers. Any alternatives?

6
  • 3
    A hash is not safe against collisions in any way, at all. What are you trying to do? Apr 28, 2012 at 20:31
  • Generate a unique ID for a number such that it is independent of permutations of digits of the number.
    – Shubham
    Apr 28, 2012 at 20:35
  • 2
    @Shubham: Why not just sort the digits, and use the result as the hash? Apr 28, 2012 at 20:40
  • @OliCharlesworth: Can that be fast enough? Also in languages like C++, sorting digits, wont it require many more steps?
    – Shubham
    Apr 28, 2012 at 20:48
  • When you say "many more", it sounds like you're comparing "it" to something (more is a relative term), what in particular are you comparing to? Apr 28, 2012 at 20:57

3 Answers 3

5

One option: Sort the digits. 123, 321, 312, and 213 all go to 123.

Another option: Use a vector of the counts of each digit as the hash. 123, 321, 312, and 213 all go to [0,1,1,1,0,0,0,0,0,0].

3
  • The second one looks pretty good. Are you sure that there wont be any collisions in it?
    – Shubham
    Apr 28, 2012 at 21:01
  • No, there are none. It's functionally identical to sorting the digits in fact.
    – user149341
    Apr 28, 2012 at 21:05
  • Thats fine. Thanks for the help!
    – Shubham
    Apr 28, 2012 at 21:10
1

You just need any hash function (let's take md5) and a way to commutatively join things. Take the hash of each digit and then join them with the commutative method. For example if I choose md5 and addition then I could md5 each digit and add the resulting hashes. If I choose to instead use sha1 and multiplication that would give me a different result but it would still have the properties you want. The questions of collisions is harder...

4
  • Well a MD5 hash is 16 byte long. Certainly If I add up the hashes (assuming you mean join from end to end), that would become really long even for small integers.
    – Shubham
    Apr 28, 2012 at 20:40
  • If you want any chance of "uniqueness", it's going to have to be large. Apr 28, 2012 at 20:46
  • That would become monstrous not only large.
    – Shubham
    Apr 28, 2012 at 20:51
  • I think he means adding the hashes arithmetically. That would work, it's just a pretty silly way of using MD5. (You might as well just choose ten random bit strings instead of MD5(0), MD5(1)...)
    – user149341
    Apr 28, 2012 at 21:12
0

Just use a cross sum as algorithm

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.