[m-dev.] For review: hash table implementation

[David Overton]

Hi,

On Wed, Jan 31, 2001 at 08:18:53AM -0800, Ralph Becket wrote:
> This has been missing for too long.  It should be considerably faster
> and more economical than maps in many cases (each update consumes only
> 6 or 7 words of storage, and only 1 if structure reuse works for it).
> Of course, against that you have the fact that you're using extra space
> up, but in practice occupancy should be between 45 - 90% which is on a
> par with 234-trees.
> 
> Downsides: arguably more expensive for mapping and folding (I have yet
> to supply these functions); weird modes are required; you have to supply
> hashing predicates for each key type (anyone got a generic hash
> function or two handy?)

For a start, the standard library has float__hash and string__hash.

> :- type hash_pred(K) == ( pred(K, int, int) ).
> :- inst hash_pred    == ( pred(in, out, out) is det ).
> 
>     % new(HashPred, N, MaxOccupancy)
>     % constructs a new hash table with initial size 2 ^ N that is
>     % doubled whenever MaxOccupancy is achieved; elements are
>     % indexed using HashPred.
>     %
>     % N must be greater than 1.
>     % MaxOccupancy must be in (0.0, 1.0).
>     %
> :- func new(hash_pred(K), int, float) = hash_table(K, V).
> :- mode new(in(hash_pred), in, in) = hash_table_uo is det.

Another approach here would be to use a type class `hashable' and define
an instance for each type you want to hash.  Have you considered this?


David
-- 
David Overton      Department of Computer Science & Software Engineering
PhD Student        The University of Melbourne, Victoria 3010, Australia
+61 3 8344 9159    http://www.cs.mu.oz.au/~dmo
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------