HashSet源码剖析

//源码中的
public interface Set<E> extends Collection<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean retainAll(Collection<?> c);
    boolean removeAll(Collection<?> c);
    void clear();
    boolean equals(Object o);
    int hashCode();
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT);
    }
}

//源码，hashSet的构造器
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);
}

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

// Dummy value to associate with an Object in the backing Map【要与后备映射中的对象关联的虚拟值】
private static final Object PRESENT = new Object();

/**
计算 key.hashCode（） 并将较高的哈希位传播 （XOR） 到较低的哈希位。由于该表使用二次方掩码，因此仅在当前掩码上方的位数上变化的哈希集将始终发生冲突。（已知的例子包括一组 Float 键，在小表中保存连续的整数。因此，我们应用了一个转换，将更高位的影响向下分散。在速度、效用和位传播质量之间需要权衡。因为许多常见的哈希集已经合理分布（所以不会从传播中受益），并且因为我们使用树来处理箱中的大量碰撞，所以我们只是以最便宜的方式对一些移位进行 XOR 以减少系统损失，并合并最高位的影响，否则由于表边界，这些位永远不会在索引计算中使用。
*/
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//实现Map.put（）的相关方法
/*
实现 Map.put 和相关方法。
形参:
哈希 – 键的哈希
密钥 – 密钥
值 – 要放置的值
onlyIfAbsent – 如果为 true，则不更改现有值
逐出 – 如果为 false，则表处于创建模式。
返回值:
上一个值，如果没有，则为 null
*/


public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    //定义的辅助变量
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //table就是hashMap的一个数组， 类型是Node[]
    //resize() : 重置数组大小，首次扩容到16个空间
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    //1. 根据key得到的hash值 ，去计算该key应该存放到table表的哪个索引位置。并把这个位置的对象赋给p
    //2. 判断这个p是否等于null ， 如果是null，就创建一个Node	
    //然后放在tab[i]的位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样&&
        //并且满足 准备加入的key 和 p指向的Node接待你的key是同一个对象 或者 不是同一个对象，但是内容相同
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //判断是否是一颗红黑树，如果是 那么就调用红黑树的putVal来进行添加
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //如果table对应的索引位置已经是一个链表，那么就使用for循环进行比较，如果最后都不同，那么就加入到链表的最后
        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;
}

//源码
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

//通过上面的调用得到该方法【hashMap中的方法】
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 && // always check first node
            ((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;
}

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}
//默认初始range为16
public LinkedHashSet() {
    super(16, .75f, true);
}

public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}