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

[Ralph Becket]

>From David Overton on 01/02/2001 12:48:26
> > 
> > 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.

Yes, I use string__hash in string_hash_pred.  However, what is lacking is
something like

	:- func generic_hash(T) = int.

and, in this case, two different hash functions would be handy.

Aside: is there any real point in providing float_hash_pred and
char_hash_pred?
The former sounds absurd and the latter is probably better served with a
list
or array based approach.

> >     % 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?

That crossed my mind, but it's not clear to me how useful double-hashing
functions are going to be outside this hash table implementation.  Might
it not be easier just to supply the appropriate pred when creating the
hash table?  I'm certainly prepared to be persuaded on this one.

Ralph

--
Ralph Becket      |      MSR Cambridge      |      rbeck at microsoft.com 

--------------------------------------------------------------------------
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
--------------------------------------------------------------------------