简述HashSet的元素唯一机制

2019-12-11

字数统计: 1.2k字 | 阅读时长≈ 5分

HashSet简介

HashSet实现Set接口，底层由HashMap来实现，为哈希表结构，新增元素相当于HashMap的key，value默认为一个固定的Object。
当有元素插入的时候，会计算元素的hashCode值，将元素插入到哈希表对应的位置中来；
它继承于AbstractSet，实现了Set, Cloneable, Serializable接口。
(1)HashSet继承AbstractSet类，获得了Set接口大部分的实现，减少了实现此接口所需的工作，实际上是又继承了AbstractCollection类；
(2)HashSet实现了Set接口，获取Set接口的方法，可以自定义具体实现，也可以继承AbstractSet类中的实现；

(3)HashSet实现Cloneable，得到了clone()方法，可以实现克隆功能；
(4)HashSet实现Serializable，表示可以被序列化。
具有如下特点：

不允许出现重复因素；
允许插入Null值；
元素无序（添加顺序和遍历顺序不一致）；
线程不安全，若2个线程同时操作HashSet，必须通过代码实现同步；
HashSet基本操作
HashSet底层由HashMap实现，插入的元素被当做是HashMap的key，根据hashCode值来确定集合中的位置，由于Set集合中并没有角标的概念，所以并没有像List一样提供get（）方法。当获取HashSet中某个元素时，只能通过遍历集合的方式进行equals()比较来实现；
HashSet元素添加分析
Set集合不允许添加重复元素，实际上是调用了HashMap中的put方法。
简单事例：

public class HashSetTest {

    public static void main(String[] agrs){
        //hashCode() 和 equals()测试：
        hashCodeAndEquals();
    }
    public static void hashCodeAndEquals(){
        //第一个 Set集合：
        Set<String> set1 = new HashSet<String>();
        String str1 = new String("huangqiuping");
        String str2 = new String("huangqiuping");
        set1.add(str1);
        set1.add(str2);
        System.out.println("长度："+set1.size()+",内容为："+set1);

        //第二个 Set集合：
        Set<App> set2 = new HashSet<App>();
        App app1 = new App();
        app1.setName("huangqiuping");

        App app2 = new App();
        app2.setName("huangqiuping");

        set2.add(app1);
        set2.add(app2);
        System.out.println("长度："+set2.size()+",内容为："+set2);

        //第三个 Set集合：
        Set<App> set3 = new HashSet<App>();
        App app3 = new App();
        app3.setName("huangqiuping");
        set3.add(app3);
        set3.add(app3);
        System.out.println("长度："+set3.size()+",内容为："+set3);
    }
}

测试结果：
长度：1,内容为：[huangqiuping]
长度：2,内容为：[com.huangqiuping.collection.App@efb78af, com.huangqiuping.collection.App@5f3306ad]
长度：1,内容为：[com.huangqiuping.collection.App@1fb030d8]

可以看到，第一个Set集合中最终只有一个元素；第二个Set集合保留了2个元素；第三个集合也只有1个元素；
来看看HashSet的add(E e)方法：

1
2
3

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

在底层HashSet调用了HashMap的put(K key, V value)方法:

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    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;
}

通过查看以上的源码，可以了解到：实际的逻辑都是在 HashMap的put() 方法中。
int hash = hash(key) 对传入的key计算hash值；
int i = indexFor(hash, table.length) 对hash值进行转换，转换成数组的index(HashMap中底层存储使用了Entry<K,V>[]数组)；
for (Entry<K,V> e = table[i]; e != null; e = e.next) 判断对应index下是否存在元素；
如果存在，则if(e.hash == hash && ((k = e.key) == key || key.equals(k)))判断；
如果不存在，则addEntry(hash, key, value, i)直接添加；
简单概括如下：
在向HashMap中添加元素时，先判断key的hashCode值是否相同，如果相同，则调用equals()、==进行判断，若相同则覆盖原有元素；如果不同，则直接向Map中添加元素；
通过上面的例子可以知道：
1、在第一个Set集合中，我们new了两个String对象，赋了相同的值。当传入到HashMap中时，key均为“huangqiuping”，所以hash和i的值都相同。进行if (e.hash == hash && ((k = e.key) == key || key.equals(k)))判断，由于String对象重写了equals()方法，所以在((k = e.key) == key || key.equals(k))判断时，返回了true，所以第二次的插入并不会增加Set集合的长度；
2、第二个Set集合中，也是new了两个对象，但没有重写equals()方法（底层调用的Object的equals()，也就是==判断），所以会增加2个元素；
3、第三个Set集合中，只new了一个对象，调用的两次add方法都添加的这个新new的对象，所以也只是保留了1个元素；

本文作者： 生活,生活?
本文链接： ayjcsgm.github.io/2019/12/11/简述HashSet的元素唯一机制/
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！

HashSet简介

HashSet基本操作

HashSet元素添加分析