Hashing arrays in Python

Question

Is it possible to hash lists?

For example, I know that hashes of tuples are possible:

>>> hash((1,2,3,4,5,6))
-319527650

But is it possible to hash a list?

>>> hash([1,2,3,4,5,6])
hash_value

Possible Solution:

Very in depth explanation to the hashing of lists, here.

Solution 1

Just try it:

>>> hash((1,2,3))
2528502973977326415
>>> hash([1,2,3])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> hash(frozenset((1,2,3)))
-7699079583225461316
>>> hash(set((1,2,3)))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'set'

So you can get hash of tuple and frozenset since the are immutable, and you can't do it for list and set because they are mutable.

Solution 2

If you really need to use a list as a dictionary key, try converting it to a string first.
my_list = str(my_list)

Solution 3

Python doesn't allow you to use mutable data as keys in dictionaries, because changes after insertion would make the object un-findable. You can use tuples as keys.

Comments

[Adam Parkin]

That's slightly incorrect, a user-defined class can be written to be hashable (and therefore be able to be a key in a dict) but its pretty damn hard to create an immutable user-defined class in Python.

[N. Virgo]

If you're going to go to the bother of converting to another data type, wouldn't a tuple make more sense?

[cgogolin]

Hashing of tuples however doesn't seem to work properly: hash((1,2,3)) yields 2528502973977326415, but hash((1,2,4)) also yields 2528502973976161366 (tested on Python 2.7.9)

[Dmitry Shintyakov]

@cgogolin The values are different, everything works properly.

[cgogolin]

Oh dear, if I could, I would down vote my own comment. I fooled myself by only comparing the first few digits of the hashes.

[Ciro Santilli OurBigBook.com]

@cgogolin good observation anyways. So many equal digits shouldn't be a coincidence, which indicates that the hashing algorithm is not very good.

[Him]

"hashing algorithm is not very good". Depends on what you need it for. Are you using it for cryptography? Well, don't do that, because the hashes are correlated with the input. Do you need to obtain a hash value quickly for looking up dictionary keys? Then this is a perfectly fine hash algorithm.

[SO_fix_the_vote_sorting_bug]

@cgogolin, that's why I always compare the first few and last few digits (hexits?) in an md5sum; not fool-proof, but it "feels" good. I'll probably get burned one day...