本文將深入討論HashSet實現原理的源碼細節。在分析源碼之前，首先我們需要對HashSet有一個基本的理解。
HashSet只存儲不同的值，set中是不會出現重復值的。
HashSet和HashMap一樣也需要實現hash算法來計算對象的hash值，但不同的是，HashMap中添加一個鍵值對的時候， (Key, Value)，hash函數計算的是Key的hash值。而HashSet則是計算value的hash值。當我們調用HashSet的add(E e)的方法 的時候，我們會計算機元素e的hash值，如果這個值之前沒出現過，就說明這個元素在set中不存在，如果出現過，就說明。set中已經存在了，就添加失敗。
java static關鍵字、知道了上述的基本概念之后，我們就可以打開JDK源碼，來一探究竟了。
關于hashSet的實現原理，最重要的一個點就是HashSet內部是使用HashMap來存儲對象的。所以請讀者務必先對hashMap的實現原理有一個初步的認識。參考筆者的文章HashMap實現原理分析(Java源碼剖析)
我們可以看到HashSet有多個構造函數，但每個構造函數都是初始化了一個HashMap的對象
/**
linkedhashset原理？* Constructs a new, empty set; the backing HashMap instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
java.util、map = new HashMap<>();
}
/**
* Constructs a new set containing the elements in the specified
java 多線程編程、* collection. The HashMap is created with default load factor
* (0.75) and an initial capacity sufficient to contain the elements in
* the specified collection.
*
java hash函數。* @param c the collection whose elements are to be placed into this set
* @throws NullPointerException if the specified collection is null
*/
public HashSet(Collection extends E> c) {
java arraylist，map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
/**
javahashset原理？* Constructs a new, empty set; the backing HashMap instance has
* the specified initial capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the hash map
Java hashset、* @param loadFactor the load factor of the hash map
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive
*/
hashset方法？public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
/**
* Constructs a new, empty set; the backing HashMap instance has
* the specified initial capacity and default load factor (0.75).
*
* @param initialCapacity the initial capacity of the hash table
* @throws IllegalArgumentException if the initial capacity is less
* than zero
*/
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
我們可以觀察到，默認的構造函數指定的初始化容量是16，負載因子是0.75.。也就是說創建了一個長度為16的數組，默認的負載因子為0.75，當達到容量時，map會自動擴容。
而這里的HashMap的是如下：
private transient HashMap map;
可以看到，HashSet中使用的HashMap，key為Set的元素類型，value為Object。
add(E e)
我們來看add方法的實現
/**
* Adds the specified element to this set if it is not already present.
* More formally, adds the specified element e to this set if
* this set contains no element e2 such that
* (e==null???e2==null?:?e.equals(e2)).
* If this set already contains the element, the call leaves the set
* unchanged and returns false.
*
* @param e element to be added to this set
* @return true if this set did not already contain the specified
* element
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
PRESENT的定義
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
我們看到PRESENT是一個靜態的類對象，Object類型。所有HashSet的實例都共享這個對象。
也就是說，我們在向set中添加一個e元素的時候，實際上就是在像map添加一個(e, Object)的鍵值對。我們添加的元素e變成了map中的key，而value則都是Obeject對象。又因為map中key值是唯一的，而value是可以重復的。所以我們添加的e作為key的話，就可以保證添加成功的話，e一定是唯一的。這就實現了set的唯一性。
remove(Object o)
我們接下來看remove的代碼
/**
* Removes the specified element from this set if it is present.
* More formally, removes an element e such that
* (o==null???e==null?:?o.equals(e)),
* if this set contains such an element. Returns true if
* this set contained the element (or equivalently, if this set
* changed as a result of the call). (This set will not contain the
* element once the call returns.)
*
* @param o object to be removed from this set, if present
* @return true if the set contained the specified element
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
我們知道Hashmap中移除一個key的話，會返回這個key值鎖對應的value，而我們這里的map，所有的key的value都是同一個對象PRESENT，所以我們這里只需要判斷map.remove(o)的返回值是不是PRESENT，就可以確定是否成功移除了
iterator()
我們知道hashSet沒有get方法，想要獲取HashSet的元素需要調用iterator()
為什么會這樣呢？
其實只要我們結合HashSet底層是由HashMap實現的就知道，我們添加的元素值都被map當成了key來存儲，顯然沒有從map中獲取單獨一個key的方法，但是我們可以獲取所有key，調用keySet方法即可。
/**
* Returns an iterator over the elements in this set. The elements
* are returned in no particular order.
*
* @return an Iterator over the elements in this set
* @see ConcurrentModificationException
*/
public Iterator iterator() {
return map.keySet().iterator();
}
小結
HashSet由于內部實現是完全基于HashMap的，所以原理較為簡單，代碼也不多，源碼加上注釋也就是300多行。
關于hashSet的實現原理，我們需要掌握一下幾點
hashSet內部用HashMap來存儲元素
HashSet利用本身的值來計算hash值，因為值被當作hashmap的key，而hashmap是利用key來計算hash值的
因為hashset將value當作key來存儲，所以根據map的key值唯一的原理，我們就可以實現set的無重復元素的功能
版权声明：本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间：8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态
