HashSet中是如何判断元素是否重复的

HashSet不能添加重复的元素，当调用add（Object）方法时候，

首先会调用Object的hashCode方法判断hashCode是否已经存在，

• 如不存在则直接插入元素；
• 如果已存在则调用Object对象的equals方法判断是否返回true，

• 如果为true则说明元素已经存在
• 如为false则插入元素。

Created with Raphaël 2.1.0

add(Object)

hashCode 是否存在

equals 是否相等

结束

查看了JDK源码，发现HashSet竟然是借助HashMap来实现的，利用HashMap中Key的唯一性，来保证HashSet中不出现重复值。具体参见代码：

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, Serializable

    private transient HashMap<E,Object> map; // hashmap

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<E,Object>();
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    public boolean add(E e) {
        return map.put(e, PRESENT) == null; // hashset中的元素就是hashmap中的key :-)      

由此可见，HashSet中的元素实际上是作为HashMap中的Key存放在HashMap中的。下面是HashMap类中的put方法：

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);

    int hash = hash(key.hashCode()); // 计算hash值
    int i = indexFor(hash, table.length); // 根据hash值，找到对应的索引

    // 遍历链表中每个结点
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 如果hash值相等，并且== or equals也相等，
        // 那么就用新值覆盖老值
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue; // 然后返回老值（不能是null）