JDK集合源碼之HashSet解析

HashSet的特點

無序性（存儲元素無序）
唯一性（允許使用null）
本質上，HashSet底層是通過HashMap來保證唯一性
HashSet沒有提供 get() 方法，同HashMap一樣，因為Set内部是無序的，是以隻能通過疊代的方式獲得

HashSet的繼承體系

HashSet源碼分析

1. 屬性(成員變量)

// HashSet内部使用HashMap來存儲元素，是以本質上是HashMap
private transient HashMap<E,Object> map;

// 虛拟對象，用來作為value放到map中(在HashSet底層的HashMap中，key為要存儲的元素，value統一為PRESENT)
private static final Object PRESENT = new Object();

2. 構造方法

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);
}

// 注意：這裡未用public修飾，主要是給LinkedHashSet使用的
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

構造方法都是調用HashMap對應的構造方法。最後一個構造方法有點特殊，它不是public的，意味着它隻能被同一個包或者子類調用，這是LinkedHashSet專屬的方法。

3. 成員方法

3.1 添加元素add(E e)

// HashSet添加元素的時候，直接調用的是HashMap中的put()方法，
// 把元素本身作為key，把PRESENT作為value，也就是這個map中所有的value都是一樣的。
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

3.2 删除元素remove(Object o)

// HashSet删除元素，直接調用HashMap的remove方法
public boolean remove(Object o) {
    // 注意：map的remove傳回是删除元素的value，而Set的remov傳回的是boolean類型
    // 如果是null的話說明沒有該元素，如果不是null肯定等于PRESENT
    return map.remove(o)==PRESENT;
}

3.3 查找元素contains(Object o)

// Set中沒有get()方法，不像List那樣可以按index擷取元素
public boolean contains(Object o) {
    return map.containsKey(o);
}

4. 完整代碼

HashSet是基于HashMap的，是以其源碼較少：

package java.util;

import java.io.InvalidObjectException;
import sun.misc.SharedSecrets;


public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    // 内部元素存儲在HashMap中
    private transient HashMap<E,Object> map;

    // 虛拟元素，用來存到map元素的value中的，沒有實際意義
    private static final Object PRESENT = new Object();

    // 空構造方法
    public HashSet() {
        map = new HashMap<>();
    }

    // 把另一個集合的元素全都添加到目前Set中
    // 注意，這裡初始化map的時候是計算了它的初始容量的
    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);
    }

    // LinkedHashSet專用的方法
    // dummy是沒有實際意義的, 隻是為了跟上上面那個操持方法簽名不同而已
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
    
    // 疊代器
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    // 元素個數
    public int size() {
        return map.size();
    }

    // 檢查是否為空
    public boolean isEmpty() {
        return map.isEmpty();
    }

    // 檢查是否包含某個元素
    public boolean contains(Object o) {
        return map.containsKey(o);
    }
    
    // 添加元素
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    // 删除元素
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
    
    // 清空所有元素
    public void clear() {
        map.clear();
    }

    // 克隆方法
    @SuppressWarnings("unchecked")
    public Object clone() {
        try {
            HashSet<E> newSet = (HashSet<E>) super.clone();
            newSet.map = (HashMap<E, Object>) map.clone();
            return newSet;
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }

    // 序列化寫出方法
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // 寫出非static非transient屬性
        s.defaultWriteObject();

        // 寫出map的容量和裝載因子
        s.writeInt(map.capacity());
        s.writeFloat(map.loadFactor());

        // 寫出元素個數
        s.writeInt(map.size());

        // 周遊寫出所有元素
        for (E e : map.keySet())
            s.writeObject(e);
    }

    // 序列化讀入方法
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // 讀入非static非transient屬性
        s.defaultReadObject();

        // 讀入容量, 并檢查不能小于0
        int capacity = s.readInt();
        if (capacity < 0) {
            throw new InvalidObjectException("Illegal capacity: " +
                                             capacity);
        }

        // 讀入裝載因子, 并檢查不能小于等于0或者是NaN(Not a Number)
        // java.lang.Float.NaN = 0.0f / 0.0f;
        float loadFactor = s.readFloat();
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        }

        // 讀入元素個數并檢查不能小于0
        int size = s.readInt();
        if (size < 0) {
            throw new InvalidObjectException("Illegal size: " +
                                             size);
        }
        // 根據元素個數重新設定容量
        // 這是為了保證map有足夠的容量容納所有元素, 防止無意義的擴容
        capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
                HashMap.MAXIMUM_CAPACITY);

        // 再次檢查某些東西, 不重要的代碼忽視掉
        SharedSecrets.getJavaOISAccess()
                     .checkArray(s, Map.Entry[].class, HashMap.tableSizeFor(capacity));

        // 建立map, 檢查是不是LinkedHashSet類型
        map = (((HashSet<?>)this) instanceof LinkedHashSet ?
               new LinkedHashMap<E,Object>(capacity, loadFactor) :
               new HashMap<E,Object>(capacity, loadFactor));

        // 讀入所有元素, 并放入map中
        for (int i=0; i<size; i++) {
            @SuppressWarnings("unchecked")
                E e = (E) s.readObject();
            map.put(e, PRESENT);
        }
    }

    // 可分割的疊代器, 主要用于多線程并行疊代處理時使用
    public Spliterator<E> spliterator() {
        return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
    }
}

總結

HashSet内部使用HashMap的key存儲元素，以此來保證元素不重複；

HashSet是無序的，因為HashMap的key是無序的；

HashSet中允許有一個null元素，因為HashMap允許key為null；

HashSet是非線程安全的；

HashSet是沒有get()方法的；

擴充：

當向HashMap中存儲n個元素時，它的初始化容量應指定為：((n/0.75f) + 1)，如果這個值小于16，就直接使用16為容量。初始化時指定容量是為了減少擴容的次數，提高效率。

LinkedHashSet分析

package java.util;

// LinkedHashSet繼承自HashSet
public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;

    // 傳入容量和裝載因子
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }
    
    // 隻傳入容量, 裝載因子預設為0.75
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }
    
    // 使用預設容量16, 預設裝載因子0.75
    public LinkedHashSet() {
        super(16, .75f, true);
    }

    // 将集合c中的所有元素添加到LinkedHashSet中
    // 好奇怪, 這裡計算容量的方式又變了
    // HashSet中使用的是Math.max((int) (c.size()/.75f) + 1, 16)
    // 這一點有點不得其解, 是作者偷懶？
    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }
    
    // 可分割的疊代器, 主要用于多線程并行疊代處理時使用
    @Override
    public Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
    }
}

LinkedHashSet繼承自HashSet，它的添加、删除、查詢等方法都是直接用的HashSet的，唯一的不同就是它使用LinkedHashMap存儲元素。

LinkedHashSet是有序的，它是按照插入的順序排序的。

LinkedHashSet是不支援按通路順序對元素排序的，隻能按插入順序排序。

因為，LinkedHashSet所有的構造方法都是調用HashSet的同一個構造方法，如下：

// HashSet的構造方法
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

通過調用LinkedHashMap的構造方法初始化map，如下所示：

public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

可以看到，這裡把accessOrder寫死為false了。

是以，LinkedHashSet是不支援按通路順序對元素排序的，隻能按插入順序排序。

JDK集合源碼之HashSet解析

HashSet源碼分析

1. 屬性(成員變量)

2. 構造方法

3. 成員方法

3.1 添加元素add(E e)

3.2 删除元素remove(Object o)

3.3 查找元素contains(Object o)

4. 完整代碼

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method