4 ms·

> 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 logicall

by 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 ago
  It'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 ago
      Um, 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 ago
  But 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..
  - koolba 10y ago
    > But 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.. It's definitely possible. Here's a simplistic example. Say I have two strings: A really long string that goes on for [truncated] ... and Some other really long string goes on for [truncated] ... I can create a hash function that looks at the first character at gives either a 0 or 1 depending on whether it's an "A". For that known data set it'll perfectly hash the two strings into two buckets. It's a very simplistic example but the same concept can be used to identify the minimum components of the inputs that would need to be looked at to create a unique hash function. It won't be a general hash function though; it's specific to that data set. Note that this isn't useless either. It's common to have a fixed/known lists of strings that you want to do lookups upon.

by curun1r 10y ago

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 ago
It'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 ago
    Um, 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 ago
But 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..
- koolba 10y ago
  > But 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.. It's definitely possible. Here's a simplistic example. Say I have two strings: A really long string that goes on for [truncated] ... and Some other really long string goes on for [truncated] ... I can create a hash function that looks at the first character at gives either a 0 or 1 depending on whether it's an "A". For that known data set it'll perfectly hash the two strings into two buckets. It's a very simplistic example but the same concept can be used to identify the minimum components of the inputs that would need to be looked at to create a unique hash function. It won't be a general hash function though; it's specific to that data set. Note that this isn't useless either. It's common to have a fixed/known lists of strings that you want to do lookups upon.