Java HashSet Implementation design

Question

Editing the question to remove my analogy and ask directly. JDK HashSet implementation is like below:

public class HashSet {
  private HashMap map;
  public HashSet(int capacity) {
    map = new HashMap(capacity);
  }

  public HashSet(int capacity, float loadFactor) {
    map = new HashMap(capacity, loadFactor);
  }

  HashSet(int capacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(capacity, loadFactor);
  }
}

And LinkedHashSet is implemented like this:

public class LinkedHashSet
  extends HashSet {
  public LinkedHashSet(int capacity) {
    super(capacity, 0, true);
  }
  public LinkedHashSet(int capacity, float loadFactor) {
    super(capacity, loadFactor, true);
  }
}

The third constructor in class HashSet : HashSet(int capacity, loadFactor, boolean dummy) exists only to help LinkedHashSet class use a LinkedHashMap as the backing map instead of default HashMap

Questions:

• Would this be considered a good design?
• Wouldn't it be better to let the subclass specify the backing map type?
• It took me 30 minutes to locate in JDK source code where exactly is the doubly linked list for LinkedHashSet because the above implementation paradigm did not intuitively occur to me, when would such a design be a good choice?

Answer 1

You are correct that this wasn't the best design choice.

to summarize:

HashSet has 3 constructors:

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * the specified initial capacity and the specified load factor.
 *
 * @param      initialCapacity   the initial capacity of the hash map
 * @param      loadFactor        the load factor of the hash map
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero, or if the load factor is nonpositive
 */
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * the specified initial capacity and default load factor (0.75).
 *
 * @param      initialCapacity   the initial capacity of the hash table
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero
 */
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

/**
 * Constructs a new, empty linked hash set.  (This package private
 * constructor is only used by LinkedHashSet.) The backing
 * HashMap instance is a LinkedHashMap with the specified initial
 * capacity and the specified load factor.
 *
 * @param      initialCapacity   the initial capacity of the hash map
 * @param      loadFactor        the load factor of the hash map
 * @param      dummy             ignored (distinguishes this
 *             constructor from other int, float constructor.)
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero, or if the load factor is nonpositive
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

The last one has an extra parameter dummy which is not used and is only there to let the compiler distinguish between the 2 constructors with the same parameters. The only difference is to change the backing map implementation.

We've gotten a lot better at Object design since these classes were written.

If this was rewritten today, there would probably a constructor that took a Map instead so that any Map implementation could be used as a backing store:

HashSet(Map<K,V> backingMap);

And/or there could be multiple static factory methods with different names but the same parameters to

 public static HashSet create(int initialCapacity, float loadFactor)

 public static HashSet createLinked(int initialCapacity, float loadFactor)

EDIT

JB Nizet brings up an interesting point. HashSet's readObject() method has explicit code when reconstructing an object from an ObjectInputStream to see if "this" the instance is of LinkedHashSet or not.

// Create backing HashMap
    map = (((HashSet<?>)this) instanceof LinkedHashSet ?
           new LinkedHashMap<E,Object>(capacity, loadFactor) :
           new HashMap<E,Object>(capacity, loadFactor));

This is only really possible because of the dummy parameter version of the constructor is package private so those are the only 2 possible implementations currently. Without this technique, you wouldn't be able to use ReadObject() correctly.

This is probably why Josh Bloch wrote the Serialization Chapter in Effective Java. You would probably have to use a SerializationProxy (Item 78) to correctly have the LinkedHashSet read correctly.