HashSet的重复值判定逻辑

HashSet是Set接口的一个具体实现类之一，它内部采用哈希算法，专门为快速查找而设计，它不允许插入重复的值，需要注意的问题是，存入HashSet的对象必须定义hashCode和equals方法。

下面我们来谈谈HashSet如何判定两个对象是否重复。
HashSet内部使用HashMap来保存对象，将需要存入的对象比如T a，以key的形式存入HashMap中，这可以从代码中看到:

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

首先，说下HashMap内部是使用数组进行存储的，数组里存放的是HashMap的内部类Entry，它是一个自引用的类，支持链表结构，用于对哈希冲突的情况下保存多个对象。

    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }
        .........//略去大段代码
    }

然后我们在HashMap的put方法中可以看到它是如何进行重复性判断的：

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

首先，可以通过key的hashCode，经过hash()函数的处理，得出一个i，这是这个对象应该存放的位置，然后去数组中查找第一个Entry，如何Entry不存在，直接进行添加操作；如果发现存在Entry，便对其进行遍历，使用条件(k = e.key) == key || key.equals(k)进行判断，如果为true，说明已经存在，便对其进行重新设置，但是因为hashSet使用的其实是key，value对其是没任何用处的。所以相当于没有任何改变。

这也就是我们为什么在使用HashSet存储自定义类时，需要重写hashCode()和equals()方法的原因，否则使用Object对象默认的hashCode()和equals方法，Object的hashCode()使用对象的地址计算散列码，使用内存地址进行equals()判定。这可能会出现你不想看到的结果。