fix hash of (dense) matrices

[dkrenn]

It took me only 4 guesses to find two matrices with the same hash:

sage: N = Matrix([[1,1],[2,2]]); N.set_immutable(); hash(N)
3
sage: N = Matrix([[0,0],[0,1]]); N.set_immutable(); hash(N)
3

This should not be that easy.

In particular (looking at the code in sage.matrix.matric_dense), the hash value does not depend on entry 1,1 of the matrix (multiplication by zero in the hash code):

sage: N = Matrix([[3,2],[0,0]]); N.set_immutable(); hash(N)
2
sage: N = Matrix([[443,2],[0,0]]); N.set_immutable(); hash(N)
2
sage: N = Matrix([[2,2],[0,0]]); N.set_immutable(); hash(N)
2

Component: misc

Work Issues: adapt doctests

Branch/Commit: u/dkrenn/hash-matrix @ 1e1263f

Issue created by migration from https://trac.sagemath.org/ticket/21316

[dkrenn]

comment:1

From sage.matrix.matrix_dense:

        v = self._list()
        cdef Py_ssize_t i
        cdef long h = 0

        for i from 0 <= i < len(v):
            h = h ^ (i * hash(v[i]))

What is a good caching strategy? Simply h = hash(tuple(self._list()))?

[sagetrac-ibookstein]

comment:2

Non-cryptographic hashes don't have to be resilient to collision attacks, but should indeed give good hash value spread for the input space - which this implementation doesn't.

I can confirm that this implementation causes massive performance degradation when matrices are used as dictionary keys, for instance.

See tuple hash algorithm and explanations why XORing hash values doesn't perform very well.

While the current implementation does try to 'save' itself from the disadvantages of XORing hash values by multiplying by the index, it still performs very poorly.

I tried the solution dkrenn suggested and it does indeed work much better.
If we don't care about the performance cost of creating a tuple (and a list), seeing as the hash value is cached, it's a nice solution.

[dkrenn]

Branch: u/dkrenn/hash-matrix

[dkrenn]

Commit: 1e1263f

[dkrenn]

Work Issues: adapt doctests

[dkrenn]

New commits:

1e1263f

new hash function for matrix_dense

[sagetrac-ibookstein]

comment:6

Looks like major work was put into this issue in #19050, rendering this ticket a duplicate.

[jdemeyer]

comment:7

Duplicate of #10950.