首頁 > 軟體

為何HashSet中使用PRESENT而不是null作為value

2022-10-14 14:01:11

1. 為什麼 HashSet 中使用 PRESENT 而不是 null 作為 value

無意之中碰到了這個問題,在此記錄一下

1.1. PRESENT 是個什麼玩意

HashSet 的部分原始碼如下

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    
    static final long serialVersionUID = -5024744406713321676L;
    private transient HashMap<E,Object> map;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
}

1.2. HashSet 的構造方法

// 預設建構函式 底層建立一個HashMap
public HashSet() {
    // 呼叫HashMap的預設建構函式,建立map
    map = new HashMap<E,Object>();
}
 
// 帶集合的建構函式
public HashSet(Collection<? extends E> c) {
    // 建立map。
    map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
    // 將集合(c)中的全部元素新增到HashSet中
    addAll(c);
}
 
// 指定HashSet初始容量和載入因子的建構函式
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<E,Object>(initialCapacity, loadFactor);
}
 
// 指定HashSet初始容量的建構函式
public HashSet(int initialCapacity) {
    map = new HashMap<E,Object>(initialCapacity);
}
 
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}

1.3. PRESENT 何時會被用到

  • add(E) 方法
  • remove(Object) 方法

1.3.1. HashSet 中的 add(E) 方法

/**
 * add(E) 方法返回 null 時,表示 HashSet 新增資料成功
 *
 * @return true 如果不包含該元素
 */
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

直接呼叫的是 HashMap 的 put(K, V) 方法,此時傳入的 value 值是 PRESENT

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    // tab表示 Node<K,V>型別的陣列,p表示某一個具體的單連結串列 Node<K,V> 節點               
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 判斷 table[] 是否為空,如果是空的就建立一個 table[],並獲取他的長度n
    if ((tab = table) == null || (n = tab.length) == 0)
    	n = (tab = resize()).length;	
    // tab[i = (n - 1) & hash] 表示陣列中的某一個具體位置的資料	
    // 如果單連結串列 Node<K,V> p == tab[i = (n - 1) & hash]) == null,
    // 就直接 put 進單連結串列中,說明此時並沒有發生 Hash 衝突
    if ((p = tab[i = (n - 1) & hash]) == null)
    	tab[i] = newNode(hash, key, value, null);
    else {
		// 說明索引位置已經放入過資料了,已經在單連結串列處產生了Hash衝突
        Node<K,V> e; K k;
		// 判斷 put 的資料和之前的資料是否重複
        if (p.hash == hash &&
            // 進行 key 的 hash 值和 key 的 equals() 和 == 比較,如果都相等,則初始化陣列 Node<K,V> e
            ((k = p.key) == key || (key != null && key.equals(k))))   			
            e = p;
		// 判斷是否是紅黑樹,如果是紅黑樹就直接插入樹中
        else if (p instanceof TreeNode)
        	e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
			// 如果不是紅黑樹,就遍歷每個節點,判斷單連結串列長度是否大於等於 7,
			// 如果單連結串列長度大於等於 7,陣列的長度小於 64 時,會優先選擇擴容
			// 如果單連結串列長度大於等於 7,陣列的長度大於 64 時,才會選擇單連結串列--->紅黑樹
            for (int binCount = 0; ; ++binCount) {
            	if ((e = p.next) == null) {
            		// 採用尾插法,在單連結串列中插入資料
                	p.next = newNode(hash, key, value, null);
                	// 如果 binCount >= 8 - 1
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                    	treeifyBin(tab, hash);
                        break;
                }
				// 判斷索引每個元素的key是否可要插入的key相同,如果相同就直接覆蓋
                if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                 p = e;
			}
		}		
        if (e != null) { 
        	// 此時說明 key 的 hash 值和 key 的 equals() 和 == 比較結果都相等
        	// 說明陣列或者單連結串列中有完全相同的 key
        	// 因此只需要將value覆蓋,並將oldValue返回即可
        	V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
            	e.value = value;
                afterNodeAccess(e);
              	return oldValue;
        }
	}
	// 說明沒有key相同,因此要插入一個key-value,並記錄內部結構變化次數
    ++modCount;
    // 判斷是否擴容
    if (++size > threshold)
    	resize();
    afterNodeInsertion(evict);
    return null;
}

關於 HashMap 的 put(K, V) 方法的 詳細解析請看這裡

  • 如果 return oldValue 說明發生了 value 覆蓋,也就是說此時返回了 PRESENT,自然而然 HashMap 新增資料失敗
  • 如果 return null 說明 HashMap 新增資料成功

而如果將 PRESENT 替換為 null 作為 value 值,那麼 HashSet 的 add(E) 方法將無法判斷新增元素的成功與失敗;因為不管是成功與失敗都會返回結果 null

1.3.2. HashMap 進行 put 元素範例

1.3.3. HashSet 中的 remove(Object) 方法

HashSet 的 remove(Object) 方法原始碼

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

HashSet 的 remove(Object) 依舊直接使用 HashMap 的 remove(Object) 方法

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

HashMap 的 remove(Object) 方法會返回 null 或 value

  • 有該值,返回 value 也就是 PRESENT,表示 remove 成功
  • 無該值,返回 null,自然而然 remove 失敗

而如果將 PRESENT 替換為 null 作為 value 值,那麼 HashSet 的 remove(Object) 方法將無法判斷移除元素的成功與失敗;因為不管是成功與失敗都會返回結果 null

以上為個人經驗,希望能給大家一個參考,也希望大家多多支援it145.com。


IT145.com E-mail:sddin#qq.com