YSMull
<-- home

HashSet 源码分析

HashSet 构造

private transient HashMap<E,Object> map;

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

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

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

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.
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

可以看到 HashSet 包裹了一个 HashMap,这里的 PRESENT 是一个空的对象,作为这个 HashMap 的 Value。注意到,HashMap 的默认初始容量为 16,默认负载因子为 0.75。

HashSet#add 调用链分析

//1.HashSet#add()
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
//HashMap#hash
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//2.HashMap#put
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
//3.HashMap#putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

调用链为:

  1. HashSet#add
  2. HashMap#put ( –> 使用到 HashMap#hash –> 使用到 Object#hashCode)
  3. HashMap#putVal ( –> 使用到了 Object#equals)

HashSet#equals 调用链分析

//1.AbstractSet#equals
public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof Set))
        return false;
    Collection<?> c = (Collection<?>) o;
    if (c.size() != size())
        return false;
    try {
        return containsAll(c);
    } catch (ClassCastException unused)   {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }
}
//2.AbstractCollection#containsAll
public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}
//3.HashSet#contains
public boolean contains(Object o) {
    return map.containsKey(o);
}
//4.HashMap#containsKey
public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}
//5.HashMap#getNode
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

上面依次调用了:

  1. AbstractSet#equals
  2. AbstractCollection#containsAll
  3. HashSet#contains
  4. HashMap#containsKey ( –> 使用到 HashMap#hash –> 使用到 Object#hashCode)
  5. HashMap#getNode ( –> 使用到了 Object#equals)

由于 HashSet 其实是把 element 存储在 HashMap 的 key 上,HashMap#getNode 根据 key 来找结点,如果不为 null,则证明 HashMap 包含这个元素,也就是 HashSet 包含这个元素。所以对两个 HashMap 进行 equals 操作时,被包装类型必须重写 equals()hashCode() 方法,否则会导致
HashSet#contains 判断失效。

HashSet#remove 调用链分析

//1.HashSet#remove
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}
//2.HashMap#remove
/**
 * Removes the mapping for the specified key from this map if present.
 *
 * @param  key key whose mapping is to be removed from the map
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
//3.HashMap#removeNode
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

调用依次为:

  1. HashSet#remove
  2. HashMap#remove
  3. HashMap#removeNode

看上面 HashMap#remove 的注释说的:
“调用这个方法会删除键值为 key 的元素并且返回该 key 的 value。如果返回 null 代表不存在这个 key”。然而马上括号里面又说返回 null也有可能是这个 key 对应的 value 就是 null。这说明 HashMap 的 value 是可以为 null 的。(其实 key 也可以为 null

总结

1.现在回过头来看《阿里巴巴 Java 开发手册》编程规约的集合处理部分第一条:

1.【强制】关于 hashCode 和 equals 的处理,遵循如下规则:

1) 只要重写equals,就必须重写hashCode。

2) 因为Set存储的是不重复的对象,依据hashCode和equals进行判断,所以Set存储的 对象必须重写这两个方法。

3) 如果自定义对象做为Map的键,那么必须重写hashCode和equals。

说明:String 重写了 hashCode 和 equals 方法,所以我们可以非常愉快地使用 String 对象 作为 key 来使用。

2.你会发现 HashMap#putVal 方法里面怎么有 putTreeVal()treeifyBin() 这样的带 tree 字眼的方法。这其实是 Java8 相对 Java7 的升级,对于 HashMap、LinkedHashMap、ConcurrentHashMap 中存在大量冲突的位置,将用一颗平衡二叉树取代链表,可以看到代码里面定义了一些常量和操作:

常量 操作
TREEIFY_THRESHOLD=8 HashMap#treeifyBin
UNTREEIFY_THRESHOLD=6 TreeNode#untreeify
MIN_TREEIFY_CAPACITY=64 HashMap#resize

详见:

3.这一版本同时去掉了 JDK7 对 HashMap 增加的一个hash function,设置 jdk.map.althashing.threshold 后,当 Map 的 size 超过这个设置的值,对于 key 类型为 String 的 Map,将会采用一个特别设计的 hash function,默认不启用。
需要重点提醒的是,不论是 JDK7 采用 alternative hash function 或者是 JDK8 把 Map 的链表优化成平衡树,均可能导致某些情况下遍历其元素的顺序产生变化。因此我们的代码 不应该依赖于对Map遍历的顺序