On 04/01/2015 12:21 AM, Waldek Hebisch wrote:
> Bill Page wrote:
>> I agree that that is an essential part of the definition of hash
>> function. In the existing XHashTable code if an incompatible hash
>> function is passed the almost immediate result is an array bounds
>> failure in the 'rehashAux!' routine due to an unexpected duplicate
>> key. A simple change in 'localSearch' to check both hash and eq, for
>> example:
>>
>> hk := h k
>> h1: Z := hk::Z
>> ...
>> hk = h toKey mk and eq(k,toKey mk) => return p -- key found
>> ...
>> not deleted? mk and hk = h toKey mk and eq(k,toKey mk) =>
>>
>> is sufficient to prevent this and maybe preferable since usually
>> calling hash is much cheaper than computing eq even when eq defaults
>> to =$Key. Since evaluation of 'and' is lazy I guess the mileage will
>> depend on the statistics of hits and misses.
> 2) What you write above looks like attempt at error hiding.
> If essential precondition is violated, then more approprate
> reaction is to signal error. In this case I would say that
> doing extra computation to detect errors is probably not
> worth the effort. Rather, detectiong out of bound array
> index is enough. We may add some test to give better
> error message, but it should be cheap (like comparing index
> with bound).
Well, in fact, Bill found a (small) bug.
table: (Key -> SingleInteger) -> %
++ table(h) creates an empty hash table that uses h instead of
++ hash$Key. Note that h should be a mathematical function in
++ the sense that from k1=k2 follows h(k1)=h(k2). If that is not
++ the case, k1 and k2 will internally be considered as being
++ different keys.
The last sentence is nothing for the specification. So I require
if k1=k2 then h(k1) = h(k2).
And since that is precondition in the specification, anything can happen
if a user of that function does not meet that condition. In other words,
I don't see need to add extra checking code.
I'm slowly checking whether I can convince myself to allow eq instead of
=$Key. Might take a few more days.
Ralf
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
