On 3/20/07, David Harvey <[EMAIL PROTECTED]> wrote:
> On Mar 21, 2007, at 1:19 AM, Nick Alexander wrote:
> > On Mar 20, 4:12 pm, William Stein <[EMAIL PROTECTED]> wrote:
> >> On Tuesday 20 March 2007 4:00 pm, Nick Alexander wrote:
> >>> For some reason, google won't let me grab your patch. Anyway,
> >>> converting to string is not a good idea. Better to hash a tuple of
> >>> real, imag I think. (Maybe you did this already?)
> >>
> >> You have to be really careful, since if a == b,
> >> then one should strive very hard to have hash(a) == hash(b).
> >> Thus, e.g.,
> >> if a is a real and b is a complex number with real part a and
> >> imaginary
> >> part 0, if you hash the strings then you get equality of the
> >> hashes, but
> >> if you hash the tuple you don't.
> > Hmm, it seems to me that this has deep implications. When hashing,
> > one really needs to find the 'minimal representation' of the element.
> > Suppose I want to hash QQ['x'](1), a constant polynomial. This should
[...]
> Oh boy I really really don't like where this is going. Insisting on
> "a == b" => "hash(a) == hash(b)" with sage's canonical coercion model
> seems really really bad.
>
> For example
>
> sage: Integers(123818273)(2394) == Integers(1)(0)
> True
>
> So then all integers mod n (for all n) have to hash to the same thing.
>
> Please let's not go there.
Sorry, but we have to go there, again. This has been discussed
before more than once on this list. Here's the definition of __hash__
in the Python reference manual [1]
"__hash__(self)
Called for the key object for dictionary operations, and by the
built-in function hash(). Should return a 32-bit integer usable as a
hash value for dictionary operations. The only required property is
that objects which compare equal have the same hash value; it is
advised to somehow mix together (e.g., using exclusive or) the hash
values for the components of the object that also play a part in
comparison of objects. If a class does not define a __cmp__() method
it should not define a __hash__() operation either; if it defines
__cmp__() or __eq__() but not __hash__(), its instances will not be
usable as dictionary keys. If a class defines mutable objects and
implements a __cmp__() or __eq__() method, it should not implement
__hash__(), since the dictionary implementation requires that a key's
hash value is immutable (if the object's hash value changes, it will
be in the wrong hash bucket)."
Notice the "The only required property is that objects which compare
equal have the same hash value". This is an assumption made by the
Python language, and violating has consequences. Fortunately, the
consequences are pretty clearly
defined and reasonably easy to understand, so if you know about them
they don't cause you trouble. I think the following example
illustrates them pretty well:
sage: v = [Mod(2,7)]
sage: 9 in v
True
sage: v = set([Mod(2,7)])
sage: 9 in v
False
sage: 2 in v
True
sage: w = {Mod(2,7):'a'}
sage: w[2]
'a'
sage: w[9]
Traceback (most recent call last):
...
KeyError: 9
---
That said, we simply can't require
(*) "a == b ==> hash(a) == hash(b)"
in SAGE, because mathematics is simply too complicated for this sort
of rule. So what is done in SAGE is to _attempt_ to satisfy (*) when it
is reasonably easy to do so, but use judgment and not go overboard.
E.g.,
sage: hash(Mod(2,7))
2
I.e., we get 2. That's better than some weird random hash that also
involves the moduli, but it's of course not right from the Python point
of view, since 9 == Mod(2,7). Long ago before we ever had this
discussion about hashing, I think Mod(2,7) was the hash of some
combination of 2 and 7.
Anyway, I hope this clarifies things for people.
[1] http://docs.python.org/ref/customization.html#l2h-196
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
