[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Scheme-reports] Seeking review of sets and hash tables proposals
- To: <scheme-reports@x>
- Subject: Re: [Scheme-reports] Seeking review of sets and hash tables proposals
- From: Biep <scheme@x>
- Date: Mon, 27 May 2013 13:44:51 +0400
- In-reply-to: <firstname.lastname@example.org>
- References: <email@example.com>
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