Re: [tlug] Are ordered hashes useful?

[Raymond Wan <rwan.kyoto@example.com>]

On Sat, Feb 12, 2011 at 1:47 AM, Stephen J. Turnbull <stephen@example.com> wrote:
> Raymond Wan writes:
>
>  > 2)  The other reason is to give a unique key through hashing.  For
>  > security reasons, you probably want the result of hashing to be
>  > different between program runs or between systems or something.
>
> But a hash can't do that, it's a deterministic algorithm and therefore
> always gives the same answer from the same inputs.  The unifying
> concept is "uniform chaotic distribution of values".  "Uniform" means
> that no value is more probable than any other, so risk of collision is
> minimized.  "Chaotic" means that inputs that are "close" to each other
> do not give close outputs more frequently than they give widely
> separated outputs.


Yes, you are right -- a hash cannot do that.  But I think the blurring
of the terminology has allows this definition to seep in (somehow).  I
guess some people consider any type of mapping (deterministic or not)
to be a hash.  For me, it would have to be deterministic; if it isn't,
I wouldn't call it a hash.  Maybe just "mapping" or something...

For what it's worth, I just encountered an area where a one-to-one
mapping with 0 chance of collisions to be called "hashing".  IMHO,
it's more an array lookup...  I also don't consider this as hashing,
but it's been in use for a while and is sort of taking on a life of
its own.

And BTW, I guess this post of mine is a bit unrelated to your original
question -- sorry!  Even if hashing is deterministic, we still cannot
(without more work) recover the order in which the objects/items were
hashed.  And that was the question you posed, I think.  I guess this
would require an additional data structure on top of the hash table?

Ray