概要

JJUG CCC 2015 Fall の Eclipse Collections のセッション (発表資料)で「Java の HashSet はメモリ効率が悪い」というお話がありました。ふと思い出して、少し調べてみたら実装が興味深かったので、書いてみます。

java.util.HashSet

要素の重複を許可しない Collection 、Set の実装の1つ
値は hashCode により一意で保持される……独自に定義した Class のオブジェクトは hashCode を実装しないと意図しない動作をする

閑話：hashSet() の簡単な実装

ちゃんとやろうとすると面倒ですが、 HashCodeBuilder を使えば簡単に実装できます。

import org.apache.commons.lang3.builder.HashCodeBuilder;

……

@Override
public int hashSet() {
    return HashCodeBuilder.reflectionHashCode(this, true);
}

衝撃！？ HashSet は Map だった！？

何を言っているのかわからないと思いますので、 GrepCode から一部ソースを転載していきます。

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;

おや、なぜ Set の中に Map のオブジェクトがあるのでしょうね？もうちょっと見ていきますか。

謎のDummyObject

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

ふむ

HashSet()

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }

!!!????!?!??!??!??!?!??

HashSet#add()

    /**
     * Adds the specified element to this set if it is not already present.
     * More formally, adds the specified element <tt>e</tt> to this set if
     * this set contains no element <tt>e2</tt> such that
     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
     * If this set already contains the element, the call leaves the set
     * unchanged and returns <tt>false</tt>.
     *
     * @param e element to be added to this set
     * @return <tt>true</tt> if this set did not already contain the specified
     * element
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

キーに Set の要素、値に空のオブジェクトを突っ込んでいる！？

どういうことか？

要するに、HashSet は HashMap の Key だけを使う、という実装になっているようです。

何が問題なのか？

「あるものを使って実装しているだけじゃない」「『エンジニアは怠惰であれ』っていうでしょ」ええ、そうですね。おっしゃる通りです。

結論：メモリが無駄

Map の value に使いもしない空のオブジェクトを突っ込んでいる
Map は key-value のペア集合だけでなく、EntrySet を内部的に持つ。この実装で使われることはあるか？

なぜこのような実装になったのか、経緯をご存知の方がいらっしゃいましたらご教示くださいますと幸甚です。

では、どうするか？

メモリ効率が気になるなら Eclipse Collections の Set 実装を使いましょう。

Set<String> strs = Sets.mutable.of("Alice", "Bob", "Charlie");