面试宝典:数据结构-HashSet

2020-08-03  本文已影响0人  平凡人笔记

Java集合类关系图整理

图1 图2

“脱掉HashSet的外衣“

构造函数

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

public HashSet() {
        map = new HashMap<>();
    }
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);
    }
 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的存取及扩容原理

删除元素

removeNode

特点

HashSet如何保持唯一性

HashSet的性能

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

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

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

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

根据经验:

结语

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

上一篇下一篇

猜你喜欢

热点阅读