Java 中的哈希集

該類別HashSet實作接口Set，基於哈希表，並由實例支援HashMap。由於HashSet元素沒有排序，因此不能保證在一段時間後元素的順序相同。只要雜湊函數正確地將元素分配到「桶」中，添加、刪除和搜尋操作就會在常數時間內完成，這將在後面討論。 關於以下幾個要點HashSet：

• 因為 該類別實作了接口Set，它只能儲存唯一值；
• 可以儲存NULL值；
• 元素添加的順序是使用哈希碼計算的；
• HashSet還實現了Serializable和Cloneable。

為了保持操作的執行時間恆定， , 操作所花費的時間必須與 中的元素數量+ 內建實例的「容量」（「籃子」數量）HashSet成正比。因此，為了保持效能，重要的是不要將初始容量設定得太高（或負載因子太低）。初始容量 – 雜湊表中單元（“bin”）的初始數量。如果所有單元格都被填滿，它們的數量將自動增加。負載係數是衡量其容量自動增加之前的滿載程度的指標。當 中的元素數量大於初始容量和負載因子的乘積時，哈希表將被重新哈希（重新計算元素的哈希碼，並根據獲得的值重建表），並且數量其中的細胞數量增加了一倍。 負載因子 = 表中儲存的元素數量 / 雜湊表大小 例如，如果表中的初始單元格數量為 16，負載因子為 0.75，則當填充的單元格數量達到 12 時，細胞數量會自動增加。負載係數和初始容量是影響效能的兩個主要因素。0.75 的負載因子可提供良好的平均效能。如果增加該參數，那麼記憶體負載將會減少（因為它將減少重新散列和重建操作的次數），但會影響追加和查找操作。為了最大限度地減少重新散列所花費的時間，您需要選擇正確的初始容量參數。如果初始容量大於最大元素數除以負載因子，則根本不會發生重新雜湊操作。 HashSetHashMapHashSetHashSetHashSet重要的：HashSet不是具有內建同步功能的資料結構，因此如果多個執行緒同時對其進行操作，並且至少其中一個執行緒試圖進行更改，則有必要從外部提供同步存取。這通常是以另一個封裝HashSet. 如果不存在這樣的對象，則Collections.synchronizedSet(). 這是目前防止與HashSet.

Set s = Collections.synchronizedSet(new HashSet(...));

哈希集構造函數：

1. HashSet h = new HashSet(); - 預設建構子。預設初始容量為16，負載係數為0.75。
2. HashSet h = new HashSet(int initialCapacity)– 具有給定初始容量的建構函式。負載係數 – 0.75。
3. HashSet h = new HashSet(int initialCapacity, float loadFactor);— 具有給定初始容量和負載係數的建構函數。
4. HashSet h = new HashSet(Collection C)– 新增另一個集合中的元素的建構子。

下面的程式碼示範了一些方法HashSet：

import java.util.*;

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

        // Add elements to the HashSet using the add() method
        h.add("India");
        h.add("Australia");
        h.add("South Africa");
        h.add("India");// try to add another same element

        // Print the elements of the HashSet to the console
        System.out.println(h);
        System.out.println("List contains India or not:" +
                           h.contains("India"));

        // Remove elements from the set using the remove() method
        h.remove("Australia");
        System.out.println("List after removing Australia:"+h);

        // Loop through the elements of the HashSet using an iterator:
        System.out.println("Iterating over list:");
        Iterator<String> i = h.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }
}

結論：

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

所有實作介面的類別Set都由實作內部支援Map。HashSet使用 儲存元素HashMap。儘管HashMap元素必須表示為鍵值對才能新增元素，但 HashSet僅會新增值。事實上，我們傳遞給物件的值HashSet是物件的鍵HashMap，並且使用一個常數作為值HashMap。這樣，在每個鍵值對中，所有鍵都將具有相同的值。 實施HashSet於java doc：

private transient HashMap map;

// Constructor - 1
// All constructors implicitly create a HashMap object.
public HashSet()
{
    // Create an implicit HashMap object
    map = new HashMap();
}

// Constructor- 2
public HashSet(int initialCapacity)
{
    // Create an implicit HashMap object
    map = new HashMap(initialCapacity);
}

// An object of the Object class, each time acting as a value in the HashMap
private static final Object PRESENT = new Object();

如果你看一下方法add()y HashSet：

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

您可以注意到方法add()y呼叫內部物件上的HashSet方法，將要新增的元素作為鍵傳遞給它，並將 PRESENT 常數作為值傳遞給它。該方法的工作原理類似。它呼叫內部物件方法： put()HashMapremove()remove()HashMap

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

HashSet基於哈希表，新增、刪除或尋找操作平均將在常數 (O(1)) 時間內完成。 方法HashSet：

1. boolean add(E e)：在 中新增一個元素HashSet，如果沒有，但如果這樣的元素已經存在，則該方法傳回false。
2. void clear():從集合中刪除所有元素。
3. boolean contains(Object o)：如果給定元素存在於集合中，則傳回true 。
4. boolean remove(Object o)：從集合中刪除給定元素（如果存在）。
5. Iterator iterator()：傳回集合元素的迭代器。
6. boolean isEmpty()：如果集合中沒有元素，則傳回true 。
7. Object clone()：執行表面克隆HashSet。

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