[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Scheme-reports] Seeking review of sets and hash tables proposals

If collisions are resolved by having binary trees in hash buckets, any too course hash function will be acceptable.
A constant hash function will then yield an O(log n) map, whereas a perfect hash function will yield a O(1) map.

Given an equivalence predicate:
(1) if the user provides a hash function, it will be used;
(2) if a hash function is associated with the predicate, it will be used;
(3) the constant hash function will be used.

This would allow for graceful degradation, useful user hash functions even if the user doesn't grasp all the subtleties, and a uniform map structure that includes both the O(1) and the O(log n) case.

Scheme-reports mailing list