Email list hosting service & mailing list manager

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 12:57 UTC

Alex Shinn scripsit:

>     The implementation may substitute a more efficient hash function for
>     any user-specified hash function, if it can prove that the substitute
>     is valid for the equality predicate as described above.  Specifically,
>     this allows the use of addresses as hashes, in which case the keys
>     must be rehashed if they are moved by the garbage collector.

That seems to give up too much control to the implementation.  Suppose the
default hash for strings is high-quality, as I would expect it to be.
A particular application, however, may want to trade off quality for
hashing speed by substituting its own hash function.  You are licensing
the implementation to just discard that and use its own superior hash
function in all cases.

> Hash functions need not be idempotent - in fact, they can't
> be if the keys are not integers.

Can you explain that?

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

> I'm not fond of the name hash-table-extend! as the common
> case seems to be not to extend, but I realize this has precedence
> in Racket and don't have great alternative suggestions.  Maybe
> hash-table-ensure! or hash-table-cache!.

The whole function is somewhat problematic: see my previous posting.

> It doesn't seem to be useful to omit failure in hash-table-extend!.

Or success in hash-table-replace!.

> Either way, the description is hard to read.

I'll work on that.

> If we're going to have -push! and -pop! conveniences, I think
> -inc! and -dec! should be there too.  I use them much more
> often.

Reasonable.

> Bimaps are useful but perhaps an order of magnitude less
> so than hash tables - I'd rather these be in a separate library.

As a matter of personal policy, I'm not trying to make packaging decisions
at this point.  I think when we decide what goes into R7RS-large and what
doesn't, we'll need to have a conspectus of all SRFIs and packaging for
them, as we did for R7RS-small.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
Linguistics is arguably the most hotly contested property in the academic
realm. It is soaked with the blood of poets, theologians, philosophers,
philologists, psychologists, biologists and neurologists, along with
whatever blood can be got out of grammarians. - Russ Rymer