On Tue, Sep 8, 2015 at 9:57 PM, John Cowan <xxxxxx@mercury.ccil.org> wrote:

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.

Yes, my intuition is that the implementation will have a better idea

of what hashes will work best for it. Moreover, I'm mostly stating

the tautology that compilers may cheat where they can get away

with it.

Wanting to substitute a cryptographically strong hash function is

perhaps a better counter-argument which makes me think this is

better left unsaid.

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

Can you explain that?

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.

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

Actually, given Taylan's proposal I think hash-table-intern! is a

perfectly good, if Lisp-centric, name.

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

Or success in hash-table-replace!.

So we require both?

Actually, I believe hash-table-extend! as specified is broken,

because you don't apply success uniformly. Assuming we

have a table of country capitols, all in titlecase, then

(hash-table-extend! capitols "France" (lambda () "Paris") string-downcase)

will return "Paris" if not present, but "paris" if present. Yet

calling it a second time is guaranteed to return "paris".

hash-table-replace! I'd have to see examples for. I'm not

sure why it's needed distinct from -update!.

Alex