3 ms·
The first section is wrong (emphasis mine): > A hash function is simply an algorithm that takes a string of any length and reduces it to a unique fixed length
by koolba 10y ago
The first section is wrong (emphasis mine):
> A hash function is simply an algorithm that takes a string of any length and reduces it to a unique fixed length string.
Hash functions strive for uniqueness but unless it's precalculated to ensure that it's true (by hashing every combination or deriving the parameters of the hash function accordingly), it's not guaranteed. A cryptographic hash function gives a high probability of uniqueness but again it's not guaranteed.
> The word 'cat' will hash to something that no other word hashes too, but it will always hash to the same thing.
Say I have a (terrible) hash function H(X) => 1. Now "cat" will hash to the same value as the string "I don't understand hash functions".
- Berobero 10y agoSurely no guide to hash algorithms is complete without mentioning the pigeonhole principle at least once.
- ReverseCold 10y agoJust learned about this => simply states that if you have x objects and y containers, where x>y, one container must have more than one object.
- curun1r 10y ago> Hash functions strive for uniqueness No hash function strives for uniqueness. As long as the digest length is shorter than the input length, you can logically guarantee that there will be collisions. And since all general purpose hash functions allow arbitrary length input data, this is always the case. But what cryptographic hash functions strive for is the difficulty in finding a collision. It's mathematically guaranteed to be there, but finding it should cost a prohibitively large amount of time and computing resources. There are also non-cryptographic hashes that only strive for the unlikelihood of accidentally getting a collision and don't protect against heavily contrived input data.
- koolba 10y ago> No hash function strives for uniqueness. As long as the digest length is shorter than the input length, you can logically guarantee that there will be collisions. Nope! For a known set of N inputs of length K, I can devise a hash function that maps then to a log2(N) bit result with zero collisions regardless of K. > And since all general purpose hash functions allow arbitrary length input data, this is always the case. It's not the arbitrary length data that breaks the uniqueness guarantee. It's that you can have 2^X + 1 entries where you only have X bits of hash result: https://en.wikipedia.org/wiki/Pigeonhole_principle https://en.wikipedia.org/wiki/Pigeonhole_principle
- smallnamespace 10y agoIt's the arbitrary length that causes you to have more pigeons than pigeonholes.
- koolba 10y ago> It's the arbitrary length that causes you to have more pigeons than pigeonholes. No you can have a fixed length and arbitrary text. Say the input could be 32 hex characters representing a UUID. The key distinction is whether there is a finite / known list of the possible inputs. If so, then it's possible to create a hash function the perfectly hashes them.
- smallnamespace 10y agoUm, a fixed set of inputs cannot be of arbitrary length, since you by definition know the size of the longest possible input string. The point is that a function cannot bijectively compress arbitrary input into fixed output. Of course if you make the function itself depend on the input itself, then you can pull all sorts of tricks, but normally we do not call a simple lookup table a 'hash function', because they are very different things.
- posterboy 10y agoBut then you have to cache the input strings, I don't see how the hash could work any other way independently of the input lengths. And thats rather called an index list compared to the common use of the word, which the GPs might have thought of differently, too..
- bquinlan 10y agoWhen I read that sentence, I assumed that the author meant that the computed hash for an input must be deterministic. But she doubles-down on the uniqueness claim later: Each hash is unique but always repeatable The word 'cat' will hash to something that no other word hashes too, but it will always hash to the same thing. This is such a large misunderstanding of hashing (as well as being obviously impossible) that it is hard to trust the rest of the article.
- analognoise 10y agoThis is why I love HN; I either discover a great resource, or know what to avoid and why, and I almost always learn something in the process.