239
SUN核心解析--常規程序編寫--集合類
上次關於JAVA的文章《SUN核心解析--常規程序--基本類》從簡單基本類簡單說名了JAVA的部分原理以及JAVA的底層對於編寫優秀代碼的重要性，但是就知識麵是較窄的，包括今天說的集合類，也隻是皮毛而已，隻是從我個人的角度，由一點點實踐希望可以在這方麵起到一點拋磚引玉的作用，下麵進入正題：
首先我從自己的角度來說，對於JAVA的內存管理思想（因為從我的角度來說不知道內存大致怎麼樣的，學習集合類隻是應付一些常規開發而已，對集合類的底層根本一無所知，也許通過本文對集合類還是不太理解，但是大致原理我相信還是知道一點點的），從抽象角度說就隻有句柄（handle或者叫引用）保存一個實體內存的首地址，隻是實體可能也是一個數組，用它的每一個位置可能會指向其它的位置，逐層連接。其次，不論是什麼集合類，內存管理其實都是基於數組或鏈表或者是兩者的結合的基礎上建立類，定義其一些列屬性和操作方法，成為集合類，所以不要覺得它很神奇，他存在的理由是JAVA是麵向對象的，對於信息的操作完全是進行了封裝，進而達到安全、減少冗餘和錯誤概率等等目，首先下麵給一張JAVA中最直觀簡單的內存管理模式（當然有很多細節，逐步闡述，這裏先闡述一點隻是引開集合類的話題）：
這是一種最簡單的說法，當然大體上可以這樣說明，不過JAVA內部如果要細節分還有：新域、舊域、救助域、永久域，這部分在核心層介紹時進行說明，這裏將整個堆看成一個整體，繼續說明對象數組的管理方式：
記住，這是對象數組的管理方式，也就是數組中每個元素都是一個對象，如果數組中每個元素是基本類型如：int、char、float、double、byte、long、boolean、short、等等，就隻會到第二層(其值直接存儲在數組內部)，尤其像String類型的對象，內部對char數組的管理，是比較特殊的，這裏不說太多東西，目前隻討論集合類，集合類和這種方式唯一的區別就是，在這個基礎上套了一層，也就是在一個類的內部定義了一個數組或者鏈表結構或者樹結構，在這個基礎上提供一係列的插入、修改、刪除、克隆等等方法，以在不同的場合靈活應用達到高效、安全的目的，並且這部分代碼也不用你自己去編寫了（付：之所以寫那麼多集合類，是因為要應對不同的應用場合，在效率和開銷以及安全等角度進行取舍，這個需要細細研究每一種集合類的特性），不論是數組、鏈表、樹結構原理一致，數組保存首地址、鏈表保存頭結點的地址、樹結構保存根節點的地址，這裏就不一一說明，隻是以數組為基礎闡述問題，從個人的角度一般隻抽象為兩個概念：連續的空間和不連續的空間。
我們假象模擬一下一個很簡單集合類的方式：
可能你已經注意到數組下標3和數組下標1指向同一塊內存空間，這是允許的，因為僅僅是保存地址而已，除非在Set集合類裏麵（其實SET內部是用MAP管理的），隻要通過計算後得到的最終KEY值是相同的，後者會替換前者，因為SET的基本規律就是不允許重複數據存在，這裏先拋開Set集合方式，我們主要以集合類最常用的ArrayList和HashMap作為研究對象，順帶簡單提及一些的其他的數據結構。
上述圖形容易讓很多人產生誤解，因為這樣會讓人覺得類對應的實體包含了內部數據的實體，這兩部分在內存分布上其實是分開的（邏輯上可以認為它是在一起的），我們現在拋開是那一種數據結構，假如在自定義類內部定義了基本數據、對象數據、普通類型數組、對象數組、對象鏈表，給一種較全的對象指向關係（不包含樹和圖），任何數據結構我們暫時都可以抽象為數組和鏈表結構，樹和圖在其基礎上有更多的特征，這裏圖形就不展示了，可以自己研究：
這裏簡單說明下，首先看出的是句柄和實體都是分開的，基本數據類型直接存儲，基本類型的數組的值直接存儲在申請的數組空間內，對象類型的數組，數組內部存儲的還是句柄，鏈表結構隻是將存儲句柄的方式改成了鏈表，而沒有將真正的操作實體進行鏈表化，因為實體是你自己定義的，它沒有能力在你的實體內部做一個next句柄來指向下一個節點；學過數據結構的知道，如果結構內的數據經常發生增加、刪除操作，此時鏈表是較好的操作（JAVA中帶Linked開頭的都有使用鏈表結構來完成），因為它不用來回移動元素，而不經常改變這些信息，用於經常定位數據，使用數組級別的列表是較好的選擇，因為數組是通過下標定位句柄位置的（句柄都是存儲地址的信息，以及包含一個所指向實體的類型的tag，所以它存儲的始終是long型的地址信息，我們先拋開類型，如你要獲取a[10]，數組首地址和a[0]一致，那麼a[10]地址自然是a[0]地址+(long的byte長度)）JAVA中long的長度為8個byte位，即64個二進製位。
首先我們要對JAVA常用的集合類的概括和繼承關係要有一個初步的認識，我這裏簡單畫了一個圖形表示常用結合類的接口、對象的繼承和實現關係如下圖所示：
這裏描述了常見集合類的關係，所有類都放在java.util包下，其次，還有Enumeration、Iterator、Dictionary輔助集合類，以及不太常用的Query、AbstractQueue、PriorityQueue、WeakHashMap、LinkedHashSet、EnumMap、EnumSet、ListIterator；另外對於java.util包下麵還有很多非常用的實用類，本文沒有詳細闡述，隻是在必要時候適當攜帶；由於圖形版麵所限，這裏隻是列個大概，實現源碼分析就闡述兩個最常用的ArrayList和HashMap，這兩個結構操作細節有所不同，不過實現底層的結構都是數組，細節可以繼續研究，接下來才進入正題。
第一步，看ArrayList常用的源碼部分：
首先來看下ArrayList屬性定義部分：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
//這裏的E就是在泛型定義時設置的數據類型，說明它也是內部使用數組實現的
private transient E[] elementData;
private int size;//為數組使用的長度，而不是數組實際的長度
然後看下幾個構造方法：
第一個最常用的（看不出任何東西，隻是自己調用另一個帶一個參數的構造方法）：
public ArrayList() {
this(10);
}
第二個構造方法（可以看到調用了父親類，這個父親類方法體是空的，最重要的是，創建了一個長度為指定長度的數組，並強製類型轉換為泛型指定的長度了，通過上一個構造方法可見：若使用new ArrayList()創建，默認情況下即使自己不使用，也會創建10個長度的空間的數組，隻是這些數組存儲的是句柄而已，所以如果你知道數組的長度，此時最好使用new ArrayList(數組實際長度);這樣比較節約空間）：
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
this.elementData = (E[])new Object[initialCapacity];
}
第三個構造方法為通過Collection進行數據拷貝過程，這裏就不多說了，因為和闡述問題的關鍵關係不大，而且這個方法我不是很推薦，經過查看JAVA源碼發現它這段代碼寫得不怎麼樣，在內部調用toArray()的時候，傳入的參數創建了一個大數組進去，結果那個大數組隻是判定一下返回值類型，根本不適用，所以這段句柄空間是浪費的。
看第一個方法（通過方法發現，數組將多餘的空節點去除掉，也就是將數組的長度和實際使用的長度保持一致，這個方法很少使用，因為我們發現它還要申請新的空間去做拷貝，時間和空間上的拷貝都不是那麼樂觀，隻是由於該集合類可能浪費的垃圾空間（創建時就有預留的10個空間）過多，但是想將該集合類長期駐留內存，且幾乎不會改變大小，此時為了節約空間，我們可以采用以下方式，前段申請的句柄將被在適當的時候被回收掉）：
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
Object oldData[] = elementData;
elementData = (E[])new Object[size];
System.arraycopy(oldData, 0, elementData, 0, size);
}
}
再看第二個方法(非常常用的就是獲取集合類實際的使用長度，原來它是一個屬性，至於屬性如何變化，下麵的方法看了自有結論):
public int size() {
return size;
}
這個方法是判定集合類的內部數據是否為空的情況，其實也是判定size屬性，隻是代碼非常幹淨利落。
public boolean isEmpty() {
return size == 0;
}
下麵這個方法貌似看不出什麼(因為是調用另一個方法完成的查看數據是否在集合內部存在，那麼肯定就要看編寫的indexOf方法了)：
public boolean contains(Object elem) {
return indexOf(elem) >= 0;
}
看下indexOf集合類方法吧，返回的是匹配成功的下標（可以看出兩個特征，一個是即使是null也能匹配；其次若不為null對象的匹配使用的是equals，所以當你的集合類內部使用的對象非SUN默認提供的類似於String、Integer、Double等等，那麼需要你自己重寫Object的equals方法，否則它將直接使用Object的該方法，該方法默認對比的是句柄信息，那麼你使用的contains將始終為false）：
public int indexOf(Object elem) {
if (elem == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (elem.equals(elementData[i]))
return i;
}
return -1;
}
對於方法：public int lastIndexOf(Object elem)就不多說，和indexOf區別就是從後向前找而已。
下麵看下克隆方法，這是被很多人忽略的方法，但是也是很好用的方法，我們在數據轉換為保證安全性並快速複製的過程，使用克隆是非常好的選擇;
從第一段代碼看出已經implements Cloneable，隻要我們實現了clone方法，就可以進行克隆了，其實你會發現Cloneable這是一個空接口，這裏可能是比較疑問的一件事情，這裏展開一點小知識：
1、JAVA的記號接口，JAVA中存在很多記號接口，即那些接口是空的，但是他們標記著一定的意義（就像標記一種狀態一樣），內部方法體將根據實現的這些類的實體運行時，必要時做一定的內部控製，如：Serializable是序列號的操作接口，允許你按照以該類所申請的對象為單位進行流的讀寫操作；而實現Cloneable接口的類的實體，在調用clone()方法時認為是合法的，否則會拋出異常：CloneNotSupportedException，這部分是由底層C語言內部機製完成，對外是透明的，因為這部分不允許被重寫。
2、clone()的過程，是形成一個副本，所謂副本就是對實體對象進行了copy，這個過程由Object類內部的本地化方法完成，它實現對實體的內存複製，但是若該實體內部還有定義其它的實體，此時他們定義的句柄將會指向同一塊內存，如下圖所示：
很明顯一個特征就是：當克隆實體進行add、remove等類型操作時，對原實體也會產生影響，所以JAVA必須要對其進行進一步的深度拷貝，在ArrayList內部clone()我們看下源碼是在這樣的：
public Object clone() {
try {
ArrayList<E> v = (ArrayList<E>) super.clone();
v.elementData = (E[])new Object[size];
System.arraycopy(elementData, 0, v.elementData, 0, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
可以看出，克隆後的對象被創建了一個新的數組，新數組的內容通過System.arraycopy將句柄內容拷貝，申請大小為原數組使用的大小size而不是原數組的長度。我們在數據傳送、靜態存儲，可以保證安全性以及轉換的效率，在實際應用中必要時推薦使用，在深度拷貝後，實現的示意圖修改成如下圖所示：
看下toArray()方法吧，有些時候我們也使用：
public Object[] toArray() {
Object[] result = new Object[size];
System.arraycopy(elementData, 0, result, 0, size);
return result;
}
可以見toArray()也是申請了一個新的數組句柄空間，大小為使用的空間大小，並將句柄存儲的值進行拷貝，和克隆有點相似，但是它畢竟是基本類型，而克隆是返回實體對象，在一般情況JAVA中還是支持對象操作，不過數組直接操作也有好處，那就是快，因為你通過源碼讀取發現它還是對數組操作，隻是封裝了一些操作而已，達到安全、封裝、抽象公共操作等的目的。
對於public <T> T[] toArray(T[] a)方法細節的這裏不想多說了，你可以知道一點點使用就是在JDK1.5以後，如果定義了泛型，若toArray()的數據不想逐個強製類型轉換回來就很簡單了，如：
List <String>list = new ArrayList();
list.add("zhongguo");
list.add("meiguo");
String []str = list.toArray(new String[0]);//這一步可以直接返回String類型的數組，不用強製類型轉換了（JDK 1.5）。
看下常用的get方法(RangeCheck方法可以不關心它，它負責進行下標校驗，若不符合規範，則拋出IndexOutOfBoundsException異常，而功能是返回數組內部第index個元素內部值，其實就是該下標值存儲的句柄)：
public E get(int index) {
RangeCheck(index);
return elementData[index];
}
一個不常用的set方法(這個太簡單了，就是改變一個下標的句柄指向):
public E set(int index, E element) {
RangeCheck(index);
E oldValue = elementData[index];
elementData[index] = element;
return oldValue;
}
再看下非常長常用的add方法(發現第二行後，全是句柄複製，那我們最想看的還是ensureCapacity方法，因為它才是處理核心):
public boolean add(E o) {
ensureCapacity(size + 1);
elementData[size++] = o;
return true;
}
那就看一下ensureCapacity方法吧：
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = (E[])new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);
}
}
通過add方法可以看出，傳入的長度為當前使用長度+1，若發現長度比數組的整體長度還要長，那麼就申請一個為以前3/2+1個長度的空間來存儲，但是這塊空間是新的空間，申請後將會將以前的數組句柄部分拷貝到新的空間，那麼以前的空間毫無疑問成為了垃圾空間，而且這些垃圾空間還是句柄指向了一些實體，當這塊空間沒有被回收掉以前，即使使用集合類的clear方法，他們所指向的實體也不會被認為是垃圾內存，實際的數據結構可能還存在多層的現象，那樣會產生更多的句柄指向，JVM有些時候就在考慮其性能的基礎上的算法，就很不容易清楚了，JVM的垃圾空間就是我們這樣不經意間逐步形成的，所以我們要盡量讓他進行內存拷貝和產生垃圾，就最好能提前預知大致的空間長度，用完我們就盡量將它clear()掉，這是最好的習慣，對於clear()文章後麵會詳細介紹。
對於public void add(int index, E element)方法多一步操作就是通過RangeCheck方法校驗位置，在進行插入前要將當前位置後的所有數組向後移動一個位置。
public E remove(int index)源碼也可以自己看下，也很簡單，通過方法RangeCheck校驗下標後，從指定位置起後的數組元素向前移動一個位置，最後一個位置設置為null，數組使用量size減少1。
public boolean remove(Object o)指定對象刪除，其實這個方法看了內部後發現循環和對比過程和indexOf很像，說明要刪除對象，若非普通對象，也需要自己重寫equals方法才行，內部調用了一個fastRemove(int index)方法，它負責刪除，看下源碼：
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null;
}
可以發現沒有使用RangeCheck校驗下標，外部你也會發現你根本沒法使用這個方法，因為他是private類型的，因為它不安全，隻能在內部被調用，被調用以前就會確定下來這個下標必須是存在的。
再看一個推薦使用完集合類使用的但是很多人都很沒有習慣使用的方法：
public void clear() {
modCount++;
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
看起來很簡單，將每個元素的句柄置為null，然後空間為空，其實這是簡單化內存的句柄，因為當你有大量的複製和深度拷貝過程後，通過上麵的方法發現JAVA的結構內部句柄將會非常混亂，很多數組的句柄空間沒有被回收，它所指向的實體空間即使即使目前所指向的集合類進行clear()操作，同樣有一些不可知的句柄指向他們，這樣越來越多就會形成大量的垃圾內存了。
剩下還有一些：addAll、removeRange、RangeCheck、writeObject、readObject等等方法就自己查看源碼吧。
通過上述源碼的分析，每個步驟都應該得出一些編碼的經驗和注意事項，因為很多時候不驚異間就產生了很多的垃圾內存，當然垃圾內存的形成還有很多，這隻是在JAVA中常見的一類而已，後續相關說明中會提及。
對於Vecter來說，你看完源碼後你會發現主要和ArrayList有兩個特點的區別，一個是它進行add和remove操作的時候會對方法體進行synchronized操作，即隻有同一個線程能在一個時候調用同一個實體的同一個方法，即相當於同步一個代碼段（關於線程和同步來說可能會專門說明，內存也分代碼段和數據段，一般我們隻關心數據段，但是如果知道代碼段對實現一些細節的理解更加有幫助），而另一個區別就是當Vecter內部的空間不夠用的時候，新增加空間大小默認情況下是按照2倍增長，但是Vecter可以再創建時設置每次增長的長度大小，增長時判定的條件就是對應的增長數字你是設置為非0，當然默認為0了。
第二部分，HashMap源碼部分：
首先也是看下屬性定義個繼承實現部分：
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
static final int DEFAULT_INITIAL_CAPACITY = 16;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Entry[] table;
transient int size;
int threshold;
final float loadFactor;
transient volatile int modCount;
static final Object NULL_KEY = new Object();
可能發現這些東西看不懂，暫時不用管，暫時知道table是存儲數據的就OK，而Entry是數據類型，其實它是一個內部類，下麵會詳細介紹和說明。
先看第一個默認的構造方法（發現有點暈，大概知道loadFactor被設置為默認值0.75f、threshold 被設置為默認值16*0.75，table申請了一個長度為默認長度16的數組，然後調用一個init()方法，這個方法不用看，是空body，用以擴展的，這裏初步結論是：默認情況下HashMap會給你申請長度為16，類型為Entry的數組）：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
再看下帶一個int參數的空間的構造方法（貌似看不出什麼，帶上自身的一個默認值0.75f，攜帶傳入的參數，調用兩個參數的方法）：
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
看下兩個參數的構造方法體（可以看出第一個參數是用於創建數組大小的，但是這個數組大小並不是和你設置的大小一摸一樣，而是2的多少次方，直到這個2的多少次方大於等於你的參數，否則繼續左移動，其他參數的操作除了一些參數的異常外，就和無參數的一致，當然這裏可以修改loadFactor的大小而已，不過通過異常判定猜出的一點就是：數組的長度應該不能大於MAXIMUM_CAPACITY，這個值為1<<30，即2的30次方為HashMap允許的數組最大長度）：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
對於構造方法：public HashMap(Map<? extends K, ? extends V> m)也不必多提了。
另外對於size()、isEmpty()、clear()、clone()方法和ArrayList的實現思路差不多，不必多提，我們這裏主要還是說明下插入刪除等方法吧。
首先看插入（這段看懂幾乎整個HashMap的實現機製都明白了，第一行maskNull(key)是對傳入KEY的空值轉轉換為前序定義的：NULL_KEY，其次hash(k)是根據將空值判定後的計算出一個hash值，indexFor將會按位求與的方式得到一個所在的數組下標（同一個節點存儲多個元素時使用Entry對象的next屬性做鏈表），得到對應下標後，即為一個Entry鏈表的首地址，開始循環遍曆該鏈表，若存在某hash的值與傳入key的hash值相同，則替換數據，所以它沒有重複的key，當沒有發現時，調用addEntry方法新增數組節點來完成，後續說明）：
public V put(K key, V value) {
K k = maskNull(key);
int hash = hash(k);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
if (e.hash == hash && eq(k, e.key)) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, k, value, i);
return null;
}
上述需要調用的內部方法：
static <T> T maskNull(T key) {
return key == null ? (T)NULL_KEY : key;
}
static int hash(Object x) {
int h = x.hashCode();
h += ~(h << 9);
h ^= (h >>> 14);
h += (h << 4);
h ^= (h >>> 10);
return h;
}
static int indexFor(int h, int length) {
return h & (length-1);
}
而對於addEntry方法實現如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
說明創建了一個新的Entry結點，並放入當前使用的最後一個index後麵，如果發現size>=threshold則申請以前二倍的空間（resize我們不看都知道要申請以前2倍的空間）那麼threshold是什麼，就是在初始化的時候設置的信息，等價於數組長度*0.75f，當然這個0.75f是可以被修改的；這個new Entry貌似有些奇怪，好像就直接由數組指向他就完了，那麼其他的鏈表結構呢，看下new Entry這個內部類的構造方法就知道了，因為它傳入了一個e，而e是在賦值以前得到原來數組所指向的Entry節點，此時將e賦值進去後，會成為這個新生成的Entry的next節點句柄，它就這樣形成鏈表了。
而resize方法內部會申請空間，因為申請空間部分都差不多，所以不多提，它有一個特殊的操作，還會做一個transfer()操作，為什麼它不直接使用像ArrayList一樣的數組拷貝呢？從前麵可以看到當進行put操作的時候，會根據數組的長度計算數組的下標，當數組的長度發生變化時，計算出來的下標就不一樣了，否則當長度發生變化時，通過你的key就找不到對應的數據了。這個transfer操作除了進行句柄的複製以外，還需要重新計算每一個KEY在結構中的位置，所以其開銷是非常大的，尤其當這個HashMap比較大的時候，所以還是如果知道HashMap的大，盡量提前預知為實際的4/3，因為你會發現，當最壞的情況數組長度和節點個數一致，但是這種情況是我們查詢的時候最理想的，因為所有節點直接就是鏈表的第一個節點，通過hash值幾乎可以直接定位數據，而不需要繼續遍曆鏈表，其實0.75的概率也是一個計算出來的較為常用的值，它將形成鏈表的概率降低得很低，因為數組的長度就比實際的元素個數要多很多，這是算法中典型的用空間換取時間的概念，數組長度為12時，就會申請32個空間，當長度為24時就需要申請64個空間，這在程序中很多地方我們都是可以控製的。
通過上述發現，HashMap內部存放的數據是將KEY轉換指定的hash值後得到的，所以在查找數據的時候非常迅速因為對比hash值是基本直接定位到數組的的下標的，鏈表的長度一般不會太長，所以hash的查找算法可以使用O(1)來說明，所以提供了一個方法（查找數據是否存在這個方法是很快速的，而且key值不用重寫equals方法，因為不是比較對象值，而是計算出的hash信息）：
public boolean containsKey(Object key) {
Object k = maskNull(key);
int hash = hash(k);
int i = indexFor(hash, table.length);
Entry e = table[i];
while (e != null) {
if (e.hash == hash && eq(k, e.key))
return true;
e = e.next;
}
return false;
}
另外有一個default範圍類型的獲取對象方法：Entry<K,V> getEntry(Object key)獲取方法類似，對於remove操作其實這裏說沒多大意義，因為remove操作隻是在對應數組所指向的鏈表中找到對應的對象，鏈表刪除節點是很簡單的過程。
上述hash曾經讓我產生過聯想，因為hash值是int類型的，所以在很多對象做equals比較的時候，是否可以用hash值來判定呢？首先為了不引起誤解確定一下，這個肯定是不成立的，雖然有結果，但是得不償失；還是以上次說過的String來說吧，跟進去源碼可以看到，通過hashCode方法獲取字符串的hash值是需要逐個字符遍曆，當兩個字符串比較時，要進行兩次循環，這樣的開銷還不如直接用equals呢，因為equals內部可能不會循環遍曆字符串，最多循環也隻會循環一次；另外即使為不同的對象，計算出的hash值是有可能重複的，就像剛才的HashMap一樣，當遇到重複的，就存儲在一個鏈表中（數據結構中把這個鏈表叫做桶），所以基本可以不用考慮用hash值來比較對象。
對於這部分最後需要注意的是，上述未key值的比較，HashMap內部隻會對key進行轉換，而不會對值進行hash轉換，所以當你使用public boolean containsValue(Object value)方法的時候，同樣要保證值所在對象已經重寫了equals方法，內部還包含很多其他的方法，這裏就不一一列舉了，可以自行查看的，總之我們數據結構總體上可以抽象的分為數組結構和鏈表結構（即連續句柄存儲、非連續句柄存儲），通過組合和操作方式我們可以實現更為複雜的結構；從邏輯層來說，實現了向量、隊列、棧、動態數組列表、樹、集合、鍵值對、枚舉、迭代器；按照JAVA提供的對象。
數據結構常規操作，對於List的常用循環：
先定義一個測試結合類：
List <String>list = new ArrayList<String>(3);
list.add("中國");
list.add("美國");
list.add("俄羅斯");
迭代循環測試輸出：
for(Iterator <String>iterator = list.iterator();iterator.hasNext();) {
String str = iterator.next();
System.out.println(str);
}
增強循環：
for (String str : list) {
System.out.println(str);
}
按照下標遍曆（注意分號的位置，在初始的時候先將長度獲取出來）：
for (int index = 0, count = list.size(); index < count;) {
System.out.println(list.get(index++));
}
對於Vecter還有一種使用Enumeration來迭代循環的方式：
Vector <String>vec = new Vector<String>();
vec.add("中國");
vec.add("美國");
vec.add("俄羅斯");
Enumeration <String>em = vec.elements();
while(em.hasMoreElements()) {
String str = em.nextElement();
System.out.println(str);
}
對於HashMap遍曆常見有以下三種方式（可以根據實際情況將三種情況演化為根據上述同結構遍曆的3*3種方式，這裏全部用迭代器去做了）：
也先申請一個對象
Map <String,String>map = new HashMap<String,String>(4);
map.put("NO1", "中國");
map.put("NO2", "美國");
1.按照鍵去遍曆：
for(Iterator <String>iterator = map.keySet().iterator();iterator.hasNext();) {
String key = iterator.next();
System.out.println("key="+key+",value="+map.get(key));
}
2.按照值去遍曆（但僅僅隻能遍曆出值）：
for(Iterator <String>iterator = map.values().iterator();iterator.hasNext();) {
System.out.println(iterator.next());
}
3.將節點對象遍曆出來（這個操作外部可以被修改，所以不是那麼安全）：
for(Iterator<Map.Entry<String,String>>iterator = map.entrySet().iterator();iterator.hasNext();) {
Map.Entry<String,String> entry = iterator.next();
System.out.println("key="+entry.getKey()+",value="+entry.getValue());
}
為了闡述克隆的說法，最後做一個簡單的實驗，首先創建一個類為繼承克隆類定義類CloneInfo：
class CloneInfo implements Cloneable {
private String[] str = new String[2];
public CloneInfo() {
str[0] = new String("a");
str[1] = new String("b");
}
public void setInfo(String a, String b) {
str[0] = a;
str[1] = b;
}
public Object clone() {
CloneInfo temp = null;
try {
temp = (CloneInfo) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
return temp;
}
public String toString() {
return str[0] + "/t" + str[1];
}
}
在定義一個測試類：
public class CloneTest {
public static void main(String[] agrs) {
CloneInfo info1 = new CloneInfo();
CloneInfo info2 = (CloneInfo) info1.clone();
info2.setInfo("c", "d");
System.out.println(info1.toString());
}
}
發現輸出為：
c d
為什麼對info2克隆對象進行修改，info1對象也被修改，因為它隻進行了淺拷貝，實現深入拷貝需要我們自己去完成，將public Object clone()方法體做如下修改：
public Object clone() {
CloneInfo temp = null;
try {
temp = (CloneInfo) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
temp.str = new String[this.str.length];
System.arraycopy(str, 0, temp.str, 0, str.length);
return temp;
}
此時再次允許測試類輸出：
a b
說明對info2進行修改，對info1已經沒有影響了，這隻是一個例子為說明問題而已，對於實際情況，如上述數組存儲的是StringBuilder仍然會相互影響，當然就看要求了，若要求完全不影響需要進進一步對每一個StringBuilder克隆過來。
本文最後小小擴展部分：
很多時候我們習慣將很多幾乎在運行過程中不會頻繁改變的列表數據放於內存靜態存儲，作為共享對象提供給大家提取和使用，假如我們使用ArrayList來存放，如果直接將這個實體的句柄返回給調用代碼的程序設計人員，它們的代碼裏麵就可以對這個ArrayList的內容進行修改，如進行一些add、remove等等操作(框架本身有能力對其進行內部的修改操作)，但是如果複製一份內存出去顯得比較浪費空間，當然你可以告訴每一個程序員，這樣得到的List隻允許查不允許修改，但是人總有疏忽的時候，我們這部分可以再框架內部去完成，這裏我們繼承於ArrayList做一些控製級別的重寫（這裏可能有人會認為用final定義List，其實可以做一下試驗就知道final隻能保證不然集合類第二次被賦值，不能保證其內部實體的修改，另外即使保證內部實體不被修改，但是這裏要求框架本身有修改這個集合類的能力，所以這個方法很明顯是不可以行的了）：
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.RandomAccess;
public class MyArrayList<E> extends ArrayList<E> implements List<E>,
RandomAccess, Cloneable, java.io.Serializable {
/**
* serialVersionUID
*/
private static final long serialVersionUID = 1765158294150418629L;
/**
* 是否已經鎖定記錄不允許被修改，true不能被修改
*/
private boolean islocked = false;
/**
* 設置islocked
*/
public void setLocked(boolean islocked) {
this.islocked = islocked;
}
/**
* 通過數量初始化
*/
public MyArrayList(int initialCapacity) {
super(initialCapacity);
}
/**
* 直接初始化
*/
public MyArrayList() {
super(10);
}
/**
* 對應值修改
*/
public E set(int index, E element) {
if(!islocked) {
return super.set(index, element);
}
return null;
}
/**
* add方法
*/
public boolean add(E o) {
if(!islocked) {
return super.add(o);
}
return false;
}
/**
* add方法 帶index下標
*/
public void add(int index, E element) {
if(!islocked) {
super.add(index, element);
}
}
/**
* 重寫remove方法
*/
public E remove(int index) {
if(!islocked) {
return super.remove(index);
}
return null;
}
/**
* 重寫remove方法2
*/
public boolean remove(Object o) {
if(!islocked) {
return super.remove(o);
}
return false;
}
/**
* 重寫addAll方法
*/
public boolean addAll(Collection<? extends E> c) {
if(!islocked) {
return super.addAll(c);
}
return false;
}
/**
* 重寫addAll方法2
*/
public boolean addAll(int index, Collection<? extends E> c) {
if(!islocked) {
return super.addAll(index, c);
}
return false;
}
/**
* 清空列表
*/
public void clear() {
if(!islocked) {
super.clear();
}
}
}
此時集合類已經被重寫，需要定義一個調用類，這部分代碼一般在框架部分就需要完成：
import java.util.List;
public class TestMyArrayList {
//定義一個靜態的MyArrayList
private static MyArrayList<String> myList = new MyArrayList<String>();
//初始化模擬幾條數據進去
static {
myList.add("張三");
myList.add("李四");
myList.setLocked(true);//設置共享對象不可以被修改
}
//直接獲取原始的List列表信息，通過上溯造型，避免外部調用控製體結構
public static List<String> getList() {
return myList;
}
//獲取克隆後的List信息
@SuppressWarnings("unchecked")
public static List<String> getCloneList() {
MyArrayList<String>list = (MyArrayList<String>)myList.clone();
list.setLocked(false);//通過克隆獲取到的列表，允許被修改
return list;
}
}
下麵測試調用一下：
public static void main(String[] args) {
System.out.println("通過[克隆調用]後，嚐試刪除掉一條數據後，顯示列表內容如下：");
List<String> list2 = getCloneList();
list2.remove(1);
for (String str : list2) {
System.out.println(str);
}
System.out.println("通過[直接獲取]後，嚐試清空數據後，顯示列表內容如下：");
List<String> list = getList();
list.clear();
for (String str : list) {
System.out.println(str);
}
}
輸出結果：
通過[克隆調用]後，嚐試刪除掉一條數據後，顯示列表內容如下：
張三
通過[直接獲取]後，嚐試清空數據後，顯示列表內容如下：
張三
李四
通過結果可以看出，通過克隆後的數據可以被修改，通過原始獲取的達到我們要的目的，不能被業務調用代碼修改，隻能被框架代碼通過MyArrayList來修改，這部分對於程序設計人員是私有的，程序設計人員可能絕大部分調用這部分數據的時候不會被修改，可以直接調用也保證數據的安全性；部分特殊情況需要做相應的轉換可以通過調用克隆方法。
補充，這裏調用克隆方法雖然使用了默認的深度克隆，但是內部存儲的是String類型，它作為一種常量對象被管理，所以不需要對實際對象深度克隆，如內部存儲的是對象，需要對對象進行進一步克隆才可以保證對象內容不被修改，這個對象也必須implements Cloneable，並實現clone方法，對內容進行克隆，這個需要根據實際情況而定了。
最後更新：2017-04-02 05:21:03