質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.10%

Python hashデータタイプの意味

解決済

回答 3

投稿

  • 評価
  • クリップ 1
  • VIEW 628

score 54

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

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

解説お願い致します。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • Lhankor_Mhy

    2018/02/10 12:44

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

    キャンセル

  • oookabe

    2018/02/10 16:45

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

    キャンセル

回答 3

checkベストアンサー

+4

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):
    ...


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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/02/10 23:13

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

    キャンセル

+1

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/02/10 16:47 編集

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

    キャンセル

  • 2018/02/10 17:07

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

    です。

    キャンセル

  • 2018/02/10 23:11

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

    キャンセル

0

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.10%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る