解读java集合框架源码-Set

通过前面几篇文章,HashMapLinkedHashMapTreeMap了解了Map这个结构是怎么实现了之后,来看看Set的实现就比较容易了,因为Set的实现类TreeSet、HashSet、LinkedHashSet底层分别是用TreeMap、HashMap、LinkedHashMap实现的,也就是说Set的实现类其实就是Map各种实现类的马甲,d=====( ̄▽ ̄*)b

TreeSet

底层是一个TreeMap

JDK注释

类继承图

成员变量

构造器

添加元素

HashSet

JDK注释

类继承图

成员变量

构造器

我们来看一个比较独特的包私有的构造器,这个构造器提供给LinkedHashSet使用,将底层的map成员变量实例化为了LinkedHashMap,保证了添加元素的迭代有序

添加元素

LinkedHashSet

JDK注释

类继承图

构造器

添加元素

直接调用的HashSet的add方法

总结

  1. TreeSet,底层为TreeMap,迭代有序,不允许元素为null,add、catains、remove操作时间复杂度为O(logn)
  2. HashSet,底层为HashMap,无序,运行元素为null,add、contains、remove时间复杂度为O(1)
  3. LinkedHashSet,底层为LinkedHashMap,迭代有序,运行元素为null,add、contains、remove时间复杂度为O(1)。而且不同于HashSet,其迭代遍历性能不受hash表capacity影响,可以在预知元素个数的前提下,设置更大的capacity来减少重新hash和扩容。不考虑内存消耗的情况来看,更适合使用LinkedHashSet而不是TreeSet