InterV 9：源碼分析
一. Hashmap的原理
源碼分析參考文章：http://www.rzrgm.cn/xwdreamer/archive/2012/06/03/2532832.html
題目參考文章：http://www.importnew.com/7099.html
總結：
HashMap基于hashing原理，我們通過put()和get()方法儲存和獲取對象。當我們將鍵值對傳遞給put()方法時，它調用鍵對象的hashCode()方法來計算hashcode，然后通過hashcode值找到bucket位置來儲存值對象。當我們調用get(k)方法，HashMap會使用鍵對象的hashcode方法得到hashcode值，然后通過hashcode值找到bucket位置，找到bucket位置之后，會調用keys.equals()方法去找到鏈表中正確的節點，最終找到要找的值對象。
HashMap使用鏈表來解決碰撞問題，當發生碰撞了，對象將會儲存在鏈表的下一個節點中。 HashMap在每個鏈表節點中儲存鍵值對對象。
當兩個不同的鍵對象的hashcode相同時會發生什么？ 它們會儲存在同一個bucket位置的鏈表中。鍵對象的equals()方法用來找到鍵值對。
面試時可能會問到的問題：
1.“你用過HashMap嗎？” “什么是HashMap？你為什么用到它？”
用過，HashMap是基于哈希表的Map接口的非同步實現（Hashtable跟HashMap很像，唯一的區別是Hashtalbe中的方法是線程安全的，也就是同步的）。此實現提供所有可選的映射操作，并允許使用null鍵和null值。此類不保證映射的順序，特別是它不保證該順序恒久不變。
2.“你知道HashMap的工作原理嗎？” “你知道HashMap的get()方法的工作原理嗎？
答案：HashMap是基于hashing的原理，我們使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中獲取對象。當我們給put()方法傳遞鍵和值時，我們先對鍵調用hashCode()方法，返回的hashCode用于找到bucket位置來儲存Entry對象。當獲取對象時，HashMap會使用鍵對象的hashcode方法得到hashcode值，然后通過hashcode值找到bucket位置，找到bucket位置之后，會調用keys.equals()方法去找到鏈表中正確的節點，最終找到要找的值對象。
解釋：這里關鍵點在于指出，HashMap是在bucket中儲存鍵對象和值對象，作為Map.Entry。這一點有助于理解獲取對象的邏輯。如果你沒有意識到這一點，或者錯誤的認為僅僅只在bucket中存儲值的話，你將不會回答如何從HashMap中獲取對象的邏輯。這個答案相當的正確，也顯示出面試者確實知道hashing以及HashMap的工作原理
3.當兩個對象的hashcode相同會發生什么
答案：因為hashcode相同，所以它們的bucket位置相同，‘碰撞’會發生。因為HashMap使用鏈表存儲對象，這個Entry(包含有鍵值對的Map.Entry對象)會存儲在鏈表中。
解釋：這個答案非常的合理，雖然有很多種處理碰撞的方法，這種方法是最簡單的，也正是HashMap的處理方法。
4.如果兩個鍵的hashcode相同，你如何獲取值對象？
答案：當我們調用get(k)方法，HashMap會使用鍵對象的hashcode找到bucket位置，找到bucket位置之后，會調用keys.equals()方法去找到鏈表中正確的節點，最終找到要找的值對象。
解釋：許多情況下，面試者會在這個環節中出錯，因為他們混淆了hashCode()和equals()方法。因為在此之前hashCode()屢屢出現，而equals()方法僅僅在獲取值對象的時候才出現。一些優秀的開發者會指出使用不可變的、聲明作final的對象，并且采用合適的equals()和hashCode()方法的話，將會減少碰撞的發生，提高效率。不可變性使得能夠緩存不同鍵的hashcode，這將提高整個獲取對象的速度，使用String，Interger這樣的wrapper類作為鍵是非常好的選擇。
5.如果HashMap的大小超過了負載因子(load factor)定義的容量，怎么辦？
答案：默認的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，將會創建原來HashMap大小的兩倍的bucket數組，來重新調整map的大小，并將原來的對象放入新的bucket數組中。這個過程叫作rehashing，因為它調用hash方法找到新的bucket位置。
解釋：除非你真正知道HashMap的工作原理，否則你將回答不出這道題。
6.你了解重新調整HashMap大小存在什么問題嗎？
答案：當重新調整HashMap大小的時候，存在條件競爭，出現死循環。因為如果兩個線程都發現HashMap需要重新調整大小了，它們會同時試著調整大小。在調整大小的過程中，存儲在鏈表中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap并不會將元素放在鏈表的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發生了，那么就死循環了。
解釋：你可能回答不上來，這時面試官會提醒你當多線程的情況下，可能產生條件競爭(race condition)。
7.為什么String, Interger這樣的wrapper類適合作為鍵？
答案：String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了，而且String最為常用。因為String是不可變的，也是final的，而且已經重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象。不可變性還有其他的優點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些，這樣就能提高HashMap的性能。
8.我們可以使用自定義的對象作為鍵嗎？
答案：這是前一個問題的延伸。當然你可能使用任何對象作為鍵，只要它遵守了equals()和hashCode()方法的定義規則，并且當對象插入到Map中之后將不會再改變了。如果這個自定義對象時不可變的，那么它已經滿足了作為鍵的條件，因為當它創建之后就已經不能改變了。
9.我們可以使用CocurrentHashMap來代替Hashtable嗎？
答案：這是另外一個很熱門的面試題，因為ConcurrentHashMap越來越多人用了。我們知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因為它僅僅根據同步級別對map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable，但是HashTable提供更強的線程安全性
10.Hashmap為什么大小是2的冪次
答案：為了hash的平均分布，減少碰撞值
11.什么是HashMap的加載因子
答案：加載因子表示Hsah表中元素的填滿的程度. 若:加載因子越大,填滿的元素越多,好處是,空間利用率高了,但:沖突的機會加大了.反之,加載因子越小,填滿的元素越少,好處是:沖突的機會減小了,但:空間浪費多了.
來自：https://github.com/leeSmall/JavaGuide
12. HashMap 簡介
HashMap 主要用來存放鍵值對，它基于哈希表的Map接口實現，是常用的Java集合之一。
JDK1.8 之前 HashMap 由 數組+鏈表 組成的，數組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的（“拉鏈法”解決沖突）.JDK1.8 以后在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為 8）時，將鏈表轉化為紅黑樹，以減少搜索時間。
13. 底層數據結構分析
13.1 JDK1.8之前
JDK1.8 之前 HashMap 底層是 數組和鏈表 結合在一起使用也就是 鏈表散列。HashMap 通過 key 的 hashCode 經過擾動函數（ HashMap 的 hash 方法）處理過后得到 hash 值，然后通過 (n - 1) & hash 判斷當前元素存放的位置（這里的 n 指的是數組的長度），如果當前位置存在元素的話，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同，如果相同的話，直接覆蓋，不相同就通過拉鏈法解決沖突。
所謂擾動函數指的就是 HashMap 的 hash 方法。使用 hash 方法也就是擾動函數是為了防止一些實現比較差的 hashCode() 方法 換句話說使用擾動函數之后可以減少碰撞。
JDK 1.8 HashMap 的 hash 方法源碼:
JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加簡化，但是原理不變。
static final int hash(Object key) { int h; // key.hashCode()：返回散列值也就是hashcode // ^ ：按位異或 // >>>:無符號右移，忽略符號位，空位都以0補齊 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
對比一下 JDK1.7的 HashMap 的 hash 方法源碼.
static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }
對比總結：相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能會稍差一點點，因為畢竟擾動了 4 次。
所謂 “拉鏈法” 就是：將鏈表和數組相結合。也就是說創建一個鏈表數組，數組中每一格就是一個鏈表。若遇到哈希沖突，則將沖突的值加到鏈表中即可。
13.2 JDK1.8之后
相比于之前的版本，jdk1.8在解決哈希沖突時有了較大的變化，當鏈表長度大于閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間。
-
loadFactor加載因子
loadFactor加載因子是控制數組存放數據的疏密程度，loadFactor越趨近于1，那么 數組中存放的數據(entry)也就越多，也就越密，也就是會讓鏈表的長度增加，loadFactor越小，也就是趨近于0，數組中存放的數據(entry)也就越少，也就越稀疏。
loadFactor太大導致查找元素效率低，太小導致數組的利用率低，存放的數據會很分散。loadFactor的默認值為0.75f是官方給出的一個比較好的臨界值。
給定的默認容量為 16，負載因子為 0.75。Map 在使用過程中不斷的往里面存放數據，當數量達到了 16 * 0.75 = 12 就需要將當前 16 的容量進行擴容，而擴容這個過程涉及到 rehash、復制數據等操作，所以非常消耗性能。
-
threshold
threshold = capacity * loadFactor，當Size>=threshold的時候，那么就要考慮對數組的擴增了，也就是說，這個的意思就是 衡量數組是否需要擴增的一個標準。
14. HashMap源碼分析
14.1 構造方法
// 默認構造函數。 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } // 包含另一個“Map”的構造函數 public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false);//下面會分析到這個方法 } // 指定“容量大小”的構造函數 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } // 指定“容量大小”和“加載因子”的構造函數 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); }
14.2 putMapEntries方法：
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); if (s > 0) { // 判斷table是否已經初始化 if (table == null) { // pre-size // 未初始化，s為m的實際元素個數 float ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); // 計算得到的t大于閾值，則初始化閾值 if (t > threshold) threshold = tableSizeFor(t); } // 已初始化，并且m元素個數大于閾值，進行擴容處理 else if (s > threshold) resize(); // 將m中的所有元素添加至HashMap中 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } }
14.3 put方法
HashMap只提供了put用于添加元素，putVal方法只是給put方法調用的一個方法，并沒有提供給用戶使用。
對putVal方法添加元素的分析如下：
- ①如果定位到的數組位置沒有元素 就直接插入。
- ②如果定位到的數組位置有元素就和要插入的key比較，如果key相同就直接覆蓋，如果key不相同，就判斷p是否是一個樹節點，如果是就調用
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)將元素添加進入。如果不是就遍歷鏈表插入(插入的是鏈表尾部)。
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } 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未初始化或者長度為0，進行擴容 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // (n - 1) & hash 確定元素存放在哪個桶中，桶為空，新生成結點放入桶中(此時，這個結點是放在數組中) if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 桶中已經存在元素 else { Node<K,V> e; K k; // 比較桶中第一個元素(數組中的結點)的hash值相等，key相等 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 將第一個元素賦值給e，用e來記錄 e = p; // hash值不相等，即key不相等；為紅黑樹結點 else if (p instanceof TreeNode) // 放入樹中 e = ((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); // 結點數量達到閾值，轉化為紅黑樹 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); // 跳出循環 break; } // 判斷鏈表中結點的key值與插入的元素的key值是否相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // 相等，跳出循環 break; // 用于遍歷桶中的鏈表，與前面的e = p.next組合，可以遍歷鏈表 p = e; } } // 表示在桶中找到key值、hash值與插入元素相等的結點 if (e != null) { // 記錄e的value V oldValue = e.value; // onlyIfAbsent為false或者舊值為null if (!onlyIfAbsent || oldValue == null) //用新值替換舊值 e.value = value; // 訪問后回調 afterNodeAccess(e); // 返回舊值 return oldValue; } } // 結構性修改 ++modCount; // 實際大小大于閾值則擴容 if (++size > threshold) resize(); // 插入后回調 afterNodeInsertion(evict); return null; }
我們再來對比一下 JDK1.7 put方法的代碼
對于put方法的分析如下：
- ①如果定位到的數組位置沒有元素 就直接插入。
- ②如果定位到的數組位置有元素，遍歷以這個元素為頭結點的鏈表，依次和插入的key比較，如果key相同就直接覆蓋，不同就采用頭插法插入元素。
public V put(K key, V value) if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { // 先遍歷 Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); // 再插入 return null; }
14.4 get方法
當我們調用get(k)方法，HashMap會使用鍵對象的hashcode方法得到hashcode值，然后通過hashcode值找到bucket位置，找到bucket位置之后，會調用keys.equals()方法去找到鏈表中正確的節點，最終找到要找的值對象。
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { // 數組元素相等 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 桶中不止一個節點 if ((e = first.next) != null) { // 在樹中get if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 在鏈表中get do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
14.5 resize方法
進行擴容，會伴隨著一次重新hash分配，并且會遍歷hash表中所有的元素，是非常耗時的。在編寫程序中，要盡量避免resize。
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { // 超過最大值就不再擴充了，就只好隨你碰撞去吧 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 沒超過最大值，就擴充為原來的2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 計算新的resize上限 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { // 把每個bucket都移動到新的buckets中 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // 原索引 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // 原索引+oldCap else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 原索引放到bucket里 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 原索引+oldCap放到bucket里 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
14.6 HashMap常用方法測試
package map; import java.util.Collection; import java.util.HashMap; import java.util.Set; public class HashMapDemo { public static void main(String[] args) { HashMap<String, String> map = new HashMap<String, String>(); // 鍵不能重復，值可以重復 map.put("san", "張三"); map.put("si", "李四"); map.put("wu", "王五"); map.put("wang", "老王"); map.put("wang", "老王2");// 老王被覆蓋 map.put("lao", "老王"); System.out.println("-------直接輸出hashmap:-------"); System.out.println(map); /** * 遍歷HashMap */ // 1.獲取Map中的所有鍵 System.out.println("-------foreach獲取Map中所有的鍵:------"); Set<String> keys = map.keySet(); for (String key : keys) { System.out.print(key+" "); } System.out.println();//換行 // 2.獲取Map中所有值 System.out.println("-------foreach獲取Map中所有的值:------"); Collection<String> values = map.values(); for (String value : values) { System.out.print(value+" "); } System.out.println();//換行 // 3.得到key的值的同時得到key所對應的值 System.out.println("-------得到key的值的同時得到key所對應的值:-------"); Set<String> keys2 = map.keySet(); for (String key : keys2) { System.out.print(key + "：" + map.get(key)+" "); } /** * 另外一種不常用的遍歷方式 */ // 當我調用put(key,value)方法的時候，首先會把key和value封裝到 // Entry這個靜態內部類對象中，把Entry對象再添加到數組中，所以我們想獲取 // map中的所有鍵值對，我們只要獲取數組中的所有Entry對象，接下來 // 調用Entry對象中的getKey()和getValue()方法就能獲取鍵值對了 Set<java.util.Map.Entry<String, String>> entrys = map.entrySet(); for (java.util.Map.Entry<String, String> entry : entrys) { System.out.println(entry.getKey() + "--" + entry.getValue()); } /** * HashMap其他常用方法 */ System.out.println("after map.size()："+map.size()); System.out.println("after map.isEmpty()："+map.isEmpty()); System.out.println(map.remove("san")); System.out.println("after map.remove()："+map); System.out.println("after map.get(si)："+map.get("si")); System.out.println("after map.containsKey(si)："+map.containsKey("si")); System.out.println("after containsValue(李四)："+map.containsValue("李四")); System.out.println(map.replace("si", "李四2")); System.out.println("after map.replace(si, 李四2):"+map); } }
二. Arraylist的原理
源碼分析參考文章：http://www.importnew.com/19867.html
問題參考文章：http://www.importnew.com/9928.html
總結：
ArrayList是基于數組實現的，是一個動態數組，其容量能自動增長（2倍），類似于C語言中的動態申請內存，動態增長內存。
ArrayList不是線程安全的，只能用在單線程環境下，多線程環境下可以考慮用Collections.synchronizedList(List l)函數返回一個線程安全的ArrayList類，也可以使用concurrent并發包下的CopyOnWriteArrayList類。
ArrayList實現了Serializable接口，因此它支持序列化，能夠通過序列化傳輸，實現了RandomAccess接口，支持快速隨機訪問，實際上就是通過下標序號進行快速訪問，實現了Cloneable接口，能被克隆。
1. ArrayList簡介
ArrayList 的底層是數組隊列，相當于動態數組。與 Java 中的數組相比，它的容量能動態增長。在添加大量元素前，應用程序可以使用ensureCapacity操作來增加 ArrayList 實例的容量。這可以減少遞增式再分配的數量。
它繼承于 AbstractList，實現了 List, RandomAccess, Cloneable, java.io.Serializable 這些接口。
在我們學數據結構的時候就知道了線性表的順序存儲，插入刪除元素的時間復雜度為O（n）,求表長以及增加元素，取第 i 元素的時間復雜度為O（1）
ArrayList 繼承了AbstractList，實現了List。它是一個數組隊列，提供了相關的添加、刪除、修改、遍歷等功能。
ArrayList 實現了RandomAccess 接口， RandomAccess 是一個標志接口，表明實現這個這個接口的 List 集合是支持快速隨機訪問的。在 ArrayList 中，我們即可以通過元素的序號快速獲取元素對象，這就是快速隨機訪問。
ArrayList 實現了Cloneable 接口，即覆蓋了函數 clone()，能被克隆。
ArrayList 實現java.io.Serializable 接口，這意味著ArrayList支持序列化，能通過序列化去傳輸。
和 Vector 不同，ArrayList 中的操作不是線程安全的！所以，建議在單線程中才使用 ArrayList，而在多線程中可以選擇 Vector 或者 CopyOnWriteArrayList。
2、ArrayList的大小是如何自動增加的？你能分享一下你的代碼嗎？
答案：當有人試圖在arraylist中增加一個對象的時候，Java會去檢查arraylist，以確保已存在的數組中有足夠的容量來存儲這個新的對象。如果沒有足夠容量的話，那么就會新建一個長度更長的數組，舊的數組就會使用Arrays.copyOf方法被復制到新的數組中去，現有的數組引用指向了新的數組
源碼：
//ArrayList Add方法： public boolean add(E e){ //檢查現有數組容量是否足夠存儲新元素 ensureCapacity(size+1); //Increment modCount!! elementData[size++] = e; return true; } //ensureCapacity方法：處理ArrayList的大小 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; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } }
解釋：請注意這樣一個情況：新建了一個數組；舊數組的對象被復制到了新的數組中，并且現有的數組指向新的數組。
3、什么情況下你會使用ArrayList？什么時候你會選擇LinkedList？
答案：訪問元素比插入或者是刪除元素更加頻繁的時候，你應該使用ArrayList。當你在某個特別的索引中，插入或者是刪除元素更加頻繁，或者你壓根就不需要訪問元素的時候，你會選擇LinkedList。
解釋：這里的主要原因是，在ArrayList中訪問元素的最糟糕的時間復雜度是”1″，而在LinkedList中可能就是”n”了。在ArrayList中增加或者刪除某個元素，通常會調用System.arraycopy方法，這是一種極為消耗資源的操作，因此，在頻繁的插入或者是刪除元素的情況下，LinkedList的性能會更加好一點。
4、當傳遞ArrayList到某個方法中，或者某個方法返回ArrayList，什么時候要考慮安全隱患？如何修復安全違規這個問題呢？
答案：當array被當做參數傳遞到某個方法中，如果array在沒有被復制的情況下直接被分配給了成員變量，那么就可能發生這種情況，即當原始的數組被調用的方法改變的時候，傳遞到這個方法中的數組也會改變。下面的這段代碼展示的就是安全違規以及如何修復這個問題。
ArrayList被直接賦給成員變量——安全隱患：
修復這個安全隱患要在把數組傳遞到方法中使用前先進行判空，不為空時進行拷貝
5、如何復制某個ArrayList到另一個ArrayList中去？寫出你的代碼？
答案：下面就是把某個ArrayList復制到另一個ArrayList中去的幾種技術：
- 使用clone()方法，比如ArrayList newArray = oldArray.clone();
- 使用ArrayList構造方法，比如：ArrayList myObject = new ArrayList(myTempObject);
- 使用Collection的copy方法。
注意1和2是淺拷貝(shallow copy)。
6、在索引中ArrayList的增加或者刪除某個對象的運行過程，效率很低嗎？解釋一下為什么？
答案：在ArrayList中增加或者是刪除元素，要調用System.arraycopy這種效率很低的操作，如果遇到了需要頻繁插入或者是刪除的時候，你可以選擇其他的Java集合，比如LinkedList。
看一下下面的代碼：
在ArrayList的某個索引i處添加元素：
刪除ArrayList的某個索引i處的元素：
7. System.arraycopy()和Arrays.copyOf()方法
通過上面源碼我們發現這兩個實現數組復制的方法被廣泛使用而且很多地方都特別巧妙。比如下面add(int index, E element)方法就很巧妙的用到了arraycopy()方法讓數組自己復制自己實現讓index開始之后的所有成員后移一個位置:
/** * 在此列表中的指定位置插入指定的元素。 *先調用 rangeCheckForAdd 對index進行界限檢查；然后調用 ensureCapacityInternal 方法保證capacity足夠大； *再將從index開始之后的所有成員后移一個位置；將element插入index位置；最后size加1。 */ public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! //arraycopy()方法實現數組自己復制自己 //elementData:源數組;index:源數組中的起始位置;elementData：目標數組；index + 1：目標數組中的起始位置； size - index：要復制的數組元素的數量； System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }
又如toArray()方法中用到了copyOf()方法
/** *以正確的順序（從第一個到最后一個元素）返回一個包含此列表中所有元素的數組。 *返回的數組將是“安全的”，因為該列表不保留對它的引用。 （換句話說，這個方法必須分配一個新的數組）。 *因此，調用者可以自由地修改返回的數組。 此方法充當基于陣列和基于集合的API之間的橋梁。 */ public Object[] toArray() { //elementData：要復制的數組；size：要復制的長度 return Arrays.copyOf(elementData, size); }
兩者聯系與區別
聯系： 看兩者源代碼可以發現copyOf()內部調用了System.arraycopy()方法
區別：
- arraycopy()需要目標數組，將原數組拷貝到你自己定義的數組里，而且可以選擇拷貝的起點和長度以及放入新數組中的位置
- copyOf()是系統自動在內部新建一個數組，并返回該數組。
8. ArrayList 核心擴容技術
//下面是ArrayList的擴容機制 //ArrayList的擴容機制提高了性能，如果每次只擴充一個， //那么頻繁的插入會導致頻繁的拷貝，降低性能，而ArrayList的擴容機制避免了這種情況。 /** * 如有必要，增加此ArrayList實例的容量，以確保它至少能容納元素的數量 * @param minCapacity 所需的最小容量 */ public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } //得到最小擴容量 private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 獲取默認的容量和傳入參數的較大值 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } //判斷是否需要擴容,上面兩個方法都要調用 private void ensureExplicitCapacity(int minCapacity) { modCount++; // 如果說minCapacity也就是所需的最小容量大于保存ArrayList數據的數組的長度的話，就需要調用grow(minCapacity)方法擴容。 //這個minCapacity到底為多少呢？舉個例子在添加元素(add)方法中這個minCapacity的大小就為現在數組的長度加1 if (minCapacity - elementData.length > 0) //調用grow方法進行擴容，調用此方法代表已經開始擴容了 grow(minCapacity); }
/** * ArrayList擴容的核心方法。 */ private void grow(int minCapacity) { //elementData為保存ArrayList數據的數組 ///elementData.length求數組長度elementData.size是求數組中的元素個數 // oldCapacity為舊容量，newCapacity為新容量 int oldCapacity = elementData.length; //將oldCapacity 右移一位，其效果相當于oldCapacity /2， //我們知道位運算的速度遠遠快于整除運算，整句運算式的結果就是將新容量更新為舊容量的1.5倍， int newCapacity = oldCapacity + (oldCapacity >> 1); //然后檢查新容量是否大于最小需要容量，若還是小于最小需要容量，那么就把最小需要容量當作數組的新容量， if (newCapacity - minCapacity < 0) newCapacity = minCapacity; //再檢查新容量是否超出了ArrayList所定義的最大容量， //若超出了，則調用hugeCapacity()來比較minCapacity和 MAX_ARRAY_SIZE， //如果minCapacity大于MAX_ARRAY_SIZE，則新容量則為Interger.MAX_VALUE，否則，新容量大小則為 MAX_ARRAY_SIZE。 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }
擴容機制代碼已經做了詳細的解釋。另外值得注意的是大家很容易忽略的一個運算符：移位運算符
簡介：移位運算符就是在二進制的基礎上對數字進行平移。按照平移的方向和填充數字的規則分為三種:<<(左移)、>>(帶符號右移)和>>>(無符號右移)。 作用：對于大數據的2進制運算,位移運算符比那些普通運算符的運算要快很多,因為程序僅僅移動一下而已,不去計算,這樣提高了效率,節省了資源 比如這里：int newCapacity = oldCapacity + (oldCapacity >> 1); 右移一位相當于除2，右移n位相當于除以 2 的 n 次方。這里 oldCapacity 明顯右移了1位所以相當于oldCapacity /2。
另外需要注意的是：
-
java 中的length 屬性是針對數組說的,比如說你聲明了一個數組,想知道這個數組的長度則用到了 length 這個屬性.
-
java 中的length()方法是針對字符串String說的,如果想看這個字符串的長度則用到 length()這個方法.
-
.java 中的size()方法是針對泛型集合說的,如果想看這個泛型有多少個元素,就調用此方法來查看!
9. ArrayList經典Demo
package list; import java.util.ArrayList; import java.util.Iterator; public class ArrayListDemo { public static void main(String[] srgs){ ArrayList<Integer> arrayList = new ArrayList<Integer>(); System.out.printf("Before add:arrayList.size() = %d\n",arrayList.size()); arrayList.add(1); arrayList.add(3); arrayList.add(5); arrayList.add(7); arrayList.add(9); System.out.printf("After add:arrayList.size() = %d\n",arrayList.size()); System.out.println("Printing elements of arrayList"); // 三種遍歷方式打印元素 // 第一種：通過迭代器遍歷 System.out.print("通過迭代器遍歷:"); Iterator<Integer> it = arrayList.iterator(); while(it.hasNext()){ System.out.print(it.next() + " "); } System.out.println(); // 第二種：通過索引值遍歷 System.out.print("通過索引值遍歷:"); for(int i = 0; i < arrayList.size(); i++){ System.out.print(arrayList.get(i) + " "); } System.out.println(); // 第三種：for循環遍歷 System.out.print("for循環遍歷:"); for(Integer number : arrayList){ System.out.print(number + " "); } // toArray用法 // 第一種方式(最常用) Integer[] integer = arrayList.toArray(new Integer[0]); // 第二種方式(容易理解) Integer[] integer1 = new Integer[arrayList.size()]; arrayList.toArray(integer1); // 拋出異常，java不支持向下轉型 //Integer[] integer2 = new Integer[arrayList.size()]; //integer2 = arrayList.toArray(); System.out.println(); // 在指定位置添加元素 arrayList.add(2,2); // 刪除指定位置上的元素 arrayList.remove(2); // 刪除指定元素 arrayList.remove((Object)3); // 判斷arrayList是否包含5 System.out.println("ArrayList contains 5 is: " + arrayList.contains(5)); // 清空ArrayList arrayList.clear(); // 判斷ArrayList是否為空 System.out.println("ArrayList is empty: " + arrayList.isEmpty()); } }
二、流行框架源碼分析
浙公網安備 33010602011771號