ハッシュテーブル対リニアリスト

Question

リニアリスト内のキーワードの検索がハッシュテーブルより高速になる場合がありますか？

リニアリストのキーワードの検索がハッシュテーブルの検索よりも高速になる場合があるかどうかを知りたいと思っています。

ありがとうございます！

Answer 1

はい、非常に少数の要素の場合です。ハッシュの仕組みについて考えてみましょう。それは、バケットを見つけるためにハッシュを計算し、そのバケット内のリストを検索しなければなりません。さらに複雑なマルチレベルのハッシュなどがあります。したがって、リニアリストを検索することは、ハッシュ検索アルゴリズムよりも多くの作業が必要です。

あなたが探している要素が常にリストの先頭または先頭にある場合も、別のインスタンスがあります。あなたがしていることに応じて、それが起こる可能性があります。

他にもありますが、それについて考えるのに役立ちます。

まだ、混乱しないでください。ハッシュは通常あなたが望むものです。

Answer 2

ハッシュテーブルでの検索は、実際には常に一定時間であるとは限りません。ハッシュ関数がデータとのマッチングが悪い場合は、多くの衝突が発生する可能性があり、極端な場合はすべてのデータ項目が同じハッシュ値を持つため、結果は線形検索によく似ています。詳細に応じて、この効果的な線形検索は、配列内のデータに対する線形検索よりも遅く動作する可能性があります。 （例えば、プロセッサキャッシュの貧弱な使用をもたらす2次探索シーケンスを用いたopen addressing）は、アレイ上の線形探索よりも遅い可能性がある。同じバケット：Java bug 4669519。