質問: pythonの辞書型を使いました。 今まで線形探索で行っていた単語の検索が異常に早くなり快適です。 ところで、ハッシュについて調べた所、 ``` h(x)=x%5 //5はテーブルの行数 ``` のようなハッシュ関数で振り分けていると分かりました。 しかし、私がこの前実行したpythonのコードでは単語数が100万語近くありました。 キーが衝突するかと思いましたが、高速に動作しました。 ここで疑問が2つ湧きました。 **・キーの衝突が無い(少ない?)ということは余りを求める数(上記のハッシュ関数の例では5)はpythonのdict型では可変なのでしょうか? ・キーの数自体が多い場合、キーの保存されている領域を探すために結局時間がかかるように思えるのですが・・・** 実際の実装の中身についてもお願いします --- 追記 回答を読んでいて、もう一つ疑問が生まれました。 キーは文字列ですよね。 では、文字列をキーにして、データにアクセスする方法(アドレスを指定する方法)はどうやって実装していますか? もともとC言語を扱っていたので、データにアクセスするにはアドレスを指定しないといけない気がします
回答: ハッシュテーブル自体はCの配列です。ハッシュ関数はkeyから、その配列のインデックスを求めるために使います。配列の要素へのアクセスは、先頭だろうと、真ん中だろうと、最後だろうと同じ時間でできるので速いわけです。 もちろんkeyの数が増えてくれば、インデックスの衝突が増えてアクセスが遅くなります。したがって、ハッシュテーブルのサイズは適宜大きくなります。