Python hashデータタイプの意味

Question

Python hashデータタイプについて質問させていただきます。

hashタイプのデータは本当にhash算法を行ってアクセスするのでしょうか。
この場合の目的は何でしょうか。
通常hash算法は非常に処理量が多い、能率悪いだと思いますが
どうしてわざわざhashをやるのでしょうか。

解説お願い致します。

Comments

[Lhankor_Mhy]

これは、辞書の実装のことでしょうか。だとすると、C言語のタグをつけたほうがいいかもしれません。

[oookabe]

辞書にhashを使う「目的」に関するお尋ねです。

Answer 1

hashはPythonのdict型のことである前提でコメントします。

通常hash算法は非常に処理量が多い、能率悪いだと思います

推測ですが、質問者さんはハッシュ値の計算にのみ着目して処理量が多いと思っておられるのではないでしょうか？しかしながらアルゴリズムというのは全体の計算量が多いか少ないかが問題なのでハッシュ値の計算量にのみ着目しても肝心な「全体的な処理の効率」を見誤る恐れがあると思います。

例えば

(A) ハッシュ値を求める計算量
(B) 2つの文字列の比較の計算量

を単純比較すれば1回当たりの(A),(B)の計算量では(B)の方が計算量が低いかも知れません。従って要素数が1とか2とかの文字列コレクションの中に特定の文字列が含まれているかを検索する場合はハッシュサーチを用いず、順サーチして求めた方が早い場合もあるでしょう。(実際世の中には「要素数がごく少数の場合は順サーチし、ある程度大きくなった場合にハッシュサーチに切り替える」といった凝ったライブラリーもあると思います。自分はPythonの実装には暗いため実装がどのようになっているか分かりませんが・・・)

一方、コレクションの中の要素数が一定以上多かったり、その中から何度も検索するような場合を考えてみてください。順サーチではコレクションの要素数の数Nに対して計算量のオーダーはO(N)になりますが、ハッシュアルゴリズムではO(1)になりますので後者がはるかに高速になります。ちなみにハッシュ値の計算を同一のインスタンスに対して何度も行わなくてよいように、一度計算したらインスタンス内部に（ひそかに）記録されるような実装も一般的です(すみませんが、これについてもPythonの実装がそうなっているかどうかまでは自分は知りません)。

どうしてわざわざhashをやるのでしょうか。

仮にPythonのdictの実装が先に述べたように「要素数が少数の場合に順サーチする」といった最適化をしていないと想定してみましょう。要素数が少ない場合確かに順サーチの方が少し効率はよいかも知れません。ただ、そもそもそういう場合は全体の計算量そのものが小さいため、ハッシュアルゴリズムであろうと順サーチであろうと大きな性能差が出ることはないでしょう。逆に要素数がある程度以上多い場合はハッシュサーチに比べ順サーチは致命的に遅くなります。

以上を総合的に考えると「一般的により全体の処理効率がより早くなることを期待して」ハッシュアルゴリズムが用いられていると理解すればよいと思います。

---

ちなみに、いくら賢くできたライブラリーを使ってもアプリケーションプログラマーが愚かな実装をすると、せっかくの優れたアルゴリズムも役に立たないようなことも起き得ます。例えばハッシュ値の計算量を気にするあまり「ハッシュ値の計算を必要以上にサボってしまう」と、ハッシュサーチとは名ばかりで事実上順サーチと同程度の計算量になる場合も有ります。ライブラリーは「なんとなくうまいことやってくれるブラックボックス的なもの」と考えてしまいがちですが、「それがどういう考え方で設計されているか」について考えることは価値あることと思います。そういう意味で質問者さんの疑問は良い疑問ではないかと思います。

ハッシュとは何かをきちんと把握しておけば独自に定義したクラスをdictのキーとしたいような場合に

class MyClass:
  def __hash__(self):
    return 1       # どのインスタンスでも常に同じハッシュ値=>ナンセンス
  def __eq__(self, other):
    ...

みたいなとんでもないポカをせずに済むのではないでしょうか・・・
「そんなことしないよ」と多くの方が思われることでしょう。しかし自分はこんな実装を過去にみたことがあります。おもわず「あわわ・・・」と思ってしまいました。

Comments

[oookabe]

最高のご指導有難うございました！

Answer 2

Pythonのハッシュ算法にかんする詳細はここに書いてあります。

Comments

[oookabe]

お返答有難うございます。
Pythonの辞書タイプは本当にhashを使っているかどうか、それから使う「目的」に関するお尋ねです。
------Python辞書の具体実装コードを解読する能力はないですね。

[YouheiSakurai]

Pythonの辞書タイプは本当にhashを使っているかどうか->yes、(Pythonの辞書タイプでhashを)使う「目的」->キーに対する値の参照コストをオーダー1にするため。

です。

[oookabe]

すっきりです。
有難うございました！

Answer 3

検索の計算オーダーが1だからではないですか？