Set的非重复判断是根据什么判断的

HashSet

首先来看下HashSet的add()这个方法的源代码：

public boolean add(E e) {

    return map.put(e, PRESENT)==null;

    }

由此可知HashSet的值是存储在一个Map的key里面的，而正好Map的key是不能重复的，以下是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<E,Object>();

    }

 public Iterator<E> iterator() {

    return map.keySet().iterator();

    }

public int size() {

    return map.size();

    }

接着再看看HashMap里的put()方法是如何判断值是否重复的，以下是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;

    }

关键这句：if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

它先进行了hashCode的判断，如果hashCode相等再接着使用==来判断传入的对象的引用地址是否相等及使用传入对象的equals()方法来进行判断。

接着再看看HashSet的contains()方法的源码：

public boolean contains(Object o) {

    return map.containsKey(o);

    }

调用的是Map的containsKey()方法，以下是HashMap的containsKey()源码：

public boolean containsKey(Object key) {

        return getEntry(key) != null;

    }

final Entry<K,V> getEntry(Object key) {

        int hash = (key == null) ? 0 : hash(key.hashCode());

        for (Entry<K,V> e = table[indexFor(hash, table.length)];

             e != null;

             e = e.next) {

            Object k;

            if (e.hash == hash &&

                ((k = e.key) == key || (key != null && key.equals(k))))

                return e;

        }

        return null;

    }

if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) 和put()方法的判断是一样的。

TreeSet
看看TreeSet的add()方法的源码：

public boolean add(E e) {

    return m.put(e, PRESENT)==null;

    }

它也同样是由一个Map的key来进行存储，看看这个Map:

/**

     * The backing map.

     */

    private transient NavigableMap<E,Object> m;

接着看看TreeSet的构造函数：

TreeSet(NavigableMap<E,Object> m) {

        this.m = m;

    }

public TreeSet() {

    this(new TreeMap<E,Object>());

    }

TreeSet的无參构造函数里实例化了一个TreeMap对象，下面看看这个TreeMap对象：

public class TreeMap<K,V>

    extends AbstractMap<K,V>

    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

{

 private final Comparator<? super K> comparator;

 public TreeMap() {

        comparator = null;

    }

public TreeMap(Comparator<? super K> comparator) {

        this.comparator = comparator;

    }

//其他略...

}

public interface NavigableMap<K,V> extends SortedMap<K,V>

接着看这个TreeMap的put()方法：

public V put(K key, V value) {

        Entry<K,V> t = root;

        if (t == null) {

        // TBD:

        // 5045147: (coll) Adding null to an empty TreeSet should

        // throw NullPointerException

        //

        // compare(key, key); // type check

            root = new Entry<K,V>(key, value, null);

            size = 1;

            modCount++;

            return null;

        }

        int cmp;

        Entry<K,V> parent;

        // split comparator and comparable paths

        Comparator<? super K> cpr = comparator;

        if (cpr != null) {

            do {

                parent = t;

                cmp = cpr.compare(key, t.key);

                if (cmp < 0)

                    t = t.left;

                else if (cmp > 0)

                    t = t.right;

                else

                    return t.setValue(value);

            } while (t != null);

        }

        else {

            if (key == null)

                throw new NullPointerException();

            Comparable<? super K> k = (Comparable<? super K>) key;

            do {

                parent = t;

                cmp = k.compareTo(t.key);

                if (cmp < 0)

                    t = t.left;

                else if (cmp > 0)

                    t = t.right;

                else

                    return t.setValue(value);

            } while (t != null);

        }

        Entry<K,V> e = new Entry<K,V>(key, value, parent);

        if (cmp < 0)

            parent.left = e;

        else

            parent.right = e;

        fixAfterInsertion(e);

        size++;

        modCount++;

        return null;

    }

TreeMap存储的对象是会进行排序的，所以存储的对象都必须实现Comparable接口。

TreeMap先判断Comparator对象是否为空，不为空则使用当前的Comparator对象的compare方法来进行比较排序，若发现compareTo返回的值为0，则认为这两个对象是重复的了，然后覆盖原来的value；如果Comparator对象为空，则使用集合对象实现的Comparable接口的compareTo方法来进行比较排序，同样地当返回值是0时就认为对象重复，然后覆盖原来的value。

巴特西

Set的非重复判断是根据什么判断的

最新文章

热门文章