4 ms·
Honest question: why not use 2-3 different hash algorithms to minimize collisions if you are simply after uniqueness (e.g.: verifying that a downloaded file is
by IgorPartola 14y ago
Honest question: why not use 2-3 different hash algorithms to minimize collisions if you are simply after uniqueness (e.g.: verifying that a downloaded file is correct)?
As for hash tables, can't you guarantee uniqueness by using only reversible operations? I remember reading a lengthy post about this on HN, but can't find the link anymore.
- gizzlon 14y ago>As for hash tables, can't you guarantee uniqueness by using only reversible operations? Wouldn't that make the output almost as long as the input, defeating the purpose?
- its_so_on 14y agoactually, just as long. Any set of possible bits is a valid input, so the input has one bit of entropy per bit. If the hash were not "just as long" then one of the following must be true: - it collides (two possible inputs would have the same hash) - some inputs could not hash - the algorithm encodes more than 2 bits of entropy per bit. This is not possible by the pigeonhole principle. http://en.wikipedia.org/wiki/Pigeonhole_principle http://en.wikipedia.org/wiki/Pigeonhole_principle There's probably a more rigorous proof here but I'm lazy. I guess something like imagine the input is going to be n bits (like 16 bits)...make an array of length 2^n and initialize them all to -1, and then for each possible input (0..2^n-1) hash it and - since the hash is not longer than the input, the representation of the hash is there in the array if you simply interpret it as the index (subscript). Set that to the n that produced it, if it's not already set (otherwise abort with a collision). After you have reached 2^n-1, you have set 2^n indices (including whatever hash 0 produced). Is it possible for you not to have made a collision? (Yes, easily: for example anything hashes to the next integer, except binary all 1's which hash to all 0's). Could some of the indices to be empty? No. If you put 2^n values in 2^n holes distinctly, there is one value per hole. Conversely, if you had anything LESS than that many holes to put it into (for example, you're trying to hash 32 bits of input into just the lower half of the indices, by creating a hash that uniquely hashes to 16 bits of output) then by the pigeonhole prinicpal you have to put two n's into the same index. So, any hash that would be unique (that can hash anything) has to be at least exactly as long as what it's hashing. If there are any outputs that are never hashed to, it would have to be even longer. Note that this proof depends on iterating on every possible input. If some inputs aren't possible, the hash could be unique while being shorter than the input. This is how lossless compression works.
- mistercow 14y ago>actually, just as long Well, more accurately, at least as long, on average. It would be possible, though, to have a guaranteed unique string which is usually shorter than the input for real world data, which is called lossless compression. Obviously, it is not possible to provide a fixed digest length though, which makes it useless for many hash function applications, like bloom filters. And, of course, a hash table implementation based on DEFLATE would be hilariously inefficient.
- its_so_on 14y agoFair enough. The proof is that you can't shave even a single bit off of every output, so that given any file that's 1024 bytes, you can hash it to 1023 bytes. Not possible unless you're hiding that entropy somewhere (filename etc).
- dllthomas 14y agoThe proof is straightforward application of the pigeonhole principle. Input strings are your pigeons, hashes are your holes.
- its_so_on 14y agowhat you've just said says nothing about the length of the hashes, which was my point. You would have to say something like "all possible inputs of a certain length are your pigeons, and these same possibilities(1) are the holes" (1)this time interpreted as the hash of one and only one of the same list of possible inputs The proof is not so straightforward, because it's not always true when you expect it to be true. For example, can you hash, reversibly and uniquely, all the numbers between 0 and 10 (real) to all the numbers between 0 and 1? You would expect the answer to be "no" since there are "more real numbers from 0 to 10 than from 0 to 1". But that's actually not necessarily true the way you might expect, and the answer is actually "yes you can". Simply geometrically establish a coordinate plane like this a 0 b 1 0 10 so that point (a) has a well-defined coordinate, say (0,1) the 0 from the second line is at the origin, the 1 at the second line is at (1,0) and the bottom 0 is at (0,-1) with the bottom 10 being wherever the ray passing through a and passing through (1,0) - enough to uniquely identify the ray - has the y-value of -1. Now to get the hash simply move 'b' to wherever between 0 and 1 you're trying to hash, solve for the ray that passes through a and that point, and solve for the x-value of the ray where it has y-value of -1. Through elementary proof which should be obvious, you'll see that any b casts a distinct ray (which is easily reversible introducing a c into line 3), and you can solve for it if you like. I'm not saying that you're wrong, but I think the proof isn't as "obvious" and straightforward as you're saying. It doesn't apply to just anything, but to the specific case of the impossibility of hashing distinct length inputs uniquely into a discrete space defined by a uniformly shorter length of bits.
- mseebach 14y ago> As for hash tables, can't you guarantee uniqueness by using only reversible operations? This is called a perfect hash and its appropriateness depends on the input data. The problem is that the problem domains where hashes are practical are where a very large space of inputs needs to fit into a finite number of buckets such that lookups are fast. For that to work with a perfect hash, you need an infinite number of buckets which needs infinite space.
- andreasvc 14y agoA perfect hash is able to avoid collisions when given the set of all possible keys in advance; it is not related to reversibility. The latter contradicts the very idea of a hash function, and would conceptually be a lossless compression technique.
- mseebach 14y agoAny reversible hash would be a perfect hash - not the other way around. That's all I'm saying. That said, there's nothing in the definition of hash functions that require them to be compressing or non-reversible - although they would typically have to be to be useful.
- andreasvc 14y agoI agree with the first point, but I think compressing and non-reversible are necessary conditions for a given function to be called a hash function; if they weren't, any mathematical function would do, wouldn't it? One could see a hash function as an (extremely) lossy compression method. However, lossy compression only makes sense when you can exploit features of the domain, e.g., psychoacccoustics with sound, or characteristics of human vision with photos; perceptual hashes come to mind here.
- mseebach 14y agoIt's really quite simple. Perfect hashes exists and are hashes. Perfect hashes do not, as a matter of definition, compress. They typically aren't reversible, because it's not an useful feature for a hash, but they could be - and if nothing else, they can always be deterministically brute forced (as they have no collisions), which is a (very bad) form of reversibility. It's not meaningful to study hashes as compression, since compression is by definition reversible.
- martincmartin 14y agoComputing two 32-bit hashes is the same as computing 1 64-bit hash. In general, computing n m-bit hashes is the same as computing 1 n*m-bit hash.
- delinka 14y agoAny digest algorithm that takes variable-sized data as input and produces fixed-sized output will necessarily produce collisions for some inputs that are larger than the output.