乐趣区

关于java:面试官HashSet如何保证元素不重复

本文已收录《Java 常见面试题》系列,Git 开源地址:https://gitee.com/mydb/interview

HashSet 实现了 Set 接口,由哈希表(理论是 HashMap)提供反对。HashSet 不保障汇合的迭代程序,但容许插入 null 值。也就是说 HashSet 不能保障元素插入程序和迭代程序雷同。
HashSet 具备去重的个性,也就是说它能够将汇合中的反复元素主动过滤掉,保障存储在 HashSet 中的元素都是惟一的。

1.HashSet 根本用法

HashSet 基本操作办法有:add(增加)、remove(删除)、contains(判断某个元素是否存在)和 size(汇合数量)。这些办法的性能都是固定操作工夫,如果哈希函数是将元素扩散在桶中的正确地位。
HashSet 根本应用如下:

// 创立 HashSet 汇合
HashSet<String> strSet = new HashSet<>();
// 给 HashSet 增加数据
strSet.add("Java");
strSet.add("MySQL");
strSet.add("Redis");
// 循环打印 HashSet 中的所有元素
strSet.forEach(s -> System.out.println(s));

2.HashSet 无序性

HashSet 不能保障插入元素的程序和循环输入元素的程序肯定雷同,也就是说 HashSet 其实是无序的汇合,具体代码示例如下:

HashSet<String> mapSet = new HashSet<>();
mapSet.add("深圳");
mapSet.add("北京");
mapSet.add("西安");
// 循环打印 HashSet 中的所有元素
mapSet.forEach(m -> System.out.println(m));

以上程序的执行后果如下:

从上述代码和执行后果能够看出,HashSet 插入的程序是:深圳 -> 北京 -> 西安 ,而循环打印的程序却是: 西安 -> 深圳 -> 北京,所以 HashSet 是无序的,不能保障插入和迭代的程序统一

PS:如果要保障插入程序和迭代程序统一,可应用 LinkedHashSet 来替换 HashSet。

3.HashSet 谬误用法

有人说 HashSet 只能保障根底数据类型不反复,却不能保障自定义对象不反复?这样说对吗?
咱们通过以下示例来阐明此问题。

3.1 HashSet 与根本数据类型

应用 HashSet 存储根本数据类型,实现代码如下:

HashSet<Long> longSet = new HashSet<>();
longSet.add(666l);
longSet.add(777l);
longSet.add(999l);
longSet.add(666l);
// 循环打印 HashSet 中的所有元素
longSet.forEach(l -> System.out.println(l));

以上程序的执行后果如下:

从上述后果能够看出,应用 HashSet 能够保障根底数据类型不反复。

3.2 HashSet 与自定义对象类型

接下来,将自定义对象存储到 HashSet 中,实现代码如下:

public class HashSetExample {public static void main(String[] args) {HashSet<Person> personSet = new HashSet<>();
        personSet.add(new Person("曹操", "123"));
        personSet.add(new Person("孙权", "123"));
        personSet.add(new Person("曹操", "123"));
        // 循环打印 HashSet 中的所有元素
        personSet.forEach(p -> System.out.println(p));
    }
}
@Getter
@Setter
@ToString
class Person {
    private String name;
    private String password;

    public Person(String name, String password) {
        this.name = name;
        this.password = password;
    }
}

以上程序的执行后果如下:

从上述后果能够看出,自定义对象类型的确没有被去重,那也就是说 HashSet 不能实现自定义对象类型的去重咯?
其实并不是,HashSet 去重性能是依赖元素的 hashCode 和 equals 办法判断的,通过这两个办法返回的都是 true 那就是雷同对象,否则就是不同对象。而后面的 Long 类型元素之所以能实现去重,正是因为 Long 类型中曾经重写了 hashCode 和 equals 办法,具体实现源码如下:

@Override
public int hashCode() {return Long.hashCode(value);
}
public boolean equals(Object obj) {if (obj instanceof Long) {return value == ((Long)obj).longValue();}
    return false;
}
// 省略其余源码......

更多对于 hashCode 和 equals 的内容,详见:https://mp.weixin.qq.com/s/40zaEJEkQYM3Awk2EwIrWA

那么,想让 HashSet 反对自定义对象去重,只须要在自定义对象中重写 hashCode 和 equals 办法即可,具体实现代码如下:

@Setter
@Getter
@ToString
class Person {
    private String name;
    private String password;
    public Person(String name, String password) {
        this.name = name;
        this.password = password;
    }
    @Override
    public boolean equals(Object o) {if (this == o) return true; // 援用相等返回 true
        // 如果等于 null,或者对象类型不同返回 false
        if (o == null || getClass() != o.getClass()) return false;
        // 强转为自定义 Person 类型
        Person persion = (Person) o;
        // 如果 name 和 password 都相等,就返回 true
        return Objects.equals(name, persion.name) &&
                Objects.equals(password, persion.password);
    }
    @Override
    public int hashCode() {
        // 比照 name 和 password 是否相等
        return Objects.hash(name, password);
    }
}

从新运行以上代码,执行后果如下图所示:

从上述后果能够看出,之前的反复项“曹操”曾经被去重了。

4.HashSet 如何保障元素不反复?

咱们只有理解了 HashSet 执行增加元素的流程,就能晓得为什么 HashSet 能保障元素不反复了?
HashSet 增加元素的执行流程是:当把对象退出 HashSet 时,HashSet 会先计算对象的 hashcode 值来判断对象退出的地位,同时也会与其余退出的对象的 hashcode 值作比拟,如果没有相符的 hashcode,HashSet 会假如对象没有反复呈现,会将对象插入到相应的地位中。然而如果发现有雷同 hashcode 值的对象,这时会调用对象的 equals() 办法来查看对象是否真的雷同,如果雷同,则 HashSet 就不会让反复的对象退出到 HashSet 中,这样就保障了元素的不反复。

为了更分明的理解 HashSet 的增加流程,咱们能够尝试浏览 HashSet 的具体实现源码,HashSet 增加办法的实现源码如下(以下源码基于 JDK 8):

// hashmap 中 put() 返回 null 时,示意操作胜利
public boolean add(E e) {return map.put(e, PRESENT)==null;
}

从上述源码能够看出 HashSet 中的 add 办法,理论调用的是 HashMap 中的 put,那么咱们持续看 HashMap 中的 put 实现:

// 返回值:如果插入地位没有元素则返回 null,否则返回上一个元素
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}

从上述源码能够看出,HashMap 中的 put() 办法又调用了 putVal() 办法,putVal() 的源码如下:

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {Node<K, V>[] tab;
        Node<K, V> p;
        int n, i;
        // 如果哈希表为空,调用 resize() 创立一个哈希表,并用变量 n 记录哈希表长度
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        /**
         * 如果指定参数 hash 在表中没有对应的桶,即为没有碰撞
         * Hash 函数,(n - 1) & hash 计算 key 将被搁置的槽位
         * (n - 1) & hash 实质上是 hash % n 位运算更快
         */
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 间接将键值对插入到 map 中即可
            tab[i] = newNode(hash, key, value, null);
        else {// 桶中曾经存在元素
            Node<K, V> e;
            K k;
            // 比拟桶中第一个元素 (数组中的结点) 的 hash 值相等,key 相等
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                // 将第一个元素赋值给 e,用 e 来记录
                e = p;
                // 以后桶中无该键值对,且桶是红黑树结构,依照红黑树结构插入
            else if (p instanceof TreeNode)
                e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
                // 以后桶中无该键值对,且桶是链表构造,依照链表构造插入到尾部
            else {for (int binCount = 0; ; ++binCount) {
                    // 遍历到链表尾部
                    if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);
                        // 查看链表长度是否达到阈值,达到将该槽位节点组织模式转为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 链表节点的 <key, value> 与 put 操作 <key, value>
                    // 雷同时,不做反复操作,跳出循环
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 找到或新建一个 key 和 hashCode 与插入元素相等的键值对,进行 put 操作
            if (e != null) { // existing mapping for key
                // 记录 e 的 value
                V oldValue = e.value;
                /**
                 * onlyIfAbsent 为 false 或旧值为 null 时,容许替换旧值
                 * 否则无需替换
                 */
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 拜访后回调
                afterNodeAccess(e);
                // 返回旧值
                return oldValue;
            }
        }
        // 更新结构化批改信息
        ++modCount;
        // 键值对数目超过阈值时,进行 rehash
        if (++size > threshold)
            resize();
        // 插入后回调
        afterNodeInsertion(evict);
        return null;
    }

从上述源码能够看出,当将一个键值对放入 HashMap 时,首先依据 key 的 hashCode() 返回值决定该 Entry 的存储地位。如果有两个 key 的 hash 值雷同,则会判断这两个元素 key 的 equals() 是否雷同,如果雷同就返回 true,阐明是反复键值对,那么 HashSet 中 add() 办法的返回值会是 false,示意 HashSet 增加元素失败。因而,如果向 HashSet 中增加一个曾经存在的元素,新增加的汇合元素不会笼罩已有元素,从而保障了元素的不反复。如果不是反复元素,put 办法最终会返回 null,传递到 HashSet 的 add 办法就是增加胜利。

总结

HashSet 底层是由 HashMap 实现的,它能够实现反复元素的去重性能,如果存储的是自定义对象必须重写 hashCode 和 equals 办法。HashSet 保障元素不反复是利用 HashMap 的 put 办法实现的,在存储之前先依据 key 的 hashCode 和 equals 判断是否已存在,如果存在就不在反复插入了,这样就保障了元素的不反复。

卒然临之而不惊,无端加之而不怒。

博主:80 后程序员。喜好:读书、写作和慢跑。

公众号:Java 面试真题解析

退出移动版