ArrayList LinkedList与HashMap 实现原理
ArrayList
定義
快速了解ArrayList究竟是什么的一個好方法就是看JDK源碼中對ArrayList類的注釋，大致翻譯如下：
/** * 實現(xiàn)了List的接口的可調(diào)整大小的數(shù)組。實現(xiàn)了所有可選列表操作，并且允許所有類型的元素，* 包括null。除了實現(xiàn)了List接口，這個類還提供了去動態(tài)改變內(nèi)部用于存儲集合元素的數(shù)組尺寸* 的方法。（這個類與Vector類大致相同，除了ArrayList是非線程安全外。）size，isEmpty，* get，set，iterator，和listIterator方法均為常數(shù)時間復(fù)雜度。add方法的攤還時間復(fù)雜度為* 常數(shù)級別，這意味著，添加n個元素需要的時間為O(n)。所有其他方法的時間復(fù)雜度都是線性級別的。* 常數(shù)因子要比LinkedList低。* 每個ArrayList實例都有一個capacity。capacity是用于存儲ArrayList的元素的內(nèi)部數(shù)組的大小。* 它通常至少和ArrayList的大小一樣大。當(dāng)元素被添加到ArrayList時，它的capacity會自動增長。* 在向一個ArrayList中添加大量元素前，可以使用ensureCapacity方法來增加ArrayList的容量。* 使用這個方法來一次性地使ArrayList內(nèi)部數(shù)組的尺寸增長到我們需要的大小提升性能。需要注意的* 是，這個ArrayList實現(xiàn)是未經(jīng)同步的。若在多線程環(huán)境下并發(fā)訪問一個ArrayList實例，并且至少* 一個線程對其作了結(jié)構(gòu)型修改，那么必須在外部做同步。（結(jié)構(gòu)性修改指的是任何添加或刪除了一個或* 多個元素的操作，以及顯式改變內(nèi)部數(shù)組尺寸的操作。set操作不是結(jié)構(gòu)性修改）在外部做同步通常通* 過在一些自然地封裝了ArrayList的對象上做同步來實現(xiàn)。如果不存在這樣的對象，ArrayList應(yīng)* 使用Collections.synchronizedList方法來包裝。最好在創(chuàng)建時就這么做，以防止對ArrayList* 無意的未同步訪問。（List list = Collections.synchronizedList(new ArrayList(...));）* ArrayList類的iterator()方法以及l(fā)istIterator()方法返回的迭代器是fail-fast的：* 在iterator被創(chuàng)建后的任何時候，若對list進行了結(jié)構(gòu)性修改（以任何除了通過迭代器自己的* remove方法或add方法的方式），迭代器會拋出一個ConcurrentModificationException異常。* 因此，在遇到并發(fā)修改時，迭代器馬上拋出異常，而不是冒著以后可能在不確定的時間發(fā)生不確定行為* 的風(fēng)險繼續(xù)。需要注意的是，迭代器的fail-fast行為是不能得到保證的，因為通常來說在未同步并發(fā)* 修改面前無法做任何保證。fail-fast迭代器會盡力拋出ConcurrentModificationException異常。* 因此，編寫正確性依賴于這個異常的程序是不對的：fail-fast行為應(yīng)該僅僅在檢測bugs時被使用。* ArrayList類是Java集合框架中的一員。 */根據(jù)源碼中的注釋，我們了解了ArrayList用來組織一系列同類型的數(shù)據(jù)對象，支持對數(shù)據(jù)對象的順序迭代與隨機訪問。我們還了解了ArrayList所支持的操作以及各項操作的時間復(fù)雜度。接下來我們來看看這個類實現(xiàn)了哪些接口。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable我們可以看到，它實現(xiàn)了4個接口：List、RandomAccess、Cloneable、Serializable。
官方文檔對List接口的說明如下：List是一個有序的集合類型（也被稱作序列）。使用List接口可以精確控制每個元素被插入的位置，并且可以通過元素在列表中的索引來訪問它。列表允許重復(fù)的元素，并且在允許null元素的情況下也允許多個null元素。
List接口定義了以下方法：
我們可以看到，add、get等方法都是我們在使用ArrayList時經(jīng)常用到的。
在ArrayList的源碼注釋中提到了，ArrayList使用Object數(shù)組來存儲集合元素。我們來一起看下它的源碼中定義的如下幾個字段：
通過以上字段，我們驗證了ArrayList內(nèi)部確實使用一個Object數(shù)組來存儲集合元素。
那么接下來我們看一下ArrayList都有哪些構(gòu)造器，從而了解ArrayList的構(gòu)造過程。
ArrayList的構(gòu)造器
首先我們來看一下我們平時經(jīng)常使用的ArrayList的無參構(gòu)造器的源碼：
/** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }我們可以看到，無參構(gòu)造器僅僅是把ArrayList實例的elementData字段賦值為DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
接下來，我們再來看一下ArrayList的其他構(gòu)造器：
通過源碼我們可以看到，第一個構(gòu)造器指定了ArrayList的初始capacity，然后根據(jù)這個初始capacity創(chuàng)建一個相應(yīng)大小的Object數(shù)組。若initialCapacity為0，則將elementData賦值為EMPTY_ELEMENTDATA；若initialCapacity為負數(shù)，則拋出一個IllegalArgumentException異常。
第二個構(gòu)造器則指定一個Collection對象作為參數(shù)，從而構(gòu)造一個含有指定集合對象元素的ArrayList對象。這個構(gòu)造器首先把elementData實例域賦值為集合對象轉(zhuǎn)為的數(shù)組，而后再判斷傳入的集合對象是否不含有任何元素，若是的話，則將elementData賦值為EMPTY_ELEMENTDATA；若傳入的集合對象至少包含一個元素，則進一步判斷c.toArray方法是否正確返回了Object數(shù)組，若不是的話，則需要用Arrays.copyOf方法把elementData的元素類型改變?yōu)镺bject。
現(xiàn)在，我們又了解了ArrayList實例的構(gòu)建過程，那么接下來我們來通過ArrayList的get、set等方法的源碼來進一步了解它的實現(xiàn)原理。
add方法源碼分析
/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }我們可以看到，在add方法內(nèi)部，首先調(diào)用了ensureCapacityInternal(size+1)，這句的作用有兩個：
- 保證當(dāng)前ArrayList實例的capacity足夠大；
- 增加modCount，modCount的作用是判斷在迭代時是否對ArrayList進行了結(jié)構(gòu)性修改。
然后通過將內(nèi)部數(shù)組下一個索引處的元素設(shè)置為給定參數(shù)來完成了向ArrayList中添加元素，返回true表示添加成功。
get方法源碼分析
/** * Returns the element at the specified position in this list. * * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { rangeCheck(index); return elementData(index); }首先調(diào)用了rangeCheck方法來檢查我們傳入的index是否在合法范圍內(nèi)，然后調(diào)用了elementData方法，這個方法的源碼如下：
E elementData(int index) { return (E) elementData[index]; }set方法源碼分析
/** * Replaces the element at the specified position in this list with * the specified element. * * @param index index of the element to replace * @param element element to be stored at the specified position * @return the element previously at the specified position * @throws IndexOutOfBoundsException {@inheritDoc} */ public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; }我們可以看到，set方法的實現(xiàn)也很簡單，首先檢查給定的索引是否在合法范圍內(nèi)，若在，則先把該索引處原來的元素存儲在oldValue中，然后把新元素放到該索引處并返回oldValue即可。
LinkedList
定義
LinkedList類源碼中的注釋如下：
/** * 實現(xiàn)了List接口的雙向鏈表。實現(xiàn)了所有可選列表操作，并且可以存儲所有類型的元素，包括null。* 對LinkedList指定索引處的訪問需要順序遍歷整個鏈表，直到到達指定元素。* 注意LinkedList是非同步的。若多線程并發(fā)訪問LinkedList對象，并且至少一個線程對其做* 結(jié)構(gòu)性修改，則必須在外部對它進行同步。這通常通過在一些自然封裝了LinkedList的對象上* 同步來實現(xiàn)。若不存在這樣的對象，這個list應(yīng)使用Collections.synchronizedList來包裝。 * 這最好在創(chuàng)建時完成，以避免意外的非同步訪問。* LinkedList類的iterator()方法以及l(fā)istIterator()方法返回的迭代器是fail-fast的：* 在iterator被創(chuàng)建后的任何時候，若對list進行了結(jié)構(gòu)性修改（以任何除了通過迭代器自己的* remove方法或add方法的方式），迭代器會拋出一個ConcurrentModificationException異常。* 因此，在遇到并發(fā)修改時，迭代器馬上拋出異常，而不是冒著以后可能在不確定的時間發(fā)生不確定行為* 的風(fēng)險繼續(xù)。需要注意的是，迭代器的fail-fast行為是不能得到保證的，因為通常來說在未同步并發(fā)* 修改面前無法做任何保證。fail-fast迭代器會盡力拋出ConcurrentModificationException異常。* 因此，編寫正確性依賴于這個異常的程序是不對的：fail-fast行為應(yīng)該僅僅在檢測bugs時被使用。* LinkedList類是Java集合框架中的一員。 */LinkedList是對鏈表這種數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)（對鏈表還不太熟悉的小伙伴可以參考深入理解數(shù)據(jù)結(jié)構(gòu)之鏈表），當(dāng)我們需要一種支持高效刪除/添加元素的數(shù)據(jù)結(jié)構(gòu)時，可以考慮使用鏈表。
總的來說，鏈表具有以下兩個優(yōu)點：
- 插入及刪除操作的時間復(fù)雜度為O(1)
- 可以動態(tài)改變大小
鏈表主要的缺點是：由于其鏈?zhǔn)酱鎯Φ奶匦?#xff0c;鏈表不具備良好的空間局部性，也就是說，鏈表是一種緩存不友好的數(shù)據(jù)結(jié)構(gòu)。
支持的操作
LinkedList主要支持以下操作：
void addFirst(E element); void addLast(E element); E getFirst(); E getLast(); E removeFirst(); E removeLast(); boolean add(E e) //把元素e添加到鏈表末尾 void add(int index, E element) //在指定索引處添加元素以上操作除了add(int index, E element)外，時間復(fù)雜度均為O(1)，而add(int index, E element)的時間復(fù)雜度為O(N)。
Node類
在LinkedList類中我們能看到以下幾個字段：
transient int size = 0; /** * 指向頭結(jié)點 */ transient Node<E> first; /** * 指向尾結(jié)點 */ transient Node<E> last;我們看到，LinkedList只保存了頭尾節(jié)點的引用作為其實例域，接下來我們看一下LinkedList的內(nèi)部類Node的源碼如下：
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }每個Node對象的next域指向它的下一個結(jié)點，prev域指向它的上一個結(jié)點，item為本結(jié)點所存儲的數(shù)據(jù)對象。
addFirst源碼分析
/** * Inserts the specified element at the beginning of this list. * * @param e the element to add */ public void addFirst(E e) { linkFirst(e); }實際干活的是linkFirst，它的源碼如下：
/** * Links e as first element. */ private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }首先把頭結(jié)點引用存于變量f中，而后創(chuàng)建一個新結(jié)點，這個新結(jié)點的數(shù)據(jù)為我們傳入的參數(shù)e，prev指針為null，next指針為f。然后把頭結(jié)點指針指向新創(chuàng)建的結(jié)點newNode。而后判斷f是否為null，若為null，說明之前鏈表中沒有結(jié)點，所以last也指向newNode；若f不為null，則把f的prev指針設(shè)為newNode。最后還需要把size和modCount都加一，modCount的作用與在ArrayList中的相同。
getFirst方法源碼分析
/** * Returns the first element in this list. * * @return the first element in this list * @throws NoSuchElementException if this list is empty */ public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; }這個方法的實現(xiàn)很簡單，主需要直接返回first的item域（當(dāng)first不為null時），若first為null，則拋出NoSuchElementException異常。
removeFirst方法源碼分析
/** * Removes and returns the first element from this list. * * @return the first element from this list * @throws NoSuchElementException if this list is empty */ public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }unlinkFirst方法的源碼如下：
/** * Unlinks non-null first node f. */ private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; }add(int index, E e)方法源碼分析
/** * Inserts the specified element at the specified position in this list. * Shifts the element currently at that position (if any) and any * subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }這個方法中，首先調(diào)用checkPositionIndex方法檢查給定index是否在合法范圍內(nèi)。然后若index等于size，這說明要在鏈表尾插入元素，直接調(diào)用linkLast方法，這個方法的實現(xiàn)與之前介紹的linkFirst類似；若index小于size，則調(diào)用linkBefore方法，在index處的Node前插入一個新Node（node(index)會返回index處的Node）。linkBefore方法的源碼如下：
/** * Inserts element e before non-null Node succ. */ void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }我們可以看到，在知道要在哪個結(jié)點前插入一個新結(jié)點時，插入操作是很容易的，時間復(fù)雜度也只有O(1)。下面我們來看一下node方法是如何獲取指定索引處的Node的：
/** * Returns the (non-null) Node at the specified element index. */ Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }首先判斷index位于鏈表的前半部分還是后半部分，若是前半部分，則從頭結(jié)點開始遍歷，否則從尾結(jié)點開始遍歷，這樣可以提升效率。我們可以看到，這個方法的時間復(fù)雜度為O(N)。
HashMap
Map接口
我們先來看下它的定義：
一個把鍵映射到值的對象被稱作一個映射表對象。映射表不能包含重復(fù)的鍵，每個鍵至多可以與一個值關(guān)聯(lián)。Map接口提供了三個集合視圖：鍵的集合視圖、值的集合視圖以及鍵值對的集合視圖。一個映射表的順序取決于它的集合視圖的迭代器返回元素的順序。一些Map接口的具體實現(xiàn)（比如TreeMap）保證元素有一定的順序，其它一些實現(xiàn)（比如HashMap）則不保證元素在其內(nèi)部有序。
也就是說，Map接口定義了一個類似于“字典”的規(guī)范，讓我們能夠根據(jù)鍵快速檢索到它所關(guān)聯(lián)的值。我們先來看看Map接口定義了哪些方法：
void clear() boolean containsKey(Object key) //判斷是否包含指定鍵 boolean containsValue(Object value) //判斷是否包含指定值 boolean isEmpty() V get(Object key) //返回指定鍵映射的值 V put(K key, V value) //放入指定的鍵值對 V remove(Object key) int size() Set<Map.Entry<K,V>> entrySet() Set<K> keySet() Collection<V> values()HashMap的定義
HashMap<K, V>是基于哈希表這個數(shù)據(jù)結(jié)構(gòu)的Map接口具體實現(xiàn)，允許null鍵和null值（最多只允許一個key為null，但允許多個value為null）。這個類與HashTable近似等價，區(qū)別在于HashMap不是線程安全的并且允許null鍵和null值。由于基于哈希表實現(xiàn)，所以HashMap內(nèi)部的元素是無序的。HashMap對與get與put操作的時間復(fù)雜度是常數(shù)級別的（在散列均勻的前提下）。對HashMap的集合視圖進行迭代所需時間與HashMap的capacity（bucket的數(shù)量）加上HashMap的尺寸（鍵值對的數(shù)量）成正比。因此，若迭代操作的性能很重要，不要把初始capacity設(shè)的過高（不要把load factor設(shè)的過低）。
（對散列表（哈希表）這種數(shù)據(jù)結(jié)構(gòu)還不太熟悉的小伙伴請戳這里散列表的原理與實現(xiàn)）
有兩個因素會影響一個HashMap的性能：intial capacity（初始容量）和load factor（負載因子）。intial capacity就是HashMap對象剛創(chuàng)建時其內(nèi)部的哈希表的“桶”的數(shù)量。load factor等于maxSize / capacity，也就是HashMap所允許的最大鍵值對數(shù)與桶數(shù)的比值。增大load factor可以節(jié)省空間但查找一個元素的時間會增加，減小load factor會占用更多的存儲空間，但是get與put的操作會更快。當(dāng)HashMap中的鍵值對數(shù)量超過了maxSize（即load factor與capacity的乘積），它會再散列，再散列會重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)，桶數(shù)（capacity）大約會增加到原來的兩
倍。
HashMap默認的load factor大小為0.75，這個數(shù)值在時間與空間上做了很好的權(quán)衡。當(dāng)我們清楚自己將要大概存放多少數(shù)據(jù)時，也可以自定義load factor的大小。
HashMap的常用方法如下：
HashMap的構(gòu)造器
HashMap有以下幾個構(gòu)造器：
HashMap() HashMap(int initialCapacity) HashMap(int initialCapacity, float loadFactor) HashMap(Map<? extends K,? extends V> m) //創(chuàng)建一個新的HashMap，用m的數(shù)據(jù)填充無參構(gòu)造器的源碼如下：
/** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }這個構(gòu)造器把loadFactor域設(shè)為DEFAULT_LOAD_FACTOR（0.75），其他域都保持默認值。
我們再來看下第三個構(gòu)造器的源碼：
/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ 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); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }以上源碼中的threshold即為上面提到的maxSize（loadFactor與capacity的乘積）。tableSizeFor方法會根據(jù)給定的initialCapacity返回一個值作為maxSize。
基本實現(xiàn)原理
HashMap是基于拉鏈法處理碰撞的散列表的實現(xiàn)，一個存儲整型元素的HashMap的內(nèi)部存儲結(jié)構(gòu)如下圖所示：
linked.jpg
我們可以看到，HashMap是采用數(shù)組+鏈表實現(xiàn)的，在JDK 1.8中，對HashMap做了進一步優(yōu)化，引入了紅黑樹。當(dāng)鏈表的長度大于8時，就會使用紅黑樹來代替鏈表。
put方法源碼分析
在分析put方法前，我們先來看下HashMap的如下字段：
/** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) */ transient Node<K,V>[] table;table字段是一個Node<K, V>數(shù)組，這個數(shù)組由鏈表的頭結(jié)點組成。我們再來看一下Node<K, V>的定義：
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; //"桶號"，即該Node在數(shù)組的索引 this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } . . . }Node類的hash域為它在Node數(shù)組中的索引，next域為它的下一個Node，key、value分別為保存在Node中的鍵和值。
接下來我們看看put方法的源碼：
這個方法內(nèi)部實際上調(diào)用了putVal方法來干活，hash方法會返回給定key在HashMap中的桶號（即key所在Node在Node數(shù)組中的索引），實際上hash方法的作用是在key的hashCode方法的基礎(chǔ)上進一步增加哈希值的隨機度。putVal方法的源碼如下：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //若table為空或table的length為0則需要通過resize方法擴容if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //讓傳入的hash與n-1做與運算從而得到目標(biāo)Node的索引//若該索引處為null，則直接插入包含了key-value pair的new Node if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //若索引處不為null，則判斷key是否存在Node<K,V> e; K k; //若key存在，則直接覆蓋valueif (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))e = p; //若key不存在，則判斷table[i]是否為TreeNode else if (p instanceof TreeNode) //若是的話，說明此處為紅黑樹，直接插入key-value paire = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//否則遍歷鏈表 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //鏈表長度大于8則轉(zhuǎn)為紅黑樹 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; }//若key已經(jīng)存在則直接覆蓋value if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //若超過maxSize，則擴容if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }以上代碼的工作過程可以總結(jié)為下圖：
put.png
關(guān)于HashMap我們還需要知道它的擴容方法resize的時間消耗比較大，因此我們在能夠估計到大致需要存儲的數(shù)據(jù)量時，應(yīng)該為其指定一個合適的初始容量。
總結(jié)
以上是生活随笔為你收集整理的ArrayList LinkedList与HashMap 实现原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： ReactNative ES6简介 及基
- 下一篇： 建行的分期通是啥回事