Is this hash guaranteed to be unique?

Question

I need to uniquely identify a pair of Facebook user ids. This is how I do that:

NSString *firstId  = @"123456789";
NSString *secondId = @"987654321";

NSUInteger first_hash = [firstId hash];
NSUInteger second_hash = [secondId hash];

NSUInteger combinedHash = first_hash ^ second_hash;
NSUInteger reverseHash  = second_hash ^ first_hash;

NSLog(@"Combined hash %d\nReverse hash %d", combinedHash, reverseHash); // both are equal

Ok, now I know that regardless the order in which the hashes are combined i'm getting the same value. That's good. But is this value guaranteed to be unique? Or it is possible that a combination of ids say 322233322 and 233322233 will produce the same value as for combinedHash? If so then how do I make an unique identifier for a pair of ids?

Apply the [*pigeonhole principle*](http://en.wikipedia.org/wiki/Pigeonhole_principle) to determine the answer to your first question. — Oliver Charlesworth, Feb 08 '14 at 10:05
[sorry for possible offtop] Looking for a way to generate unique identifiers for strings? I am going to look for it as well - let me know if you find any decent solutions - please, just post abou them here as a comment. — Stanislav Pankevich, Feb 08 '14 at 10:32
[again, sorry for possible offtop] Did you see http://stackoverflow.com/questions/6714715/fastest-possible-string-key-lookup-for-known-set-of-keys? — Stanislav Pankevich, Feb 08 '14 at 10:33
@AndreyChernukha, I've already noticed that you have a different task than I have, so yours is a bit of irrelevant to me ;) — Stanislav Pankevich, Feb 08 '14 at 10:52

deviantfan · Accepted Answer · 2014-02-08T10:20:10.783

5

Without understanding much of ObjectiveC, it looks like you´re just XOR-ing the values.
This is, of course, NOT unique.
101^100 = 001
001^000 = 001
It´s that easy.

Must it be a irreversible hash or do you need just an unique id?
Latter: Just concatenate, with a unique delimiter between.
Else, depending on the maximal possible input length, a unique hash is probably impossible.
(without inventing a completely new algorithm, which may take time :))

edit, about the two possible orders of concatenation:
Just compare the two numbers before concatenating and put the smaller one first.
That way, any search by ID have not to be done twice.

edited Feb 08 '14 at 10:20

answered Feb 08 '14 at 10:07

deviantfan

11,268
3
32
49

I need just an unique id and of course i could get it by concatenation, but it doesn't suit me. – Andrey Chernukha Feb 08 '14 at 10:13
"but it doesn't suit me.". Why? – deviantfan Feb 08 '14 at 10:13
because of the order of concatenation. Which id must go first? It will require twice as much time to get a value by this id. You see? – Andrey Chernukha Feb 08 '14 at 10:15
What about comparing the two numbers and put the smaller in the front? ... No need for double DB queries or something like that... – deviantfan Feb 08 '14 at 10:16

James Snook · Answer 2 · 2014-02-08T10:19:39.390

The answer to your first question is no because 1 ^ 1 == 0 ^ 0 and 1 ^ 0 = 0 ^ 1. So if you flip a bit in your first hash, and the same bit in your second hash then your first and second hash will be different but the combined hash will remain the same.

The point of a hash is to identify something with less information than you had in the original object. As you are compacting the information to make comparisons faster it is guaranteed that a hash won't be unique.

Apending 1 ID to the end of the other.

Is this hash guaranteed to be unique?

2 Answers2