HashSet的反复值判定逻辑

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()判定。这可能会出现你不想看到的结果。

查看更多 下一篇