私はハッシュテーブルと一様に分散されたハッシュ関数を持っており、それはリンクされたリストと別の連鎖を使用しているとしましょう。O（1）の時間の複雑さを平均的に節約するために、キー全体をハッシュする必要がありますか？
テーブルに保存されたキーは(a,b)（無制限の数字）のペアであり、hash(a)（私はbを無視しています）に従ってテーブルに挿入します。
find,insertおよびdeleteはまだ平均でO(1)にありますか？または、bを含むキー全体をハッシュする必要がありますか？
いいえ、期待されるO（1）ルックアップを保証するものではありません。たとえば、ハッシュ（0、0）、（0,1）、（0,2）、（0,3）、...、（0、n-1）を想像してみてください。これらの値のすべてnは、テーブルの同じ場所にハッシュします（2番目のコンポーネントは無視されるため）。ハッシュ関数が最初のコンポーネント（0）をどのようにハッシュするかに関係なく、同じ位置にn個の要素があります。あなたのルックアップを最悪の場合にはΘ（n）の時間に堕落させるハッシュテーブル。
一般に、ハッシュテーブルを使用する場合は、キー全体をハッシュする必要があります。それ以外の場合は、キーの一部を一定に保ち、他の部分を変更することで、ハッシュの衝突で簡単に終了することができます。
とにかくこの 'O（n）'最悪の場合です。平均的なケースはどうですか？どのようにそれを台無しにするのですか？ –
@XtremeJoe「平均」という言葉が聞こえたら、「何を平均化したのか」と思っているはずです。従来のハッシュテーブル分析では、データが無作為に選択され、ハッシュ関数によってランダム性が提供され、良好なハッシュテーブルの実装では、提供されるデータに関係なく良好な保証が提供されることが前提です。提案する方法で平均的なケース分析を行うには、可能な入力に対する確率分布の数学的に厳密な記述を提供する必要があります。 – templatetypedef
しかし、私が提示したケースでは、 'b'について何も知りませんでしたが、入力上で' O（1） '平均を達成することが可能です –
キーとして(a, b)を使用していて、hash(a)に基づいて格納する場合は、同じ値の複数のオブジェクトがある場合はいつでも衝突します。aたとえば、(1, 2)と(1, 3)は両方とも同じバケットにハッシュするので、リンクされたリストをトラバースする必要があります。実際のパフォーマンスへの影響はデータセットによって異なりますが、平均してではなく、ではまだO（1）のパフォーマンスがあります。
事前にaとbについて何か知っていますか？いいえの場合は、両方をハッシュする必要があります。両方がかなりランダムであることがわかっている場合は、単独でのハッシングは十分であるはずですが、2つの整数をハッシュするのは1つの計算よりも計算量が多いはずはありません。
*を組み込むのに最適です*重要なことは重要な洞察です。また、ハッシュされるペアの数を大幅に超えています。そうであれば、衝突はほとんどありません。これは、0から10の範囲の 'a'と対照的です.bは0から10億です。値は非常にランダムですが、百万のペアをハッシュしている場合、衝突が発生しています。 –
「無制限の数字」*は何を意味しますか？すなわち、非常に多数のこのようなペアが存在する可能性があるか、または個々の整数が広い範囲にわたって均等に分布している（例えば、すべての32ビット値が等しくなる可能性がある）、または...？ –
@TonyD彼らは何でもかまいません –