アイテムがランダムに編成されている場合、テーブルはどのようにしてどこから探し始めるかを知るのですか？
非ランダムテーブルでは、アイテムはいくつかの特性に従って編成されます。（つまり名前）。したがって、テーブルが「John」に関する任意の情報を検索する必要がある場合は、「J」バケットの検索を開始できます。
ただし、ユニバーサルハッシュテーブルでは、アイテムはランダムに配置されます。明確な特徴はありません。したがって、「ジョン」に関する任意の情報を見つけるために、テーブルはすべてのバケットを調べる必要はありませんか？
それは時間の無駄ではありませんか？それはあなたの家のすべてのキャビネットを調べてスプーンを見つけるようなものです。
前の答えは本質的に正しいですが、それらはユニバーサルハッシュアルゴリズムのランダムな部分に直接対処していません。ユニバーサルハッシュアルゴリズムは、キーのハッシュを計算するときにランダム性を使用しません。乱数は、ハッシュ関数のファミリーからハッシュ関数を選択するためにハッシュテーブルの初期化中にのみ使用されます。これにより、ハッシュ関数の詳細にアクセスできる攻撃者が最悪の場合のキーのセットを考案するのを防ぐことができます。
つまり、ハッシュテーブルの存続期間中、特定のキーのバケットは一貫しています。ただし、別のインスタンス（次回のプログラム実行時など）では、同じキーを別のバケットに配置する場合があります。
ハッシュは多かれ少なかれランダムに見えますが、決定論的です。つまり、特定の入力は常に同じハッシュ値を生成します。
これに基づいて、ハッシュテーブルにアイテムを挿入する場合は、まずその入力のハッシュを生成します。次に、それを使用してテーブルにインデックスを付け、テーブルのその場所にアイテムを挿入します。通常、キーとして扱われる部分が1つあり、それに関連する情報がいくつかあります（たとえば、名前で人を検索でき、名前ごとにその人に関する情報があります）。
後で、特定のキー（この場合は人）を検索（関連付けられている情報）する場合は、キーを入力してハッシュし、ハッシュテーブル内でその情報を検索する適切な場所を見つけます。
これは、同じハッシュ値を生成するために発生する2つ以上の入力を処理する方法など、いくつかの重要な詳細をスキップします（許容される入力に制限を設けない限り、これは避けられません）。これを処理するには、テーブルを順番に調べて次の空きスポットを見つける、再ハッシュしてテーブル内の別のスポットを見つける、同じ値にハッシュされたアイテムのリンクリストのようなものを作成するなど、さまざまな方法があります。
いずれにせよ、ハッシュテーブルがあなたが推測したように少し終わるユースケースがあることをおそらく追加する必要があります。ほんの一例として、（一度に1つのアイテムを検索するだけでなく）ハッシュテーブルのすべてのコンテンツを表示する場合、通常はテーブル全体をスキャンします。ハッシュテーブルがほとんど空の場合でも、通常は一方の端からもう一方の端までスキャンして、実際に使用されているすべてのエントリを探す必要があります。これを行うと、かなりランダムに見える順序でアイテムを取得します。
これは、ハッシュテーブルのもう1つの欠点を示しています。通常、ハッシュテーブルが正常に機能するには、単一の元のレコードと正確に一致する必要があります。たとえば、私の名前に基づいたいくつかのクエリを考えてみましょう。家系の名前全体でインデックスを作成したとすると、「棺」を見つけるのは簡単ですが、少なくともほとんどの通常のハッシュ関数では、「すべての名前を見つける」と同様に、「「Cof」で始まるもの」の検索は劇的に遅くなります。 「棺」と「デミング」の間。
そのため、あなたはある程度正しいです-ハッシュテーブルは通常、いくつかの特定のケース（主に完全一致を検索する）では非常に高速ですが、あなたが概説した一般的なアイデア（データを見つけるためにテーブル全体をスキャンする） ）は、他の目的で利用できるほぼ唯一の選択肢であるため、完全一致以外のものをサポートする場合は、別のデータ構造が望ましい場合があります。
これは主に、ハッシュテーブルの最も一般的な使用法/タイプを扱っています。これらのルールをさまざまな程度に少なくとも曲げる（完全に破らない場合でも）ハッシュ関数を作成することができます。ただし、ほとんどの場合、これらにはいくつかの妥協が伴います。たとえば、地理情報を入力として指定すると、座標（またはとにかくそれらの1つ）を切り捨てるだけで（ある種の）ハッシュを作成して、同じ情報をより低い精度で取得できます。これにより、情報が少なくともある程度整理されるため、近くにあるものは同様のハッシュ値になり、隣接するデータを見つけやすくなります。ただし、これにより衝突が増えることがよくあります（たとえば、大都市のダウンタウンでは、同じ値にハッシュされるアイテムが多数取得されます）。
特にユニバーサルハッシュを見ると、これによりパズルに1つの要素が追加されます。単一のハッシュ関数の代わりに、「ランダムに」選択するハッシュ関数のファミリーがあります。ユニバーサルハッシュを使用してハッシュテーブルを実装する場合（常にではありません。メッセージ認証コードなどにもよく使用されます）、通常、アイテムを挿入するたびにランダムにハッシュ関数を選択することはありません。むしろ、通常はハッシュを選択し、一定数の衝突が発生するまでハッシュを使用し続けます。次に、別のハッシュ関数をランダムに選択します。
たとえば、Cuckooハッシュ（おそらく最も一般的に使用されるユニバーサルハッシュ）では、キーをハッシュして場所を見つけます。すでに占有されている場合は、そこにある既存のアイテムを「キックアウト」し、再ハッシュして別の場所を見つけます。そこに挿入されます。そのスロットがすでに占有されている場合、そのスロットにすでにあるアイテムを「キックアウト」し、パターンが繰り返されます。
アイテムを検索するときは、それをハッシュしてその場所を調べます。それが空の場合、アイテムが存在しないことがすぐにわかります。そのスロットが占有されているが、アイテムが含まれていない場合は、別の場所を見つけるために再ハッシュします。使用している数のハッシュ関数に対してこのパターンを続けます（通常、カッコウハッシュの場合は2つだけですが、他の点では同様のアルゴリズムをより多くの関数で使用できることは明らかです）。
これが失敗する可能性があります-無限ループに入る、または（ほぼ同等に）事前に設定された長さを超えるチェーンを構築する。この場合、最初からやり直して、別のハッシュ関数のペアを使用してテーブルを再構築します。
オープンハッシュ（ユニバーサルハッシュが1つの形式）を使用する場合、削除は簡単ではない傾向があります。特に、ある場所でアイテムを削除するときに、その場所で衝突したアイテムのチェーンの始まりではないことを確認する必要があります。多くの場合、スロットに3番目の状態を追加するのが最も効率的です。スロットが占有されたことがない場合は、空です。現在使用中の場合は使用中です。アイテムがそこで削除されている場合、それは削除されます。このように、アイテムを検索しているときに「削除された」スロットに遭遇した場合は、アイテムの検索を続行します（一方、使用されたことのないスロットに到達した場合は、すぐに検索を停止できます。アイテムは明確に表示されます。挿入されたことはありません）。
ハッシュテーブルはランダムに編成されていません。ハッシュ値で構成されています。テーブルはハッシュ値で検索され、正しいハッシュグループが取得されます。