HashSet源码解析(基于Java8)

• List保证元素的添加顺序，元素可重复
• Set不保证元素的添加顺序，元素不可重复

  

  

public class Test {
    public static void main(String[] args){
        Set<String> strSet = new HashSet<>();//new了一个HashSet
        strSet.add("张三");
        strSet.add("李四");
        strSet.add("王五");
        strSet.add("赵六");

        System.out.println("strSet : " + strSet);
        System.out.println("strSet.size() : " + strSet.size());
        System.out.println("strSet里是否为空 : " + strSet.isEmpty());

        System.out.println("删除王五。。。。");
        boolean delFlag = strSet.remove("王五");
        System.out.println("删除王五是否成功" + delFlag);
        System.out.println("删除王五后的strSet : " + strSet);
        System.out.println("strSet中是否包含王五：" + strSet.contains("王五"));
        System.out.println("strSet中是否包含张三：" + strSet.contains("张三"));

        System.out.println("clear清除元素...");
        strSet.clear();
        System.out.println("clear清除元素后的strSet : " + strSet);
        System.out.println("strSet长度 : " + strSet.size());
        System.out.println("strSet里是否为空 : " + strSet.isEmpty());

    }
}
           

new一个HashSet，只要是看到new，肯定在堆内存里开辟了一块空间，先找到HashSet的构造函数

出现了HashMap，再看一下map

继续执行以下代码，往strSet添加元素"张三"

strSet.add("张三");   
           

再看

add

就是调用底层HashMap的put方法，把"张三"作为key，

PRESENT

作为value放在HashMap

HashMap

如果

put

时

key

重了，会返回被覆盖的

value

（oldValue），否则返回

null

HashSet

又包装了，如果

key

没有重（

oldValue == null

），就返回

true

，否则返回

false

继续看这个

PRESENT

很简单就是new了一个Object,所有元素的value都指向Object对象

HashSet虽然底层是用HashMap来实现的，但由于用不到HashMap的value，所以不会为底层HashMap的每个value分配一个内存空间，因此并不会过多的占用内存，请放心食用。

再来看看示例代码里的

size()

isEmpty()

image.png

remove()

contains()

clear()

基本上没什么逻辑代码，就是复用了HashMap里的方法而已

HashSet就是利用HashMap来实现的。

大胆的猜测一下，TreeSet是不是也是用TreeMap来实现的呢

构造函数this调了另一个构造函数

、

再来看m

这个m是NavigableMap类型的，NavigableMap只是一个接口而已

再来看TreeMap，实现了NavigableMap这个接口

绕了好大一个圈，其实就是相当于

NavigableMap m = new TreeMap<>();
           

也就是说，

TreeSet

底层实现也是利用

TreeMap

来实现的，再来看看

TreeSet

的其它方法

TreeMap

的

add

是调用底层

TreeMap

put

，只是改了个名字而已

其它方法大致上也是如此，就不一一举例说明了

小结

HashSet底层声明了一个HashMap，HashSet做了一层包装，操作HashSet里的元素时其实是在操作HashMap里的元素。

TreeSet底层也是声明了一个TreeMap，操作TreeSet里的元素其实是操作TreeMap里的元素。

附 关于有序性

“不保证有序”和“保证无序”不等价，HashSet的iterator是前者而不是后者，所以在一次运行中看到有序的结果也是正常的，但不能依赖这个有序行为。况且HashSet并不关心key的“排序”，就算其iterator“有序”通常也是说“按元素插入顺序”（LinkedHashSet就支持插入顺序遍历）。

JDK8的HashSet实现变了，导致元素插入的位置发生了变化；iterator自身实现的顺序倒没变，还是按照内部插入的位置顺序来遍历，于是题主就看到了JDK7和JDK8的结果不一样。具体来说，是JDK7与JDK8的java.util.HashMap的hash算法以及HashMap的数据布局发生了变化。题主插入HashSet的是Integer，其hashCode()实现就返回int值本身。所以在对象hashCode这一步引入了巧合的“按大小排序”。然后HashMap.hash(Object)获取了对象的hashCode()之后会尝试进一步混淆。JDK8版java.util.HashMap内的hash算法比JDK7版的混淆程度低；在[0, 2^32-1]范围内经过HashMap.hash()之后还是得到自己。外加load factor正好在此例中让这个HashMap没有hash冲突，这就导致例中元素正好按大小顺序插入在HashMap的开放式哈希表里

\