在 JDK1.8 中,HashMap 是由 數組+鏈表+紅黑樹構成,相對于早期版本的 JDK HashMap 實現,新增了紅黑樹作為底層數據結構,在數據量較大且哈希碰撞較多時,能夠極大的增加檢索的效率。了解 HashMap 的具體實現后,我們再來介紹由 HashMap 作為底層數據結構實現的一種數據結構——HashSet。(如果不了解 HashMap 的實現原理,建議先看看 HashMap,不然直接看 HashSet 是很難看懂的)。
1、HashSet 定義
HashSet 是一個由 HashMap 實現的集合。元素無序且不能重復。
public class HashSet< E >
extends AbstractSet< E >
implements Set< E >, Cloneable, java.io.Serializable
和前面介紹的大多數集合一樣,HashSet 也實現了 Cloneable 接口和 Serializable 接口,分別用來支持克隆以及支持序列化。還實現了 Set 接口,該接口定義了 Set 集合類型的一套規范。
2、字段屬性
//HashSet集合中的內容是通過 HashMap 數據結構來存儲的
private transient HashMap< E,Object > map;
//向HashSet中添加數據,數據在上面的 map 結構是作為 key 存在的,而value統一都是 PRESENT
private static final Object PRESENT = new Object();
第一個定義一個 HashMap,作為實現 HashSet 的數據結構;第二個 PRESENT 對象,因為前面講過 HashMap 是作為鍵值對 key-value 進行存儲的,而 HashSet 不是鍵值對,那么選擇 HashMap 作為實現,其原理就是存儲在 HashSet 中的數據 作為 Map 的 key,而 Map 的value 統一為 PRESENT(下面介紹具體實現時會了解)。
3、構造函數
①、無參構造
public HashSet() {
map = new HashMap< >();
}
直接 new 一個 HashMap 對象出來,采用無參的 HashMap 構造函數,具有默認初始容量(16)和加載因子(0.75)。
②、指定初始容量
public HashSet(int initialCapacity) {
map = new HashMap< >(initialCapacity);
}
③、指定初始容量和加載因子
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap< >(initialCapacity, loadFactor);
}
④、構造包含指定集合中的元素
public HashSet(Collection< ? extends E > c) {
map = new HashMap< >(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
集合容量很好理解,這里我介紹一下什么是加載因子。在 HashMap 中,能夠存儲元素的數量就是:總的容量*加載因子 ,新增一個元素時,如果HashMap集合中的元素大于前面公式計算的結果了,那么就必須要進行擴容操作,從時間和空間考慮,加載因子一般都選默認的0.75。
4、添加元素
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
通過 map.put() 方法來添加元素,在上一篇博客介紹該方法時,說明了該方法如果新插入的key不存在,則返回null,如果新插入的key存在,則返回原key對應的value值(注意新插入的value會覆蓋原value值)。
也就是說 HashSet 的 add(E e) 方法,會將 e 作為 key,PRESENT 作為 value 插入到 map 集合中,如果 e 不存在,則插入成功返回 true;如果存在,則返回false。
5、刪除元素
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
調用 HashMap 的remove(Object o) 方法,該方法會首先查找 map 集合中是否存在 o ,如果存在則刪除,并返回該值,如果不存在則返回 null。
也就是說 HashSet 的 remove(Object o) 方法,刪除成功返回 true,刪除的元素不存在會返回 false。
6、查找元素
public boolean contains(Object o) {
return map.containsKey(o);
}
調用 HashMap 的 containsKey(Object o) 方法,找到了返回 true,找不到返回 false。
7、遍歷元素
HashSet< Integer > set = new HashSet< >();
set.add(1);
set.add(2);
//增強for循環
for(Integer i : set){
System.out.println(i);
}
//普通for循環
Iterator< Integer > iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
8、小結
好了,這就是JDK中java.util.HashSet 類的介紹。
-
存儲
+關注
關注
13文章
4298瀏覽量
85812 -
JAVA
+關注
關注
19文章
2966瀏覽量
104707 -
數據結構
+關注
關注
3文章
573瀏覽量
40124 -
JDK
+關注
關注
0文章
81瀏覽量
16594
發布評論請先 登錄
相關推薦
評論