Hashing p-adic elements
David Roe
I'm working on #11895, which points out that there is no hash for
extension elements. And I have a design question which applies to
hashing for elements of Qp and Zp as well.
sage: a
1 + O(5^2)
sage: b
1 + 5^2 + O(5^5)
sage: a==b
True
sage: hash(a)
1
sage: hash(b)
26
Of course, we see this problem for elements of Zmod(N) compared to
integers as well, but the problem is even more severe here. Two
elements of Zmod(N) will have the same hash if and only if they are
equal (with some exceptions when N is very large). But here we see
that equal elements of Zp(p) can have different hashes.
The best solution I can think of is to choose some k with p^k at least
a fixed size (e.g. k = ceil(log_p(2^20)) and reduce all hashes modulo
p^k. The reason to not just reduce modulo p is that for small p we'd
get too many collisions and lose a lot of efficiency for dictionaries
using p-adic elements as hash keys. But maybe it's worth the
efficiency loss to ensure that equal elements have the same hash value
(I'm not worried about elements with zero precision).
Thoughts?
David
William Stein
This is a huge general problem in implementing mathematics using
Python. On the one hand we have (from [1]): "The only required
property [of __hash__] is that objects which compare equal have the
same hash value."
On the other hand, this is violated all over the place in Sage. For example,
sage: ComplexField(10)(1/3) == ComplexField(20)(1/3)
True
sage: hash(ComplexField(10)(1/3)), hash(ComplexField(20)(1/3))
(1432322048, 1431623680)
sage: 5 == Mod(2,3)
True
sage: hash(5), hash(Mod(2,3))
(5, 2)
[1] http://docs.python.org/reference/datamodel.html
I think the main way Python uses this assumption is when making
dictionaries (and sets). E.g.,
sage: d = {5:'a', Mod(2,3):'b'}
sage: d[5]
'a'
sage: d[Mod(2,3)]
'b'
sage: d.keys()[0] == 5
True
sage: d.keys()[1] == 5
True
A purist might reasonably say that d should have len = 1, since the
two keys are equal. But it has length 2 since the hash values are
different. In contrast, when the hash values are the same we have:
sage: d = {2:'a', Mod(2,3):'b'}
sage: d
{2: 'b'}
Thus the behavior depends on the hash values.
In my experience, once one learns this subtlety, one can use Python
just fine *without* making the following assumption in the case of
specialized numeric types: "The only required property [of __hash__]
is that objects which compare equal have the same hash value."
-- William