immutableクイズ - aodagの日記

http://www.nishiohirokazu.org/blog/2007/03/immutable.html
西尾さんとこにimmutableクイズ
リスト(のようなものまでOK?) をハッシュのキーにするコードの中間を埋める.
hashをなんとかすればいいので、__hash__を入れ替えてみる

>>> x = [0]
>>> x.__hash__ = lambda x: x[0].__hash__()
<type 'exceptions.AttributeError'>: 'list' object attribute '__hash__' is read-only

直接入れ替えはダメですorz

ひょっとしてhash関数交換すればいいんじゃね?

>>> __biltins__.hash = lambda x: x.__hash__() if not isinstance(x, list) else x[0]
>>> hash([0])
0
>>> dic = {[0], 0}
<type 'exceptions.TypeError'>: list objects are unhashable

... dict内ではhash関数使ってないのかorz
しょうがないlistを継承しよう

>>> class HashableList(list):
>>>     def __hash__(self):
>>>         return self[0].__hash__()
...
>>> dic = {HashableList([0]), 0}
>>> dic
{[0], 0}
>>> dic[HashableList([0])]
0

上記の__hash__メソッドは同内容の場合ももちろん同じハッシュ値を返す.
さてここで、キーに要素を追加してみよう.
listを継承しているからもちろん可能だ.

>>> dic.keys()[0].append(1)
>>> dic
{[0, 1]: 0}
>>> dic[HashableList([0, 1])]
0

この場合はハッシュ値に変わりがないが値自体は変わっているためHashableList([0,1])で取得する.
ちなみに第一要素を変更するとハッシュ値が変わってしまい、dict内でハッシュ値と異なるバケットに入った状態になってしまいキーでアクセスできなくなる.
それでもkeysメソッドなどでキー一覧を取得すると値はちゃんとHashableList([1,1])と等しい.

>>> dic.keys()[0][0] = 1
>>> dic
>>> {[1, 1]: 0} 
>>> dic[HashableList([1,1])]
<type 'exceptions.KeyError'>: [1, 1]
>>> dic.keys()[0] == HashableList([1,1])
True

mutable なリストでは内容を基にしたHash値を使うとHash値が変わる可能性がある.
Hash値が変わるとキーを使って参照できなくなる(ハッシュ値と違うバケットに値が入った状態になるから)
でも内容を基にしたHash値を使わないと, あとからキーを作成するのが面倒.
例えば, オブジェクトidを使うと、そのオブジェクトを保持してないといけない.
ということでmutableなリストをdictのキーに使うと甚だ不便というかバグのもとというか使い物になりません.