Re: [Scheme-reports] Seeking review of sets and hash tables proposals Biep 27 May 2013 09:44 UTC

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
Scheme-reports@scheme-reports.org
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports