On Mar 17, 3:29 pm, Jeroen Demeyer <jdeme...@cage.ugent.be> wrote:
> On 2011-03-17 15:04, Jason Grout wrote:
>
> > def hash(self):
> > h=0
> > for i,j,entry in m.nonzero_entries(): # nonzero entries for sparse
> > matrices
> > h^=hash(entry)^i^j
> > return h
>
> Since you're only xorring, this will give a lot of collisions. I think
> something like
>
> def hash(self):
> n = m.ncols()
> h = (m.nrows() + m.ncols())**2 + n
> for i,j,entry in m.nonzero_entries():
> h ^= hash(entry)*(i*n + j + 1)
> return h
>
> has less chance of collisions. Of course everything should be computed
> as a C long.
>
> Jeroen.
an even better solution with respect with collision would be to rotate
the hash state
:
def hash(self):
n = m.ncols()
h = (m.nrows() + m.ncols())**2 + n
for i,j,entry in m.nonzero_entries():
h = ((h << 17) | (h >> (sizeof(long) - 17))) ^
hash(entry)*(i*n + j + 1)
return h
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
