ハッシュ値の計算方法

Python

なるほど。__hash__も__cmp__、__eq__も定義されていなければid(obj)が使われるのか。

なんで「tp->tp_compare == NULL && RICHCOMPARE(tp) == NULL」って条件が必要なのかがわからない。tp_hashを持っているならそれでハッシュ値を計算して、持ってないならポインタの値から計算する、でいいのに。

これは、

に書いたことで、

>>> class Foo(object):
...     def __init__(self, v):
...         self.value = v
...     def __cmp__(self, oth):
...         return cmp(self.value, oth.value)
...
>>> d = dict()
>>> d[Foo(1)] = 'a'  # 辞書にキーFoo(1)の値'a'を登録
>>> d[Foo(1)]        # 辞書からキーFoo(1)の値を参照
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: <__main__.Foo object at 0x00C26210>

もし旧スタイルクラスで__hash__が定義されずに__cmp__が定義されていてTypeErrorにならなければ、こういう矛盾が起きるので、それを避けるためだと思う。しかし、新スタイルクラスではobjectに__hash__が定義されているので必ず__hash__を持つので、Cのソース中のTypeErrorは起こらないと思う。その代わり、list自体は__hash__でTypeErrorを投げるように実装されているのではないだろうか。旧スタイルクラスは以下のようにTypeErrorを出せる。

>>> class Old:
...   def __cmp__(self, oth):
...     return cmp(self, oth)
...
>>> o = Old()
>>> d = {}
>>> d[o] = 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable instance

まとめると、ハッシュ値の決め方は以下の手順。

  1. __hash__が定義されている。 ⇒ obj.__hash__()
  2. __hash__が定義されていない。かつ、__cmp__および__eq__が定義されてない。 ⇒ id(obj)
  3. __hash__が定義されていないが、__cmp__もしくは__eq__が定義されている。 ⇒ TypeError

まだ完全な理解をしていないので、もう少し研究してみるつもりだが、Python 3.0から旧スタイルクラスはなくなるので、新スタイルクラスの挙動が分かれば十分な気がしてきた。新旧2つを統一的に考えようとすると複雑になりすぎるかも…。


追記：

まとめると結局、「__hash__が定義されていれば辞書のキーにすることが可能」というのは間違いではないが、__hash__が定義されていない他の条件でも辞書のキーにすることが可能。むしろ辞書のキーにすることができない場合は以下の2通りと言えるのではないだろうか。

  • __hash__が定義されていなくて、かつ、__cmp__もしくは__eq__が定義されている場合。
  • __hash__で正しい整数値(ハッシュ値)を返さない場合。例えばTypeError例外が発生するなど。