c++ - HashTable キーと値のフェッチの複雑さ

Question

ハッシュキーとハッシュ値のフェッチの複雑さを尋ねるインタビューの質問を読んだところです。私は常に、O(1 + n/k) (k はバケットの数) で、両方が同じであると考えていました。私は何が欠けていますか？

Answer 1

ハッシュキーを取得すると、キーの長さがO(lk)になります。これは、ハッシュする必要があるためですが、n/k特定のハッシュテーブルに対して一定であると想定されています。nこれは通常、に依存しないため O(1) と呼ばれますが、キー サイズが固定されていない限り、厳密にはO(1) ではありません。

ただし、ハッシュ値を取得するには、事前に注文していないと仮定して、テーブル全体を繰り返し処理する必要があります (O(log(n)) のバイナリ ルックアップもサポートできるハッシュ テーブルを設計できますが、これは一般的ではありません)。 .

Answer 2

ハッシュ値は、最初の検索場所です。必要なデータがそのインデックスに格納されていない場合は、検索対象のデータが見つかるまで反復してハッシュ キーを取得します。