Python dictionary with list keyword
-
11-05-2021 - |
Pregunta
I'm coding a N'th order markov chain.
It goes something like this:
class Chain:
def __init__(self, order):
self.order = order
self.state_table = {}
def train(self, next_state, *prev_states):
if len(prev_states) != self.order: raise ValueError("prev_states does not match chain order")
if prev_states in self.state_table:
if next_state in self.state_table[prev_states]:
self.state_table[prev_states][next_state] += 1
else:
self.state_table[prev_states][next_state] = 0
else:
self.state_table[prev_states] = {next_state: 0}
Unfortunally, list and tuples are unhashable, and I cannot use them as keywords in dicts... I have hopefully explained my problem well enough for you to understand what I try to achieve.
Any good ideas how I can use multiple values for dictionary keyword?
Followup question:
I did not know that tuples are hashable. But the entropy for the hashes seem low. Are there hash collisions possible for tuples?!
Solución
Tuples are hashable when their contents are.
>>> a = {}
>>> a[(1,2)] = 'foo'
>>> a[(1,[])]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
As for collisions, when I try a bunch of very similar tuples, I see them being mapped widely apart:
>>> hash((1,2))
3713081631934410656
>>> hash((1,3))
3713081631933328131
>>> hash((2,2))
3713082714462658231
>>> abs(hash((1,2)) - hash((1,3)))
1082525
>>> abs(hash((1,2)) - hash((2,2)))
1082528247575
Otros consejos
You can use tuples as dictionary keys, they are hashable as long as their content is hashable (as @larsman said).
Don't worry about collisions, Python's dict takes care of it.
>>> hash('a')
12416037344
>>> hash(12416037344)
12416037344
>>> hash('a') == hash(12416037344)
True
>>> {'a': 'one', 12416037344: 'two'}
{'a': 'one', 12416037344: 'two'}
In this example I took a string and an integer. But it works the same with tuples. Just didn't have any idea how to find two tuples with identical hashes.