|
在程序中，集合類每天都在使用，以致于某些代碼充斥著List和Map，一直沒有機會整理下它們背后的實現(xiàn)原理。這幾天不太忙，正好可以看會代碼，補充下概念。
和集合類的大致分類類似，下面我也分List,Map和Set來描述。 一． List 1).ArrayList 
ArrayList維護(hù)著一個對象數(shù)組。如果調(diào)用new ArrayList()后，它會默認(rèn)初始一個size=10的數(shù)組。 每次add操作都要檢查數(shù)組容量，如果不夠，重新設(shè)置一個初始容量1.5倍大小的新數(shù)組，然后再把每個元素copy過去。 在數(shù)組中間插入或刪除，都要移動后面的所有元素。（使用System.arraycopy()） 2).LindedList LinkedList的實現(xiàn)是一個雙向鏈表。每個節(jié)點除含有元素外，還包含向前，向后的指針。 新建一個LinkedList，生成一個頭節(jié)點（header，就是一個頭指針），它的元素為null。 
它自包含，next和previous指針都指向自己。 執(zhí)行add(Object obj)方法后，會生成一個新節(jié)點 
Header節(jié)點的next指向鏈表的第一個節(jié)點，previous指向鏈表的最后一個節(jié)點，在這里都是first。 再增加一個對象，它的形狀像下面這樣。 
現(xiàn)在是一個標(biāo)準(zhǔn)的雙向鏈表形狀。每個節(jié)點都有自己的next和previous指針。 增加節(jié)點，只會對鏈表的指針進(jìn)行操作，速度快 LinkedList實現(xiàn)了Deque，所以它有雙向隊列的特征，在鏈表兩端可增刪數(shù)據(jù) 使用index查找對象時，會以index和size/2比較，從前或從后向中間搜索 ListIterator可向前或向后迭代 比較ArrayList和LinkedList的結(jié)構(gòu)，就可以得出： 1． ArrayList的remove和add(index, Object)操作代價高，需要移動后面的每個元素。 2． LinkedList的get(index)操作代價高，它要先循環(huán)遍歷list，找到Object 二． Map 1).HashMap HashMap的結(jié)構(gòu)是一個散列桶，初始化時生成如下結(jié)構(gòu) 
每個bucket包含一個Entry(map自定義的一種結(jié)構(gòu)，包含一個往后的指針)的鏈表。 在put(key, value)后，它的結(jié)構(gòu)如下 
將key的hashcode再次散列，然后用這個hash和length-1進(jìn)行按位與操作，得到bucket的index，然后檢查當(dāng)前bucket的鏈表，有沒有這個key,如果有替換value，沒有則跟在鏈表的最后。 允許key和value都可以是null Index=0的bucket存key=null的value，也可以是其它hashcode為0的項 初始容量必須為2的冪次（我的理解是，在生成index的時候有這樣的代碼:hase ^ (length - 1)），length – 1的二進(jìn)制代碼為全1,則容易進(jìn)行hash的設(shè)計） 如果兩個key散列后的index一樣的話，第一個key生成的Entry先存在桶中，第二個key生成的Entry會將第一個Entry設(shè)為自己的next，串起來。（如圖中，先put(yy, “first”)，會將這個Entry設(shè)為bucket的第一項，后put(xx,”second”)，則生成新Entry，它的next為key為yy的Entry，生成一個鏈表） 在put操作中，會比較threshold（capacity * load_factor，一個臨界值），如果size > threshold的話，生成一個當(dāng)前bucket兩倍數(shù)量的buckets，然后把現(xiàn)有的數(shù)據(jù)重新散列到新bucket中 對HashMap迭代時，返回數(shù)據(jù)的順序是:index從0到length-1，循環(huán)遍歷每個bucket，把不為null的數(shù)據(jù)取出，每個bucket內(nèi)的順序由鏈表的順序決定。而不是由插入數(shù)據(jù)決定。 2).LinkedHashMap 上面說過，Map的迭代不由插入順序決定。如果要保持這種順序呢？就要新增加一種結(jié)構(gòu)來保持。 
LinkedHashMap是HashMap的子類，增加一個雙向鏈表，用來存儲每個新加入的節(jié)點。在遍歷時，按鏈表的順序進(jìn)行。其實差不多就是上面HashMap和LinkedList的和吧。 三． Set 1).HashSet HashSet使用HashMap來保持元素。Key = 元素，value是一個公有的對象，對每個元素都一樣，在HashMap里面key是惟一的，當(dāng)然很適合于構(gòu)造set集合。等同于用HashMap包裝了次，顯示Set自己的特性。 最后還要提到集合類里面一個很重要的類:Collections，它有很多自己獨特的靜態(tài)方法。當(dāng)然它主要提供幾種特殊集合(List, Map,Set)，可以調(diào)用靜態(tài)方法來獲得：Unmodifiable*(不可修改集合，不可添加或刪除元素)，Synchronize*(保持同步集合，它的基本每個方法都加鎖，防止并發(fā)操作)，Checked*(聲明之始傳入特定類型，以后的操作都會驗證加入元素是否屬于已定類型)，Singleton*(集合中只包含一個元素)。它們都是通過包裝集合類中的抽象類獲得，產(chǎn)生不同的行為。 上面是常見的幾種集合類，其它類我很少使用到。 不記得是誰說過，我們最容易記住圖像化的知識。在學(xué)習(xí)了部分集合類知識后，總結(jié)下，以便以后忘記了還能翻看下。 |
|
|
