Ralf Hemmecke wrote:
>
> >> Ah, before I forget. XHashTable in my opinion is not going to replace
> >> HashTable, but rather Table. (Not at the moment, of course, but that
> >> would be my plan.)
>
> > We need to implement hash functions first
>
> Yes, I see the problem with good hash functions, but I think good hash
> functions are orthogonal to providing a good hash table implementation.
>
> OK, but if you mean to replace AssociationList, that's of cource another
> issue.
I was specifically writing about replacing AssociationList case of
Table.
> Do you see for the meantime any chance to recognize a good hash
> function from a bad one? I mean, before we started there was a default
> implementation of hash(x)=0 in SetCategory.
>
> Maybe we could rather define a default hash==badHash
>
> with a global function (maybe lisp) badHash and in Table try to test
> whether hash$Key = badHash (pointer comparison of where the function
> object is stored). If it is still badHash, then AssociationList would be
> used otherwise XHashTable could jump in.
This should be possible with some Lisp support.
> Anyway, defining a hash for a general expression is probably impossible
> if equality of the underlying domain is used. But what is Maple doing
> when one adds "option remember". In fact, to implement a cache, it's
> irrelevant whether hash(k1)=hash(k2) for k1=k2 where k1 and k2 have
> different underlying representation. It just means storing more entries
> in the table and of course some related consequences. But even with a
> bad (but reasonably well distributing) hashing routine (i.e. not a
> mathematical function), a true hash table instead of an association list
> could have some advantages. Probably depends on the user's needs.
>
> In general I would assume that the user knows when the hasing routine is
> bad for the respective key domain.
AssociationList may be used to remove duplicates, for this equality
from domain is mandatory. For caching small number of duplicates
is not a problem.
General case needs more thought. We want generic code in algebra,
so writer of library routine does not know if parameters are
suitable for hashing.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
