Pythonで学ぶ 基礎からのプログラミング入門 (11) 知っていると便利な「型」について学ぼう

がいるかどうか確認すればいいのです。どうです、リストの探索が「先頭から末尾まで順に「John Smith」かどうかを確認していく」ことであるのに比べると随分スマートだと思いませんか。実際、ハッシュを使った要素の探索は非常に高速です。

ただ、ハッシュも使い方を間違えると効率が悪くなります。もう一度図を見てください。よく見ると「John Smith」と「Sandra Dee」は同じハッシュ値に割り当てられていますね。これはいわゆる「ハッシュの衝突」と呼ばれており、これが多発すると探索のスピードが遅くなります。なぜなら「Sandra Dee」の有無の確認をする際に「01」を見にいって、そこに「John Smith」やほかの要素がたくさん入っていると、「01」のなかで「リストの探索」のようにして全部をチェックしていかないといけないからです。

この問題を防ぐためにハッシュ値の範囲は十分な広さを持たせる必要があります。たとえば今回のように00から15などという範囲は狭すぎるので、これをもっと広げます。そうすると確率的には衝突は発生しにくくなります。まぁ、普通はこんなことを気にしなくてもPythonがよしなに処理してくれるので大丈夫です(笑)。