Java集合類關(guān)系圖整理
“脫掉HashSet的外衣“
構(gòu)造函數(shù)
- 默認(rèn)構(gòu)造器
將傳入的集合添加到HashSet的構(gòu)造器
public?HashSet()?{
????????map?=?new?HashMap<>();
????}- 將傳入的集合添加到HashSet的構(gòu)造器
public?HashSet(Collection<??extends?E>?c)?{
????????map?=?new?HashMap<>(Math.max((int)?(c.size()/.75f)?+?1,?16));
????????addAll(c);
}- 明確初始容量和裝載因子的構(gòu)造器
public?HashSet(int?initialCapacity,?float?loadFactor)?{
????????map?=?new?HashMap<>(initialCapacity,?loadFactor);
????}- 僅明確初始容量的構(gòu)造器（裝載因子默認(rèn)0.75）
?public?HashSet(int?initialCapacity)?{
????????map?=?new?HashMap<>(initialCapacity);
?}脫掉HashSet的外衣之后 發(fā)現(xiàn)里面是HashMap
新增元素
private?static?final?Object?PRESENT?=?new?Object();
public?boolean?add(E?e)?{
????????return?map.put(e,?PRESENT)==null;
????}HashSet添加的元素是存放在HashMap的key位置上，而value取了默認(rèn)常量PRESENT，是一個(gè)空對(duì)象
-
一個(gè)HashMap中是16個(gè)默認(rèn)容量元素的陣列-每個(gè)區(qū)塊對(duì)應(yīng)于不同的哈希碼值
-
如果各種對(duì)象具有相同的哈希碼值咨演，則它們將存儲(chǔ)在單個(gè)存儲(chǔ)buckets
-
如果達(dá)到了加載因子孝宗，則會(huì)創(chuàng)建一個(gè)新數(shù)組讨盒，該數(shù)組的大小是前一個(gè)數(shù)組的兩倍亿昏，并且所有元素都會(huì)被重新分散并在新的相應(yīng)存儲(chǔ)塊中并重新分配
-
要檢索一個(gè)值，我們對(duì)一個(gè)鍵進(jìn)行哈希處理霹陡，對(duì)其進(jìn)行修改憋槐，然后轉(zhuǎn)到相應(yīng)的存儲(chǔ)塊双藕，并在存在多個(gè)對(duì)象的情況下搜索潛在的鏈表
刪除元素
removeNode
特點(diǎn)
-
存儲(chǔ)唯一元素并允許空值
-
由HashMap支持
-
不保持插入順序
-
不是線程安全的
HashSet如何保持唯一性
-
將一個(gè)對(duì)象放入一個(gè)HashSet時(shí)，它使用該對(duì)象的hashcode值來(lái)確定一個(gè)元素是否已經(jīng)在該集合中
-
每個(gè)散列碼值對(duì)應(yīng)于某個(gè)塊位置秦陋，該塊位置可以包含計(jì)算出的散列值相同的各種元素
-
具有相同hashCode的兩個(gè)對(duì)象可能不相等蔓彩。因此治笨，將使用equals（）方法比較同一存儲(chǔ)桶中的對(duì)象
HashSet的性能
HashSet的性能主要受兩個(gè)參數(shù)影響 - 初始容量和負(fù)載因子
將元素添加到集合的預(yù)期時(shí)間復(fù)雜度是O（1）驳概，在最壞的情況下（僅存在一個(gè)存儲(chǔ)桶）可以降至O（n） - 因此，維護(hù)正確的HashSet容量至關(guān)重要
從JDK 8開(kāi)始旷赖，最壞的情況時(shí)間復(fù)雜度為O（log * n）
較低的初始容量降低了空間復(fù)雜性顺又，但增加了重新散布的頻率
根據(jù)經(jīng)驗(yàn)：
-
高初始容量適用于大量條目，幾乎沒(méi)有迭代
-
低初始容量適用于具有大量迭代的少數(shù)條目
結(jié)語(yǔ)
HashSet具有恒定的時(shí)間性能和避免重復(fù)的能力 只有深入了解它等孵，才能更好的使用它
