java - Set インターフェイスはどのようにして非重複を保証しますか

Question

今日、インタビュアーは私に尋ねました: Set はどのように非重複を保証しますか?

Answer 1

答えは、addメソッドのソース コードにあります。たとえばTreeSet、add メソッドのソース コードでは、次のように実装されています。

public boolean add(E e) 
{
    return m.put(e, PRESENT)==null;
}

ここで、PRESENTはObjectクラスのオブジェクトです。そしてmの対象ですNavigableMap。これは、要素を指定 されたキーとしてNavigableMap m格納するために使用されます。したがって、すべてのキーのオブジェクトは同じです。Oracle doc内で定義されている方法は次のとおりです。ekeyPRESENTvalueemPRESENTputMap

指定された値をこのマップ内の指定されたキーに関連付けます。マップに以前にキーのマッピングが含まれていた場合、古い値が置き換えられます。
...
...
戻り値: key に関連付けられた以前の値、またはkeyのマッピングがなかった場合は null。(null 戻り値は、マップが以前に null をキーに関連付けていたことを示す場合もあります。)

したがって、 set 内に重複する要素を配置すると、この要素はNavigableMapas key with valueに配置されますPRESENT。このキーが存在しなかった場合NavigableMap、putメソッドは戻りnull、したがって m.put(e,PRESENT)==nulltrue を返し、要素が追加されたことがわかります。そして、キーがすでに存在する場合NavigableMap、メソッドはforをPRESENT でputオーバーライドし、古い値 (PRESENT) を返すため、 戻り、要素が追加されていないことがわかります。valuekey eNavigableMapm.put(e,PRESENT)==nullfalse

Answer 2

Set は、さまざまな方法で実装できる抽象データ型です。それ自体がコントラクトの仕様です。そのため、何も保証しません。コントラクトが満たされることを保証するのは、インターフェイスの実装次第です。

したがって、実装がどのように、なぜ機能するのかを調べることはより興味深いことです。いくつかの一般的な実装は次のとおりです。

• Java で実装されているハッシュ テーブルHashSet
• Javaで実装されたバランスの取れたツリーTreeSet
• EnumSetおよびによって Java に実装されているビット セット (特殊な型の場合)BitSet
• によって実装されたスキップリストConcurrentSkipListSet
• 単純な配列: 要素を追加する前に配列をスキャンします。頻繁には使用されません。としてJavaで実装CopyOnWriteArraySet

就職の面接では、上記のように答え、実装の詳細を説明することを申し出るでしょう。面接担当者はすでにこれらのいくつかを知っているはずであり、尋ねられない限り、それらについてとりとめのないことを始めることはあなたの利益にはなりませんでした.

Answer 3

仕様の観点からは、たとえばadd、複製を追加しようとした場合にメソッドが何をしなければならないかを指定することによってそれを実現します。メソッドのドキュメントには、addたとえば次のように記載されています。

指定された要素がまだ存在しない場合は、このセットに追加します (オプションの操作)。より正式には、(e==null ? e2==null : e.equals(e2)) となる要素 e2 がセットに含まれていない場合、指定された要素 e をこのセットに追加します。このセットにすでに要素が含まれている場合、呼び出しはセットを変更せずに false を返します。コンストラクターの制限と組み合わせることで、セットに重複する要素が決して含まれないようになります。

同じページから ( http://docs.oracle.com/javase/6/docs/api/java/util/Set.html ):

コンストラクターに関する追加の規定は、驚くことではありませんが、すべてのコンストラクターは重複する要素を含まないセットを作成する必要があるということです (上記で定義されているように)。

(完全を期すために、セットの抽象化を適切にモデル化することを保証するequalsおよびに関する規定もあります。)hashCodeSet