Java HashSet 实现设计

Question

编辑问题以删除我的类比并直接提问。 JDK HashSet 实现如下:

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);
  }
}

而LinkedHashSet的实现如下:

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

HashSet 类中的第三个构造函数:HashSet(intcapacity, loadFactor, boolean dummy) 的存在只是为了帮助 LinkedHashSet 类使用 LinkedHashMap 作为支持映射而不是默认的 HashMap

问题:

• 这算得上是一个好的设计吗？
• 让子类指定支持的 map 类型不是更好吗？
• 我花了30分钟才在JDK源码中定位到LinkedHashSet的双向链表到底在哪里，因为我没有直观地想到上面的实现范式，这样的设计什么时候好？选择？

Answer 1

你是对的，这不是最好的设计选择。

总结一下:

HashSet 有 3 个构造函数:

/**
 * 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);
}

最后一个有一个额外的参数虚拟，它没有被使用，只是让编译器区分两个具有相同参数的构造函数。唯一的区别是更改支持 map 实现。

自从编写这些类以来，我们在对象设计方面取得了很大进步。

如果今天重写，可能会有一个构造函数采用 Map 来代替，以便任何 Map 实现都可以用作后备存储:

HashSet(Map<K,V> backingMap);

和/或可能有多个名称不同但参数相同的静态工厂方法

 public static HashSet create(int initialCapacity, float loadFactor)

 public static HashSet createLinked(int initialCapacity, float loadFactor)

编辑

JB Nizet 提出了一个有趣的观点。当从 ObjectInputStream 重建对象以查看“this”实例是否属于 LinkedHashSet 时，HashSet 的 readObject() 方法具有显式代码。

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

这实际上是可能的，因为构造函数的虚拟参数版本是包私有(private)的，因此这是当前仅有的两种可能的实现。如果没有这种技术，您将无法正确使用 ReadObject()。

这可能就是 Josh Bloch 在《Effective Java》中撰写序列化章节的原因。您可能必须使用 SerializationProxy(第 78 项)才能正确读取 LinkedHashSet。