Java中的HashSet

原文位址：HashSet in Java

HashSet：

• 實作了Set接口
• HashSet依賴的資料結構是哈希表
• 因為實作的是Set接口，是以不允許有重複的值
• 插入到HashSet中的對象不保證與插入的順序保持一緻。對象的插入是根據它的hashcode
• HashSet中允許有NULL值
• HashSet也實作了Searlizable和Cloneable兩個接口

HashSet的構造函數：

HashSet h = new HashSet();      
   預設初始化大小是，預設裝載因子是.

   HashSet h = new HashSet(int initialCapacity);  
   預設裝載因子是

   HashSet h = new HashSet(int initialCapacity, float loadFactor);

   HashSet h = new HashSet(Collection C);
           

什麼是初始化大小與裝載因子：

初始化尺寸就是當建立哈希表（HashSet内部用哈希表的資料結構）的時候桶（buckets）的數量。如果目前的尺寸已經滿了，那麼桶的數量會自動增長。

裝載因子衡量的是在HashSet自動增長之前允許有多滿。當哈希表中實體的數量已經超出裝載因子與目前容量的積，那麼哈希表就會再次進行哈希（也就是内部資料結構重建），這樣哈希表大緻有兩倍桶的數量。

表中已經存儲的元素的數量
   裝載因子 = -----------------------------------------
                       哈希表的大小
           

例如：如果内部容量為16，裝載因子為0.75，那麼當表中有12個元素的時候，桶的數量就會自動增長。

性能影響：

裝載因子和初始化容量是影響HashSet操作的兩個主要因素。裝載因子為0.75的時候可以提供關于時間和空間複雜度方面更有效的性能。如果我們加大這個裝載因子，那麼記憶體的上限就會減小（因為它減少了内部重建的操作），但是将影響哈希表中的add與查詢的操作。為了減少再哈希操作，我們應該選擇一個合适的初始化大小。如果初始化容量大于實體的最大數量除以裝載因子，那麼就不會有再哈希的動作發生了。

HashSet中的一些重要方法：

1. boolean add(E e)：如果不存在則添加，存在則傳回false。
2. void clear() ：移除Set中所有的元素
3. boolean contains(Object o)：如果這個元素在set中存在，那麼傳回true。
4. boolean remove(Object o)：如果這個元素在set中存在，那麼從set中删除。
5. Iterator iterator()：傳回set中這個元素的疊代器。

簡單的程式：

// Java program to demonstrate working of HashSet
import java.util.*;

class Test
{
    public static void main(String[]args)
    {
        HashSet<String> h = new HashSet<String>();

        // adding into HashSet
        h.add("India");
        h.add("Australia");
        h.add("South Africa");
        h.add("India");// adding duplicate elements

        // printing HashSet
        System.out.println(h);
        System.out.println("List contains India or not:" +
                           h.contains("India"));

        // Removing an item
        h.remove("Australia");
        System.out.println("List after removing Australia:"+h);

        // Iterating over hash set items
        System.out.println("Iterating over list:");
        Iterator<String> i = h.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }
}
           

上述代碼的輸出：

[Australia, South Africa, India]
List contains India or not:true
List after removing Australia:[South Africa, India]
Iterating over list:
South Africa
India
           

HashSet内部是如何工作的？

所有Set接口的類内部都是由Map做支撐的。HashSet用HashMap對它的内部對象進行排序。你一定好奇輸入一個值到HashMap，我們需要的是一個鍵值對，但是我們傳給HashSet的是一個值。

那麼HashMap是如何排序的？

實際上我們插入到HashSet中的值在map對象中起的是鍵的作用，因為它的值Java用了一個常量。是以在鍵值對中所有的鍵的值都是一樣的。

如果我們在Java Doc中看一下HashSet的實作，大緻是這樣的：

private transient HashMap map;

// Constructor - 1
// All the constructors are internally creating HashMap Object.
public HashSet()
{
    // Creating internally backing HashMap object
    map = new HashMap<>();
}

// Constructor - 2
public HashSet(int initialCapacity)
{
    // Creating internally backing HashMap object
    map = new HashMap<>(initialCapacity);
}

// Dummy value to associate with an Object in Map
private static final Object PRESENT = new Object();
           

如果我們看下HashSet中的add方法：

public boolean add(E e)
{
   return map.put(e, PRESENT) == null;
}
           

我們可以注意到，HashSet類的add()方法内部調用的是HashMap的put()方法，通過你指定的值作為key，常量“PRESENT”作為值傳過去。

remove()也是用類似的方法工作。它内部調用的是Map接口的remove。

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

HashSet操作的時間複雜度：

HashSet底層的資料結構是哈希表，是以HashSet的add，remove與查詢（包括contain方法）的分攤（平均或者一般情況）時間複雜度是O(1)。

參考文獻：

https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html