プログラミングとデータ構造

Question

1からnまでの整数のサブセットSを表すためのデータ構造を提案する。集合Sに対する以下の演算は、一定時間（Sの基数に依存しない）で実行される。 データ構造が適切に初期化されていると仮定できます。

（i）。 MEMBER（X）：Xが集合Sか

（II）であるかどうかを

チェック。 FIND-ONE（S）：Sが空でない場合、集合Sの1つの要素（任意の要素が行います）

（iii）を返します。 ADD（X）：整数Xを加算してSを設定する。

（iv）。 （X）：Sから整数Xを削除してください。

私の分析： - ハッシュテーブルはここでうまくいくと思いますが、ハッシュテーブルはFIND-ONES（S）操作でどのように動作するのでしょうか？スキャンする必要があるので全体は現在の要素を探すためのテーブルを持っています。

Answer 1

ハッシュテーブルは機能しますが、具体的な実装について考える必要があります。 compact version from Python 3.6を使用している場合は、リストを調べて、一定時間内にFIND-ONEsを実行できます。例えば

、辞書：次のように

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'} 

が示されている：あなたはJavaで、このために定期的にHashSetのを使用することができます

indices = [None, 1, None, None, None, 0, None, 2] 
entries = [[-9092791511155847987, 'timmy', 'red'], 
      [-8522787127447073495, 'barry', 'green'], 
      [-6480567542315338377, 'guido', 'blue']] 

Answer 2

。 FIND-ONE(S)の場合は、isEmpty()に電話してください。それがfalseを返す場合は、組み込みイテレータを使用し、イテレータが返す最初の値を取得します。