なぜ日JavaでHashSetの実装は、HashMapのは、そのバッキングとして使用していますか？

StackOverflow https://stackoverflow.com/questions/2235546

  •  19-09-2019
  •  | 
  •  

質問

のJava 6のソースを見ると、HashSet<E>は、実際に設定のすべてのエントリにダミーのオブジェクトインスタンスを使用して、HashMap<E,Object>を使用して実装されます。

と思い、そのエントリ自体のサイズのために廃棄物4バイト（32ビットマシン上で）。

しかし、なぜそれはまだ使用されていますか？それが簡単にコードを維持することのほかに、それを使用する理由はありますか？

役に立ちましたか？

解決

実際には、それだけでHashSetではありません。 のJava 6の中Setインターフェイスのすべてのの実装では、基礎となるMapに基づいています。これは必須ではありません。それだけで実装がある方法です。あなたは<のhref =「http://java.sun.com/javase/6/docs/api/java/util/Set.html」のrel = "noreferrerの様々な実装のドキュメントをチェックアウトすることによって自分自身のために見ることができます"タイトル=" 設定 "> Set でます。

あなたの主な質問がある

  

しかし、なぜそれはまだ使用されていますか？ある   それを作る以外にも、それを使用する理由   コードを維持しやすい？

私は、コードの保守が大きな動機要因であることを前提としています。だから、重複や肥大化を防止されます。

SetとMap要素が許可されない二重に、同様のインタフェースです。

（私はそれが不変だからだけSetはののMapに裏打ちされていない、珍しいコレクションでCopyOnWriteArraySet、である。だと思います）

具体

の

ドキュメントSetするます：

  

なしを含むコレクション   要素を複製します。より正式に、   セットは要素のないペアを含まないE1   そしてE2例えばe1.equals（E2）とでその   多くても1つのヌル要素。によって示唆されるように   その名は、このインタフェースは、モデル   数学的な集合の抽象化ます。

     

Setインタフェースを追加配置します   継承されたもの以外の規定、   Collectionインタフェースから、上   上のすべてのコンストラクタとの契約   アドオンの契約は、等しく、   hashCodeメソッド。以下のための宣言   他の継承された方法もあります   便宜のためにここに含まれています。 （   これらに伴う仕様   宣言はに調整されています   インターフェイスを設定し、彼らは含まれていません。   任意の追加の規定。）

     

追加の規定に   コンストラクタは驚くことではないが、あります、   すべてのコンストラクタは、作成しなければならないこと   重複を含まない集合   要素（上記で定義した通り）。

と Map <から/>

  

キーを値にマッピングするオブジェクト。   マップは重複したキーを含めることはできません。各キーは1つの値にマッピングすることができます。

既存のコードを使用してSetsを実装することができた場合は、

は、既存のコードから実現することができます任意の利益（例えば速度が）同様にあなたのSetに計上ます。

あなたはSet裏地なしMapを実装することを選択した場合は、

、あなたは重複要素を防ぐために設計されたコードを複製する必要があります。ああ、おいしい皮肉ます。

違ったあなたSetsを実装するからあなたを妨げるものは何もありません、言った。

他のヒント

私はそれが実際のアプリケーションや重要なベンチマークのための重要な問題として上がったことはないことを推測しています。なぜ本当の利益のためにコードを複雑に？

また、そのオブジェクトのサイズは、多くのJVM実装で切り上げされているため、実際のサイズの増加（私はこの例ではわかりません）がないことが、注意してください。またHashMapのためのコードがコンパイルされる可能性が高いとキャッシュです。他の物事が等しい場合、より多くのコード=>複数のキャッシュ・ミス=>低性能ます。

私の推測では、HashSetのは、もともとそれが迅速かつ容易に成し遂げるためにはHashMapの観点で実施されたということです。コードの行の点で、HashSetのは、ハッシュマップの一部である。

私はそれはまだ最適化されていない理由は、変更の恐れであることを推測ます。

しかし、廃棄物はあなたが考えているよりもはるかに悪いです。 32ビットと64ビットの両方で、HashSetのは、必要以上に大きく4倍され、HashMapのは、必要以上に大きく2倍されます。 HashMapのは、キーと値その中の（プラス衝突の鎖）を有するアレイを用いて実現することができます。すなわち、エントリ当たり2つのポインタ、または64ビットVM上の16のバイトを意味します。実際には、HashMapのエントリへのポインタのための8バイト、エントリオブジェクトヘッダの8つのバイトを追加エントリごとエントリオブジェクトを含んでいます。 HashSetのは、要素ごとに32バイトを使用するが、それは唯一の要素ごとに8つのバイトを必要とするため、廃棄物ではなく、2倍の4倍である。

私はあなたの質問を見て、それはあなたが言ったことを考えるように私にしばらく時間がかかりました。だからここHashSetの実施に関する私の意見です。

値であるか、またはセットに存在しないかどうかを知るためにダミーのインスタンスを有することが必要である。

addメソッドを見てみましょう。

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

アブドは、今のは、プットの戻り値を見てみましょう。

  

は、キーのマッピングがなかった場合、キー、またはnullに関連付けられた以前の値を@returns。 （nullの戻りは、マップが以前にキーとヌル関連することを示すことができる。）

PRESENTオブジェクトがちょうどセットはE値が含まれていることを表すために使用されるように。私はnullの代わりPRESENTを使用しない理由を尋ねたと思います。 map.put(key,value)は常にnullを返しますし、あなたはキーが存在していたかどうかを知る方法を持っていないので、エントリが地図上以前だった場合しかし、あなたは区別することができません。

<時間>

あなたは、彼らがこのような実装を使用していることができると主張している可能性が言われていること。

   public boolean add(E e) {

        if( map.containsKey(e) ) {
            return false;
        }

        map.put(e, null);

        return true;

}

私は、彼らが（キーが追加されようとしている場合）、それはキーを2回で、高価になる可能性があるので、ハッシュコードを計算避けるために4つのバイトを無駄に推測します。

<時間> 代わりに、わずか4のようなエントリを使用して、いくつかの他のデータ構造の

あなたは、彼らが（理由HashMapの）8つのバイトを無駄にMap.Entryを使用する理由と呼ば疑問がある場合は、[はい、私は彼らが理由のためにそれをやったと言うでしょうあなたは言及しています。

なぜ、穏やかな非効率的な標準の実装を迷って、このようなページを検索した後、見つかったcom.carrotsearch.hppc.IntOpenHashSet

あなたの質問： 私は、エントリ自体の大きさのために廃棄物（32ビットマシン上の）4バイトだと思います。

ちょうど1オブジェクト変数は、HashSetの全体のデータ構造のために作成され、それを行うことは、再び、コードの再書き込み全体のHashMapの種類から自分を救うます。

private static final Object PRESENT = new Object();

すべてのキーが1つの値すなわちPRESENTオブジェクトを持っています。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top