> What a good hash function should do though is ensure that small changes in the source guarantee a completely different output hash.
Not always true. For example, see locality sensitive hashing [1] which relies on similar inputs being hashed to similar outputs to quickly look up similar items.
That's where I think the really interesting aspect of hashing algorithms comes from - what the different characteristics are and what applications that has (speed for checksums, slow for passwords, similar inputs giving similar outputs for similarity searching)
[Edit]
The key characteristic of all hashing functions is it produces a fixed size output. The fact this makes a one way function is incidental; though crucial for many applications like password storage, it's not really that important for things like checksums [2] or hash tables.
About your edit: That's not actually a good key characteristic. E.g. in the context of purely functional data structure, the key property is that hash functions are fast to compute and provide keys that are easy to look up, but may have collisions.
I meant the characteristic that makes it a hash function is producing a fixed size output.
It may not be that important for some contexts, but without that characteristic it's not a hashing function.
Conversely, I can have a function that isn't one way, but produces a fixed size output. Granted, it's not going to be that useful, but it's still a hashing function. If I have a one-way function that doesn't produce a fixed size output, it's not a hashing function.
Not always true. For example, see locality sensitive hashing [1] which relies on similar inputs being hashed to similar outputs to quickly look up similar items.
That's where I think the really interesting aspect of hashing algorithms comes from - what the different characteristics are and what applications that has (speed for checksums, slow for passwords, similar inputs giving similar outputs for similarity searching)
[Edit] The key characteristic of all hashing functions is it produces a fixed size output. The fact this makes a one way function is incidental; though crucial for many applications like password storage, it's not really that important for things like checksums [2] or hash tables.
[1] http://en.wikipedia.org/wiki/Locality_sensitive_hashing
[2] Though it can be useful if using checksums for security.