News for hackers. Stuff that matters.
Re:How Hash Algorithms Work (2007) by koolba on Friday January 13, 2017 @10:17AM (#13391396)
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".

Re:How Hash Algorithms Work (2007) by bquinlan on Friday January 13, 2017 @01:06PM (#13392963)
When 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.

Re:How Hash Algorithms Work (2007) by analognoise on Friday January 13, 2017 @03:21PM (#13394362)
This 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.
Re:How Hash Algorithms Work (2007) by curun1r on Friday January 13, 2017 @01:01PM (#13392915)
> 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.

Re:How Hash Algorithms Work (2007) by koolba on Friday January 13, 2017 @01:13PM (#13393043)
> 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

Re:How Hash Algorithms Work (2007) by posterboy on Friday January 13, 2017 @03:43PM (#13394518)
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..
Re:How Hash Algorithms Work (2007) by koolba on Friday January 13, 2017 @04:28PM (#13394842)
> 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.

Re:How Hash Algorithms Work (2007) by smallnamespace on Friday January 13, 2017 @02:37PM (#13394000)
It's the arbitrary length that causes you to have more pigeons than pigeonholes.
Re:How Hash Algorithms Work (2007) by koolba on Friday January 13, 2017 @04:31PM (#13394867)
> 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.

Re:How Hash Algorithms Work (2007) by smallnamespace on Friday January 13, 2017 @06:18PM (#13395656)
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.

Re:How Hash Algorithms Work (2007) by Berobero on Friday January 13, 2017 @10:49AM (#13391670)
Surely no guide to hash algorithms is complete without mentioning the pigeonhole principle at least once.
Re:How Hash Algorithms Work (2007) by ReverseCold on Friday January 13, 2017 @08:40PM (#13396321)
Just 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.