47

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

エントリ自体のサイズに4バイト（32ビットマシンの場合）を浪費すると思います。

しかし、なぜそれがまだ使用されているのですか？コードの保守を容易にする以外に、それを使用する理由はありますか？

4

7 に答える 7

22

実際、それはだけではありませんHashSet。 Java 6のインターフェースのすべての実装はSet、基礎となるに基づいていMapます。これは必須ではありません。それはまさに実装方法です。のさまざまな実装のドキュメントを確認することで、自分の目で確かめることができますSet。

あなたの主な質問は

しかし、なぜそれがまだ使用されているのですか？コードの保守を容易にする以外に、それを使用する理由はありますか？

コードのメンテナンスが大きな動機付けになると思います。重複や膨満感を防ぎます。

SetとMapは類似したインターフェースであり、重複する要素は許可されていません。（aに裏打ちされてSet いないMapのはCopyOnWriteArraySet、不変であるため、珍しいコレクションであると思います。）

具体的には：

のドキュメントからSet：

重複する要素を含まないコレクション。より正式には、セットには、e1.equals（e2）のような要素e1とe2のペアは含まれず、最大で1つのnull要素が含まれます。その名前が示すように、このインターフェースは数学的な集合の抽象化をモデル化します。

Setインターフェースは、Collectionインターフェースから継承されたもの以外に、すべてのコンストラクターのコントラクトとadd、equals、およびhashCodeメソッドのコントラクトに追加の規定を配置します。便宜上、他の継承されたメソッドの宣言もここに含まれています。（これらの宣言に付随する仕様は、Setインターフェースに合わせて調整されていますが、追加の規定は含まれていません。）

コンストラクターに関する追加の規定は、当然のことながら、すべてのコンストラクターは、（上記で定義されたように）重複する要素を含まないセットを作成する必要があるということです。

そしてからMap：

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

既存のコードを使用してを実装できる場合はSet、既存のコードから実現できるメリット（速度など）Setも同様に発生します。

Setバッキングなしで実装することを選択した場合はMap、要素の重複を防ぐように設計されたコードを複製する必要があります。ああ、おいしい皮肉。

とは言うものの、sを別の方法で実装することを妨げるものは何もありませんSet。

于 2010-02-10T10:04:41.723 に答える
5

私の推測では、HashSetは元々、HashMapをすばやく簡単に実行するために、HashMapの観点から実装されていたと思います。コード行に関しては、HashSetはHashMapの一部です。

それがまだ最適化されていない理由は、変化への恐れだと思います。

しかし、無駄はあなたが思っているよりはるかに悪いです。32ビットと64ビットの両方で、HashSetは必要なサイズの4倍であり、HashMapは必要なサイズの2倍です。HashMapは、キーと値を含む配列（および衝突用のチェーン）を使用して実装できます。これは、エントリごとに2つのポインタ、または64ビットVMでは16バイトを意味します。実際、HashMapにはエントリごとにEntryオブジェクトが含まれており、Entryへのポインタ用に8バイト、Entryオブジェクトヘッダー用に8バイトが追加されます。HashSetも要素ごとに32バイトを使用しますが、要素ごとに8バイトしか必要としないため、無駄は2xではなく4xです。

于 2011-05-07T16:48:37.820 に答える
4

実際のアプリケーションや重要なベンチマークにとって、これが重大な問題になることは一度もないと思います。なぜ実際の利益のためにコードを複雑にするのですか？

また、多くのJVM実装ではオブジェクトのサイズが切り上げられているため、実際にはサイズが大きくならない場合があることに注意してください（この例ではわかりません）。また、のコードHashMapはコンパイルされてキャッシュに入れられる可能性があります。他の条件が同じであれば、コードが増える=>キャッシュミスが増える=>パフォーマンスが低下します。

于 2010-02-10T09:49:04.313 に答える
3

はい、その通りです。そこには少量の無駄があります。PRESENTすべてのエントリで同じオブジェクト（finalと宣言されている）を使用するため、小さいです。したがって、無駄になるのは、HashMap内のすべてのエントリの値だけです。

ほとんどの場合、彼らは保守性と再利用性のためにこのアプローチを採用したと思います。（JCF開発者は、とにかくHashMapをテストしたので、再利用しないと考えていたでしょう。）

ただし、膨大なコレクションがあり、メモリフリークの場合は、TroveやGoogleコレクションなどのより優れた代替手段をオプトアウトすることができます。

于 2010-02-10T09:50:22.080 に答える
3

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

値がセットに存在するかどうかを知るために、ダミーインスタンスが必要です。

addメソッドを見てください

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

Abdでは、putの戻り値を見てみましょう。

@は、キーに関連付けられた以前の値を返します。キーのマッピングがなかった場合はnullを返します。（nullリターンは、マップが以前に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;

}

キーのhashCodeを2回計算するのを避けるために、4バイトを浪費していると思います（キーが追加される場合）。

HashMapたった4の同様のエントリを使用する他のデータ構造の代わりに、なぜ8バイトを浪費する（のために）を使用したのかという質問がある場合はMap.Entry、そうです、あなたが述べた理由でそれを行ったと思います。

于 2010-02-10T10:03:12.973 に答える
0

このようなページを検索した後、なぜやや非効率的な標準実装なのか疑問に思い、com.carrotsearch.hppc.IntOpenHashSetを見つけました

于 2013-09-18T19:44:31.357 に答える
-3

あなたの質問：エントリ自体のサイズに4バイト（32ビットマシンの場合）を浪費すると思います。

ハッシュセットのデータ構造全体に対して1つのオブジェクト変数が作成されるだけで、これを行うことで、hashMapの種類のコード全体を再度書き直す必要がなくなります。

private static final Object PRESENT = new Object();

すべてのキーは1つの値、つまりPRESENTオブジェクトを持っています。

于 2012-11-19T21:42:48.740 に答える