HashSet的add()源码分析

2019-05-22 本文已影响0人御都

【总结：】
1、HashCode中的add()底层是由HashMap来实现的；
2 、add()方法同hashCode()和equals()强相关：
2个元素如果hashCode()值相同且equals()比较的返回值为true则被认定为重复元素，不进行添加
2个元素如果hashCode()值相同，equals()比较返回false,可以添加
2个元素如果hashCode()值不同，则被认定为非重复元素，可以进行添加
3 String类中重写了hashCode()和equals()，内容相同的2个字符串hashCode()相同和equals()为true
可以做到看字面值就能判断是否能添加进HashSet集合。
4 没有重写hash()和equals()的类，和Object保持一致
5 如果类中重写了hash()和equals()，具体问题再具体分析
【简略代码】

interface Collection{
...
}
interface Set extends Collection{
...
}
class HashSet<E> implements Set<E>{
    private static final Object PRESENT = new Object();
    private transient HashMap<E,Object> map;
    //无参构造方法，生成一个HashMap对象
    public HashSet() {
    map = new HashMap<E,Object>();
    }
    public boolean add(E e) {
    //返回值类型为PRESENT对象所对应的类，即Object
    return map.put(e, PRESENT)==null;
    }
}
class HashMap<K,V> implements Map<K,V>{
    transient Entry[] table;//哈希表
    
     public V put(K key, V value) {
        // key为空不指向任何对象时，直接返回value
        if (key == null)
            return putForNullKey(value);
        //计算元素的hashCode值
        int hash = hash(key.hashCode());
        //通过元素的hashCode值，得到该元素在哈希表中的索引，如果哈希表中不存在
        //该元素，返回的应该是一个负数(i<0)，执行不了接下来的for循环
        int i = indexFor(hash, table.length);
        //查找到元素在哈希表中的索引i(i>=0）
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //哈希值相同的前提下，地址值相同或者equals相同才执行不添加
            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;
    }
    
    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }
}

【HashSet的存放--哈希表】
1 通过源码可以看到HashSet集合底层调用的是HashMap实现的元素的添加，也就是说元素是存放在哈希表中的。
2 哈希表是一个元素为链表的数组，结合了数组和链表2种数据结构的优点，在这里链表称为桶结构。
3 存放特点：

3.1 当2个元素的hashCode()值相同时，存放在哈希表相同脚标的数组中，即放在同一个链表中。
3.2 当2个元素的hashCode()值不同时，存放在哈希表不同脚标的数组中。

image.png

4 链表这种数据结构的特点是增删快，查找慢。当一个链表中存放很多个集合元素，它查找的效率就会更慢了。所以最好在链表中只存放少数几个元素，查找的效率才高。这就要求各个元素对象的hashCode()尽量不一样。
5 如何做到元素对象的hashCode()值尽量不同呢？

5.1 重写元素对象对应类的hashCode()方法，使得该方法的返回值和成员属性强相关。如果是基本类型就直接加该值，如果是引用类型就直接加该值的hashCode()
可以通过快捷键自动生成重写的hashCode()方法。比如Student类中有2个属性int age和String name，可以自动生成如下代码

public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

HashSet的add()源码分析

猜你喜欢

热点阅读