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 [email protected] http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports
