ハッシュテーブルシーケンスが常に挿入される

Question

ハッシュテーブルに関連する問題があります。

オープンリニアスキーマのディメンション2^nのハッシュテーブルを考えてみましょう。

1. h(k,i) = (k^n + 2*i)mod(2^n)。シーケンス {1,2,...2^n}が常にハッシュテーブルに挿入できることを示します。

数字がテーブルに挿入される方法でパターンを特定してから、私が質問を証明できるかどうかを確認するために誘導を適用しようとしました。教師が私たちに与えた問題は、私はこれらの問題を解決する方法を理解することはできません。

Answer 1

h(k,i) = (k^n + 2*i)mod(2^n)。シーケンス{1,2,...2^n}は常にハッシュテーブルに挿入できることを示します。ハッシュ関数について

2つの観測：

k^n

、 kが奇数の場合、および kも毎秒バケツを検証します

• 2*i場合でもn >= 1のために、奇数になります（最後から最初に折り返す）

したがって、ハッシュ{1,2,...2^n}を使用すると、使用されていない奇数インデックス付きバケットと偶数インデックス付きバケットの検索が交互に行われます。

k^nビットは、奇数キーを奇数インデックスのバケットに、偶数キーを偶数インデックスのバケットに制限します。2*iは、空きキーが見つかるまでこれらのバケットをすべて考慮します。iがインクリメントされているため、h(k,i)が未使用のバケットを見つけられずにテーブルがいっぱいになっても、キーのちょうど半分が奇数となり、半分になる必要があります。

Answer 2

ここでは、多くの用語の問題があります。

1. あなたのハッシュテーブルはdimensionsを持っていません（実際には持っているが、それは一次元ではなく、2^nが）、それは、スロット/バケットの数を持っています。
2. ほとんどの場合、質問した質問は、あなたの本/教師があなたが解決したいと思う質問ではありません。あなたは言う：

が

シーケンス{1,2、... 2^nは}常に ハッシュテーブルに挿入することができることを示して、問題があなたのケースであること任意の自然数をハッシュテーブルに挿入できます。あなたのハッシュ関数は任意の数を[0から2^n]までの範囲の自然数にマップし、ハッシュ関数は2^nのスロットを持つので、任意の数があなたのハッシュに収まるため、これは明らかです。

---

あなたの先生が望むものを明確にして、あなたのハッシュ関数でkとiが何であるかを説明し、別のより良い準備された質問をしてください。