HashSet去重原理

HashSet中的元素是不重复的，那么是何如做好这点呢？下面就结合源码来看这个问题（源码基于JDK1.8）。

1、HashSet.add()方法

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

    HashSet中的数据存储在一个Map中，其提供的操作也是依赖这个map来实现的。

    add方法只是调用map的put方法来添加元素，并没有什么过滤逻辑。因此去重逻辑应该在map的put方法中。

2、HashMap.put()方法。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
//获取key的hashcode值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //map内数组判空
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //(n - 1) & hash是获取元素在数组中的索引位置，当key所在数组的位置对应的值为空，直接新建一个节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //在上一个if中，p=tab[(i-1)&hash]且p!=null
        //这里，有3个比较：1、hash值比较；2、p.key == key；3、key.equals(k)
        //当key存在时，直接取数组索引位置的元素，而不新建节点元素。
        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;
            }
        }
        //设置val
        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;
}

在上面的注释中，利用了key的hashCode值、==或equals比较，来确认key是否存在，存在，则key不放入set中，否则，放入set中。这也就是HashSet去重的原理。

示例程序：

1、hashCode一致，equals方法不一致

@Override
public boolean equals(Object o) {
    if (this == o) {
        return true;
    }
    if (o == null || getClass() != o.getClass()) {
        return false;
    }
    SetModel setModel = (SetModel) o;
    return Objects.equals(name, setModel.name);
}

@Override
public int hashCode() {
    //return Objects.hash(name);
    return 1111;
}

单测：hashCode一致，equals方法不一致，元素是不一样的。

@Test
public void test01() {
    HashSet set = new HashSet();
    set.add(new SetModel("aaa"));
    set.add(new SetModel("bbb"));
    CollectionUtils.printList(set);
}

结果：
SetModel(name=aaa)
SetModel(name=bbb)

2、hashCode与equals都一致

@Override
public boolean equals(Object o) {
    return true;
}

@Override
public int hashCode() {
    return 1111;
}

单测：hashCode与equals都一致，则元素也是相同的、

@Test
public void test01() {
    HashSet set = new HashSet();
    set.add(new SetModel("aaa"));
    set.add(new SetModel("aaa"));
    set.add(new SetModel("bbb"));
    set.add(new SetModel("bbb"));
    set.add(new SetModel("bbb"));
    set.add(new SetModel("ccc"));
    CollectionUtils.printList(set);
}

结果：
SetModel(name=aaa)

3、hashCode不一致，equals一致

@Override
public boolean equals(Object o) {
    return true;
}

@Override
public int hashCode() {
    return Objects.hash(name);
}

单测：hashCode不一致，equals一致，元素是不同的。

@Test
public void test01() {
    HashSet set = new HashSet();
    set.add(new SetModel("aaa"));
    set.add(new SetModel("aaa"));
    set.add(new SetModel("bbb"));
    set.add(new SetModel("bbb"));
    set.add(new SetModel("bbb"));
    set.add(new SetModel("ccc"));
    CollectionUtils.printList(set);
}
结果：
SetModel(name=bbb)
SetModel(name=aaa)
SetModel(name=ccc)

注释：SetModel(name=aaa)或SetModel(name=bbb)也只有一个，是因为Objects.hash(name)中，当name一样时，其hashCode值也一样。

结论：HashSet是依靠元素的hashCode值与equals方法来判断对象是否一样并去重的。