美文网首页
面试宝典:数据结构-HashSet

面试宝典:数据结构-HashSet

作者: 平凡人笔记 | 来源:发表于2020-08-03 17:10 被阅读0次

    Java集合类关系图整理

    图1 图2

    “脱掉HashSet的外衣“

    构造函数

    • 默认构造器

    将传入的集合添加到HashSet的构造器

    public HashSet() {
            map = new HashMap<>();
        }
    • 将传入的集合添加到HashSet的构造器
    public HashSet(Collection<? extends E> c) {
            map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
            addAll(c);
    }
    • 明确初始容量和装载因子的构造器
    public HashSet(int initialCapacity, float loadFactor) {
            map = new HashMap<>(initialCapacity, loadFactor);
        }
    • 仅明确初始容量的构造器(装载因子默认0.75)
     public HashSet(int initialCapacity) {
            map = new HashMap<>(initialCapacity);
     }

    脱掉HashSet的外衣之后 发现里面是HashMap

    新增元素

    private static final Object PRESENT = new Object();

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

    HashSet添加的元素是存放在HashMap的key位置上,而value取了默认常量PRESENT,是一个空对象

    HashMap的存取及扩容原理
    • 一个HashMap中是16个默认容量元素的阵列-每个区块对应于不同的哈希码值

    • 如果各种对象具有相同的哈希码值,则它们将存储在单个存储buckets

    • 如果达到了加载因子,则会创建一个新数组,该数组的大小是前一个数组的两倍,并且所有元素都会被重新分散并在新的相应存储块中并重新分配

    • 要检索一个值,我们对一个键进行哈希处理,对其进行修改,然后转到相应的存储块,并在存在多个对象的情况下搜索潜在的链表

    删除元素

    removeNode

    特点

    • 存储唯一元素并允许空值

    • 由HashMap支持

    • 不保持插入顺序

    • 不是线程安全的

    HashSet如何保持唯一性

    • 将一个对象放入一个HashSet时,它使用该对象的hashcode值来确定一个元素是否已经在该集合中

    • 每个散列码值对应于某个块位置,该块位置可以包含计算出的散列值相同的各种元素

    • 具有相同hashCode的两个对象可能不相等。因此,将使用equals()方法比较同一存储桶中的对象

    HashSet的性能

    HashSet的性能主要受两个参数影响 - 初始容量和负载因子

    将元素添加到集合的预期时间复杂度是O(1),在最坏的情况下(仅存在一个存储桶)可以降至O(n) - 因此,维护正确的HashSet容量至关重要

    从JDK 8开始,最坏的情况时间复杂度为O(log * n)

    较低的初始容量降低了空间复杂性,但增加了重新散布的频率

    根据经验:

    • 高初始容量适用于大量条目,几乎没有迭代

    • 低初始容量适用于具有大量迭代的少数条目

    结语

    HashSet具有恒定的时间性能和避免重复的能力 只有深入了解它,才能更好的使用它

    相关文章

      网友评论

          本文标题:面试宝典:数据结构-HashSet

          本文链接:https://www.haomeiwen.com/subject/xbkbrktx.html