hash functions and other comments Alex Shinn (08 Sep 2015 06:19 UTC)
Re: hash functions and other comments John Cowan (08 Sep 2015 12:57 UTC)
Re: hash functions and other comments Alex Shinn (08 Sep 2015 13:32 UTC)
Re: hash functions and other comments John Cowan (08 Sep 2015 14:59 UTC)
Re: hash functions and other comments Alex Shinn (09 Sep 2015 04:29 UTC)
Re: hash functions and other comments John Cowan (09 Sep 2015 13:18 UTC)
Re: hash functions and other comments Alex Shinn (10 Sep 2015 02:09 UTC)
Re: hash functions and other comments John Cowan (10 Sep 2015 03:46 UTC)
Re: hash functions and other comments Arthur A. Gleckler (10 Sep 2015 03:56 UTC)
Re: hash functions and other comments Alex Shinn (10 Sep 2015 10:05 UTC)
Re: hash functions and other comments Kevin Wortman (11 Sep 2015 19:01 UTC)
Re: hash functions and other comments John Cowan (11 Sep 2015 19:51 UTC)
Re: hash functions and other comments Alex Shinn (12 Sep 2015 06:29 UTC)
Re: hash functions and other comments John Cowan (12 Sep 2015 22:16 UTC)
Re: hash functions and other comments Alex Shinn (15 Sep 2015 03:23 UTC)
Re: hash functions and other comments John Cowan (15 Sep 2015 11:31 UTC)
Re: hash functions and other comments Alex Shinn (15 Sep 2015 12:57 UTC)
Re: hash functions and other comments Alex Shinn (16 Sep 2015 03:01 UTC)

Re: hash functions and other comments John Cowan 08 Sep 2015 14:59 UTC

Alex Shinn scripsit:

> Idempotence means applying the same operation multiple
> times without changing the result, i.e. f(f(x)) = f(x).  This is
> basically never the case for hash functions.

Yes, of course.  I meant to say "pure" instead of "idempotent".
I'll reword this.

> > There's no discussion of the trade-offs involved in perfect
> > > hashes.  The requirements seem to forbid them by requiring
> > > amortized O(1) on mutation, but if that were relaxed we could
> > > have guaranteed (non-amortized) O(1) on access.  It's probably
> > > better to leave this to a separate data-structure to support the
> > > frequent update case, but I thought I'd mention this.
> >
> > Unpack this, please.
> >
>
> ?

Ah, you're not a Miles Vorkosigan fan.  I meant that the explanation is
too condensed for me to follow: please elaborate on it.

> Actually, given Taylan's proposal I think hash-table-intern! is a
> perfectly good, if Lisp-centric, name.

Sounds reasonable, but I want to rethink the whole -extend!/-replace! family.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
Half the lies they tell about me are true.
        --Tallulah Bankhead, American actress