HashSet工作原理_動力節點Java學院整理

對於 HashSet 而言，它是基於 HashMap 實現的，HashSet 底層采用 HashMap 來保存所有元素，因此 HashSet 的實現比較簡單，查看 HashSet 的源代碼，可以看到如下代碼：

public class HashSet<E> 
 extends AbstractSet<E> 
 implements Set<E>, Cloneable, java.io.Serializable 
 { 
 // 使用 HashMap 的 key 保存 HashSet 中所有元素
 private transient HashMap<E,Object> map; 
 // 定義一個虛擬的 Object 對象作為 HashMap 的 value 
 private static final Object PRESENT = new Object(); 
 ... 
 // 初始化 HashSet，底層會初始化一個 HashMap 
 public HashSet() 
 { 
 map = new HashMap<E,Object>(); 
 } 
 // 以指定的 initialCapacity、loadFactor 創建 HashSet 
 // 其實就是以相應的參數創建 HashMap 
 public HashSet(int initialCapacity, float loadFactor) 
 { 
 map = new HashMap<E,Object>(initialCapacity, loadFactor); 
 } 
 public HashSet(int initialCapacity) 
 { 
 map = new HashMap<E,Object>(initialCapacity); 
 } 
 HashSet(int initialCapacity, float loadFactor, boolean dummy) 
 { 
 map = new LinkedHashMap<E,Object>(initialCapacity 
 , loadFactor); 
 } 
 // 調用 map 的 keySet 來返回所有的 key 
 public Iterator<E> iterator() 
 { 
 return map.keySet().iterator(); 
 } 
 // 調用 HashMap 的 size() 方法返回 Entry 的數量，就得到該 Set 裡元素的個數
 public int size() 
 { 
 return map.size(); 
 } 
 // 調用 HashMap 的 isEmpty() 判斷該 HashSet 是否為空，
 // 當 HashMap 為空時，對應的 HashSet 也為空
 public boolean isEmpty() 
 { 
 return map.isEmpty(); 
 } 
 // 調用 HashMap 的 containsKey 判斷是否包含指定 key 
 //HashSet 的所有元素就是通過 HashMap 的 key 來保存的
 public boolean contains(Object o) 
 { 
 return map.containsKey(o); 
 } 
 // 將指定元素放入 HashSet 中，也就是將該元素作為 key 放入 HashMap 
 public boolean add(E e) 
 { 
 return map.put(e, PRESENT) == null; 
 } 
 // 調用 HashMap 的 remove 方法刪除指定 Entry，也就刪除了 HashSet 中對應的元素
 public boolean remove(Object o) 
 { 
 return map.remove(o)==PRESENT; 
 } 
 // 調用 Map 的 clear 方法清空所有 Entry，也就清空了 HashSet 中所有元素
 public void clear() 
 { 
 map.clear(); 
 } 
 ... 
 }

由上面源程序可以看出，HashSet 的實現其實非常簡單，它只是封裝了一個 HashMap 對象來存儲所有的集合元素，所有放入 HashSet 中的集合元素實際上由 HashMap 的 key 來保存，而 HashMap 的 value 則存儲了一個 PRESENT，它是一個靜態的 Object 對象。

HashSet 的絕大部分方法都是通過調用 HashMap 的方法來實現的，因此 HashSet 和 HashMap 兩個集合在實現本質上是相同的。

HashMap 的 put 與 HashSet 的 add

由於 HashSet 的 add() 方法添加集合元素時實際上轉變為調用 HashMap 的 put() 方法來添加 key-value 對，當新放入 HashMap 的 Entry 中 key 與集合中原有 Entry 的 key 相同（hashCode() 返回值相等，通過 equals 比較也返回 true），新添加的 Entry 的 value 將覆蓋原來 Entry 的 value，但 key 不會有任何改變，因此如果向 HashSet 中添加一個已經存在的元素，新添加的集合元素（底層由 HashMap 的 key 保存）不會覆蓋已有的集合元素。

掌握上面理論知識之後，接下來看一個示例程序，測試一下自己是否真正掌握了 HashMap 和 HashSet 集合的功能。
主要說明的就是重寫equals()方法時，就必須重寫hashCode()方法。

 class Name
{
 private String first; 
 private String last; 
 public Name(String first, String last) 
 { 
  this.first = first; 
  this.last = last; 
 } 
 public boolean equals(Object o) 
 { 
  if (this == o) 
  { 
   return true; 
  } 
 if (o.getClass() == Name.class) 
  { 
   Name n = (Name)o; 
   return n.first.equals(first) 
    && n.last.equals(last); 
  } 
  return false; 
 } 
}
public class HashSetTest
{
 public static void main(String[] args)
 { 
  Set<Name> s = new HashSet<Name>();
  s.add(new Name("abc", "123"));
  System.out.println(
   s.contains(new Name("abc", "123")));
 }
}

上面程序中向 HashSet 裡添加了一個 new Name("abc", "123") 對象之後，立即通過程序判斷該 HashSet 是否包含一個 new Name("abc", "123") 對象。粗看上去，很容易以為該程序會輸出 true。

實際運行上面程序將看到程序輸出 false，這是因為 HashSet 判斷兩個對象相等的標准除了要求通過 equals() 方法比較返回 true 之外，還要求兩個對象的 hashCode() 返回值相等。而上面程序沒有重寫 Name 類的 hashCode() 方法，兩個 Name 對象的 hashCode() 返回值並不相同，因此 HashSet 會把它們當成 2 個對象處理，因此程序返回 false。

由此可見，當我們試圖把某個類的對象當成 HashMap 的 key，或試圖將這個類的對象放入 HashSet 中保存時，重寫該類的 equals(Object obj) 方法和 hashCode() 方法很重要，而且這兩個方法的返回值必須保持一致：當該類的兩個的 hashCode() 返回值相同時，它們通過 equals() 方法比較也應該返回 true。通常來說，所有參與計算 hashCode() 返回值的關鍵屬性，都應該用於作為 equals() 比較的標准。

如下程序就正確重寫了 Name 類的 hashCode() 和 equals() 方法，程序如下：

class Name 
{ 
 private String first;
 private String last;
 public Name(String first, String last)
 { 
  this.first = first; 
  this.last = last; 
 } 
 // 根據 first 判斷兩個 Name 是否相等
 public boolean equals(Object o) 
 { 
  if (this == o) 
  { 
   return true; 
  } 
  if (o.getClass() == Name.class) 
  { 
   Name n = (Name)o; 
   return n.first.equals(first); 
  } 
  return false; 
 } 
 // 根據 first 計算 Name 對象的 hashCode() 返回值
 public int hashCode() 
 { 
  return first.hashCode(); 
 }
 public String toString() 
 { 
  return "Name[first=" + first + ", last=" + last + "]"; 
 } 
 } 
 public class HashSetTest2 
 { 
 public static void main(String[] args) 
 { 
  HashSet<Name> set = new HashSet<Name>(); 
  set.add(new Name("abc" , "123")); 
  set.add(new Name("abc" , "456")); 
  System.out.println(set); 
 } 
}

上面程序中提供了一個 Name 類，該 Name 類重寫了 equals() 和 toString() 兩個方法，這兩個方法都是根據 Name 類的 first 實例變量來判斷的，當兩個 Name 對象的 first 實例變量相等時，這兩個 Name 對象的 hashCode() 返回值也相同，通過 equals() 比較也會返回 true。

程序主方法先將第一個 Name 對象添加到 HashSet 中，該 Name 對象的 first 實例變量值為"abc"，接著程序再次試圖將一個 first 為"abc"的 Name 對象添加到 HashSet 中，很明顯，此時沒法將新的 Name 對象添加到該 HashSet 中，因為此處試圖添加的 Name 對象的 first 也是" abc"，HashSet 會判斷此處新增的 Name 對象與原有的 Name 對象相同，因此無法添加進入，程序在①號代碼處輸出 set 集合時將看到該集合裡只包含一個 Name 對象，就是第一個、last 為"123"的 Name 對象。

以上所述是小編給大家介紹的HashSet工作原理_動力節點Java學院整理，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對網站的支持！