java中HashSet詳解

?？莺?/a> 2013-09-19

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

Java代碼

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 創(chuàng)建 HashSet
// 其實就是以相應的參數(shù)創(chuàng)建 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);
}
// 調(diào)用 map 的 keySet 來返回所有的 key
public Iterator<E> iterator()
{
return map.keySet().iterator();
}
// 調(diào)用 HashMap 的 size() 方法返回 Entry 的數(shù)量，就得到該 Set 里元素的個數(shù)
public int size()
{
return map.size();
}
// 調(diào)用 HashMap 的 isEmpty() 判斷該 HashSet 是否為空，
// 當 HashMap 為空時，對應的 HashSet 也為空
public boolean isEmpty()
{
return map.isEmpty();
}
// 調(diào)用 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;
}
// 調(diào)用 HashMap 的 remove 方法刪除指定 Entry，也就刪除了 HashSet 中對應的元素
public boolean remove(Object o)
{
return map.remove(o)==PRESENT;
}
// 調(diào)用 Map 的 clear 方法清空所有 Entry，也就清空了 HashSet 中所有元素
public void clear()
{
map.clear();
}
...
}

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

HashSet 的絕大部分方法都是通過調(diào)用 HashMap 的方法來實現(xiàn)的，因此 HashSet 和 HashMap 兩個集合在實現(xiàn)本質(zhì)上是相同的。
掌握上面理論知識之后，接下來看一個示例程序，測試一下自己是否真正掌握了 HashMap 和 HashSet 集合的功能。

Java代碼

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。

實際運行上面程序?qū)⒖吹匠绦蜉敵?false，這是因為 HashSet 判斷兩個對象相等的標準除了要求通過 equals() 方法比較返回 true 之外，還要求兩個對象的 hashCode() 返回值相等。而上面程序沒有重寫 Name 類的 hashCode() 方法，兩個 Name 對象的 hashCode() 返回值并不相同，因此 HashSet 會把它們當成 2 個對象處理，因此程序返回 false。

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

Java代碼

class Name
{
private String first;
private String last;
public Name(String first, String last)
{
this.first = first;
this.last = last;
}
// 根據(jù) 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;
}
// 根據(jù) 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() 兩個方法，這兩個方法都是根據(jù) 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 對象。