2

私は次のインタビュー質問をされました：

通常のインターフェースを提供するHashSet実装があるとします。HashSetの1つ以上のインスタンスを使用して、通常のHashTableインターフェイスに通常の時間制約を提供するHashTableを実装するにはどうすればよいですか？

私は2回質問しましたが、その意味はこの方法であり、その逆ではありません（HashTableを使用したHashSetの実装は非常に簡単です。たとえば、Javaがこれを行います）。

不可能だと答えました。この回答はインタビュアーを統計化していないようだったので、私はより良い回答を探しています。インターネットやStackOverflowで検索しても、解決策が見つかりませんでした。

トリックの質問だったと思いますが、念のため、この質問をSOに投稿します。

4

1 に答える 1

5

これを行うための標準的な方法の1つは、ハッシュテーブルをキー/値ペアのハッシュセットとして扱うことです。ここで、キー/値ペアのハッシュコードは純粋にキーのハッシュコードであり、等式比較関数は任意の2つのキーを示します。 / valueペアは、キーが等しい場合に正確に等しくなります。このように、通常のハッシュセット操作では、キーと値のペアが次のように格納されます。

  • 同じキーを持つ2つのキー/値のペアは保存されず、
  • ハッシュテーブルでキーを検索すると、そのキーを持つキーと値のペアオブジェクトが見つかり、そこから値を検索できます。

お役に立てれば！

于 2012-06-08T16:35:15.660 に答える