資源描述：
《java容器學(xué)習(xí)筆記(二)set接口及其實(shí)現(xiàn)類的相關(guān)知識(shí)總結(jié)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。
1、Java容器學(xué)習(xí)筆記（二）Set接口及其實(shí)現(xiàn)類的相關(guān)知識(shí)總結(jié)分類：?Java學(xué)習(xí)?實(shí)習(xí)筆記2011-10-2100:54?652人閱讀?評(píng)論(4)?收藏?舉報(bào)在Java容器學(xué)習(xí)筆記（一）中概述了Collection的基本概念及接口實(shí)現(xiàn)，并且總結(jié)了它的一個(gè)重要子接口List及其子類的實(shí)現(xiàn)和用法。本篇主要總結(jié)Set接口及其實(shí)現(xiàn)類的用法，包括HashSet（無序不重復(fù)），LinkedHashSet（按放入順序有序不重復(fù)），TreeSet（按紅黑樹方式有序不重復(fù)），EnumSet，ConcurrentSkipListSet（來自于java.util.concurrent包），CopyO
2、nWriteArraySet（來自于java.util.concurrent包）等。?2.????Set接口及其實(shí)現(xiàn)類Set接口中方法清單：Set集合和List集合都存放的是單個(gè)元素的序列，但是Set集合不允許集合中有重復(fù)元素（主要依賴于equals方法）。Set接口的父接口為Collection和Iterable，直接實(shí)現(xiàn)該接口的子接口有SortedSet和NavigableSet。實(shí)現(xiàn)Set接口的重要類有HashSet（無序不重復(fù)），LinkedHashSet（按放入順序有序不重復(fù)），TreeSet（按紅黑樹方式有序不重復(fù)），EnumSet，ConcurrentSkipLi
3、stSet（來自于java.util.concurrent包），CopyOnWriteArraySet（來自于java.util.concurrent包）。在Set接口中沒有新增任何方法，所有方法均來自其父接口。它無法提供像List中按位存取的方法。在數(shù)學(xué)上一個(gè)集合有三個(gè)性質(zhì)：確定性，互異性，無序性。???HashSet的特點(diǎn)、實(shí)現(xiàn)機(jī)制及使用方法a)?????HashSet的特點(diǎn)：HashSet中存放的元素是無序的，底層是用HashMap實(shí)現(xiàn)的，其中key是要放入的元素，value是一個(gè)Object類型的名為PRESENT的常量，由于用到了散列函數(shù)，因此其存取速度是非?？斓?，在
4、地址空間很大的情況下它的存取速度可以達(dá)到O(1)級(jí)。如果首先了解了HashMap的實(shí)現(xiàn)方法，那么HashSet的實(shí)現(xiàn)是非常簡單的。b）HashSet的實(shí)現(xiàn)機(jī)制：首先需要了解一下散列或者哈希的用法。我們知道，當(dāng)數(shù)據(jù)量很大時(shí)hash函數(shù)計(jì)算的結(jié)果將會(huì)重復(fù)，按照下圖所示的形式進(jìn)行存貯。在HashSet中有個(gè)loadFactor（負(fù)載因子），對(duì)于上圖所示總共有11個(gè)位置，目前有4個(gè)位置已經(jīng)存放，即40%的空間已被使用。在HashSet的默認(rèn)實(shí)現(xiàn)中，初始容量為16，負(fù)載因子為0.75，也就是說當(dāng)有75%的空間已被使用，將會(huì)進(jìn)行一次再散列（再哈希），之前的散列表（數(shù)組）將被刪除，新增加的散
5、列表是之前散列表長度的2倍，最大值為Integer.MAX_VALUE。負(fù)載因子越高，內(nèi)存使用率越大，元素的尋找時(shí)間越長。負(fù)載因子越低，內(nèi)存使用率越小，元素的尋找時(shí)間越短。從上圖可以看出，當(dāng)哈希值相同時(shí)，將存放在同一個(gè)位置，使用鏈表方式依次鏈接下去。（面試官問到這個(gè)問題，當(dāng)時(shí)我的回答是再哈希，其實(shí)我并不知道HashSet真正是怎么實(shí)現(xiàn)的，我只知道在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)學(xué)習(xí)過再哈希，就是這個(gè)哈希表很滿時(shí)需要重新建立哈希表，以便于存取，因?yàn)榇罅康闹捣旁谝粋€(gè)位置上就變成了鏈表的查詢了，幾乎是O(n/2)級(jí)別的，但是我沒有說出來再哈希的過程，以及哈希值相同時(shí)到底如何存放，所以……~~o(>_
6、<)o~~）。為了說明HashSet在Java中確實(shí)如上實(shí)現(xiàn)，下面附上JDK中兩個(gè)重要方法的源碼：（下面源碼來自于HashMap，原因是HashSet是基于HashMap實(shí)現(xiàn)的）viewplainprint?1./**?1.?????*?Rehashes?the?contents?of?this?map?into?a?new?array?with?a?2.?????*?larger?capacity.??This?method?is?called?automatically?when?the?3.?????*?number?of?keys?in?this?map?reaches
7、?its?threshold.?4.?????*?5.?????*?If?current?capacity?is?MAXIMUM_CAPACITY,?this?method?does?not?6.?????*?resize?the?map,?but?sets?threshold?to?Integer.MAX_VALUE.?7.?????*?This?has?the?effect?of?preventing?future?calls.?8.?????*?9.?????*?@param?newC
