On 09/26/2013 05:50 PM, Wolfgang Eder wrote: > hi, > in recent discussions on this list, the idea of using hashes to > identify or even name things is often mentioned. > in this context, hashes are treated as being unique; > > albeit unlikely, it *is* possible that hashes are equal > for two distinct things. are there ideas about > how to handle such a situation? >
If what you want is unique identifiers, you basically have two choices: 1) Have a single central authority that hands out identifiers. 2) Settle for a very small probability that identifiers will not be unique. The central authority model works in some scenarios, but for widely distributed systems the reliability problems (the central authority may be down or unreachable) or scalability problems make it unworkable. Whenever you generate identifiers concurrently in multiple places there is some chance that you will generate duplicates. There have been schemes to generate globally unique identifiers. These all turned out to be flawed, so that just using a good random number generator and generating enough bits is more reliable. So a random number generator is a pretty good solution if all you want is unique identifiers. Where a hash comes in is if you want the identifiers generated in different places to be the *same* if the content being identified is the same -- you hash the content, and the resulting hash is the identifier. If the identifiers must also be unique, it's important to use a strong cryptographic hash. These are designed so that you can't get collisions even if you know how they work and try really hard, so they have good uniqueness properties. The probability of duplicate hashes is still non-zero, but it's pretty tiny. This is why, for instance, git uses the SHA-1 hash as a unique identifier. You *could* get two non-equal objects with the same hash, but it's so unlikely that this case is not handled, AFAIK. To even detect the case you'd probably have to introduce a central authority, and re-introduce all those much worse problems. Regards, -Martin _______________________________________________ fonc mailing list [email protected] http://vpri.org/mailman/listinfo/fonc
