java中用到的主要的數(shù)據(jù)結(jié)構(gòu)有 數(shù)組诸典，list，set, map，隊(duì)列蒂窒，棧
其實(shí)分成兩類就是 數(shù)組 與 容器
1.首先來說說最原始的 數(shù)組
數(shù)組與其他容器之間的主要區(qū)別在于三方面：效率膀估，類型以及保存基本類型的能力
1.1 在java中有一種說法是 ：數(shù)組是一種效率最高的存儲(chǔ)于隨機(jī)訪問對(duì)象引用序列的方式幔亥，因?yàn)閿?shù)組就是一個(gè)簡單的線性表，這使得元素的訪問速度非巢齑浚快帕棉，但為這種速度所付出的代價(jià)是數(shù)組對(duì)象的大小要固定，并且在其生命周期中不可變饼记。ArrayList的底層實(shí)現(xiàn)其實(shí)也是數(shù)組香伴，這點(diǎn)在后面講arraylist的時(shí)候再說
1.2 在jdk1.5之前，也就是泛型之前具则，容器在處理對(duì)象是都是將其看作是Object類型即纲，但是數(shù)組 卻可以持有對(duì)象的具體類型類似 Object[].
1.3 在jdk1.5之前，具體來說是泛型與自動(dòng)裝拆箱之前博肋，容器是不能持有基本類型的數(shù)據(jù)也就是說你寫成List<int> 是無法通過編譯器編譯的（當(dāng)然現(xiàn)在也不能）低斋，但是數(shù)組能持有基本類型的引用也就是int [],在自動(dòng)拆裝箱之后，容器能持有基本類型的包裝類型（對(duì)象）也就是類似于List<Integer>.
以上是數(shù)組與容器之間的主要區(qū)別,隨著自動(dòng)包裝機(jī)制的出現(xiàn)匪凡，數(shù)組僅存的優(yōu)點(diǎn)就只剩下效率了
在類加載機(jī)制的時(shí)候提到膊畴，數(shù)組本是由java虛擬機(jī)直接創(chuàng)建。但說到底锹雏，數(shù)組類其實(shí)也是一個(gè)類巴比，但是這個(gè)類沒有放在任何包（java引用包下），沒有任何屬性與方法礁遵，其加載與初始化的過程與其他類型均相同轻绞，如果其元素不是基本類型，元素的類加載過程依舊不變佣耐。在分析對(duì)象內(nèi)存結(jié)構(gòu)的時(shí)候也說到政勃，對(duì)象頭中類型指針如果當(dāng)前的對(duì)象是數(shù)組，那么類型指針中必須還要有一個(gè)數(shù)組長度的字段兼砖，用來確定當(dāng)前對(duì)象所需的內(nèi)存大小奸远，因?yàn)橐粋€(gè)對(duì)象所需的內(nèi)存大小在類加載完成之后便可以確定既棺，所以必須要有數(shù)組的長度。
數(shù)組的具體使用在工具類 Arrays 類中有很好的定義懒叛，相應(yīng)的容器的工具類是 Collections丸冕，下面來看看Arrays中關(guān)于數(shù)組的實(shí)用方法：
1.asList 這個(gè)方法用于將任意序列或數(shù)組轉(zhuǎn)換為List容器（實(shí)際上是一個(gè)arrayList對(duì)象）
2.System.arrayCopy()用于對(duì)復(fù)制數(shù)組，用此方法復(fù)制數(shù)組比用for循環(huán)來復(fù)制要快很多薛窥，并且對(duì)所有類型做了重載胖烛，如果當(dāng)前復(fù)制的對(duì)象不是原始類型，那么這種復(fù)制是一種淺復(fù)制稱之為淺克隆诅迷，只是單純的復(fù)制了當(dāng)前對(duì)象的引用而已佩番，并沒有重創(chuàng)建對(duì)象。對(duì)應(yīng)到Arrays中是copyOf方法罢杉。
3.sort用于對(duì)數(shù)組進(jìn)行排序
4.binarySearch用于對(duì)已經(jīng)排序的數(shù)組中查找元素（最原始的二分查找）趟畏，并且針對(duì)所有的類型做了重載處理。
5.arrys重寫了equals方法滩租，用于對(duì)數(shù)組進(jìn)行比較赋秀，Arrays.equals(a[],b[]).兩個(gè)數(shù)組相等的前提是數(shù)組的長度要相等，并且其包含的元素的equals方法相等（對(duì)于基本類型律想，使用的是包裝器類型的equals方法）
6.數(shù)組元素的比較沃琅，這里使用的是典型的策略模式，通用不變的是排序算法蜘欲，變化的是各種對(duì)象相互比較的方式。java中有兩種方式來實(shí)現(xiàn)比較功能晌柬，第一種是實(shí)現(xiàn)Comparable接口姥份，使你的類天生具有比較功能。該接口中只包含有一個(gè)compareTo方法年碘，小于返回負(fù)值澈歉，大于返回正值，等于返回0.第二種方式是創(chuàng)建一個(gè)實(shí)現(xiàn)Comparator接口的獨(dú)立的類
2.容器
首先通過一張圖來對(duì)容器的組成有一個(gè)整體的認(rèn)識(shí)：
容器家族的組成結(jié)構(gòu)還是比較復(fù)雜的屿衅，其中有七大基本接口埃难，分別是 Iterator，List涤久，Collection涡尘，Map，Set响迂，Queue考抄，Comparable。其中List蔗彤，Set接口繼承了Collection接口
List系列
1.1 ArrayList
ArrayList 繼承了 AbstractList 實(shí)現(xiàn)了List 接口川梅，被稱之為可擴(kuò)容的動(dòng)態(tài)數(shù)組（resizeable - array）ArrayList 的屬性數(shù)組 的初始默認(rèn)大小為 10疯兼， arrayList的核心是在擴(kuò)容，我們來具體分析下擴(kuò)容的方法：
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//原來數(shù)組的大小
int newCapacity = oldCapacity + (oldCapacity >> 1);//每次擴(kuò)容的大小為原數(shù)組的一半
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);//然后將原數(shù)組拷貝到新的數(shù)組中
}
add方法（注意區(qū)分length 與size length是當(dāng)前數(shù)組的長度贫途，size是當(dāng)前數(shù)組中元素的個(gè)數(shù)）我們調(diào)用ArrayList.size（）拿到的是列表中元素的個(gè)數(shù)
也就是說ArrayList的每次add元素都會(huì)先去判斷當(dāng)前的空間是否足夠（默認(rèn)為10）吧彪，如果空間不夠會(huì)調(diào)用動(dòng)態(tài)擴(kuò)容，每次擴(kuò)容會(huì)把數(shù)組大小擴(kuò)充為 length + length/2丢早。擴(kuò)容完成之后姨裸，在借用Arrays中的copyOf方法將原數(shù)組拷貝到擴(kuò)容之后的數(shù)組中，數(shù)組元素的size+1香拉，這里同樣是淺克隆啦扬，即只克隆當(dāng)前對(duì)象的引用。如果元素加在頭部凫碌，元素移動(dòng)的次數(shù)是size扑毡，如果元素插入在尾部，元素移動(dòng)的次數(shù)為0.
indexOf 方法
該方法用于查到當(dāng)前對(duì)象在列表中位置盛险，其實(shí)現(xiàn)的基本原理是一次循環(huán)遍歷瞄摊，時(shí)間復(fù)雜度為n，其最終比較的方法依舊是調(diào)用當(dāng)前對(duì)象的 equals 方法去進(jìn)行比較苦掘，如果相等返回當(dāng)前對(duì)象在數(shù)組的下標(biāo)换帜，如果找不到則返回-1。
remove方法
該方法的核心依舊是復(fù)制鹤啡，找到當(dāng)前要移除的對(duì)象惯驼，移除當(dāng)前對(duì)象，將當(dāng)前對(duì)象之后的對(duì)象全部重新按照下標(biāo)進(jìn)行拷貝递瑰，也就是說只有移除最后一個(gè)位置的對(duì)象拷貝的次數(shù)為0祟牲，移除第一個(gè)位置的元素移動(dòng)的次數(shù)為n-1。類似于先進(jìn)先出的隊(duì)列的實(shí)現(xiàn)方式是不合適用數(shù)組的抖部。
clone方法
ArrayList實(shí)現(xiàn)了Cloneable接口说贝，所以具備克隆當(dāng)前列表的能力（淺克隆）
/**
* Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
* elements themselves are not copied.)
*
* @return a clone of this <tt>ArrayList</tt> instance
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
ArrayList中還有很多經(jīng)常用到的方法慎颗，類似于subList乡恕，toArray等等。
ArryList總結(jié)
ArrayList的底層實(shí)現(xiàn)是 一個(gè)可動(dòng)態(tài)擴(kuò)容的數(shù)組（數(shù)組默認(rèn)大小為10）俯萎，每次擴(kuò)容的大小為原有數(shù)組的一半傲宜，基于數(shù)組的優(yōu)劣，ArrayList在讀取數(shù)據(jù)方面相當(dāng)快的讯屈，但 插入 與 刪除 數(shù)據(jù)的時(shí)候設(shè)計(jì)到大量數(shù)據(jù)的移動(dòng)與復(fù)制蛋哭，性能有損耗. 在數(shù)據(jù)的移動(dòng)與復(fù)制時(shí)使用的是Arrays.copyOf()方法，該方法性能比較優(yōu)異的涮母。
1.2LinkedList
首先要了解LinkedList的底層實(shí)現(xiàn)是一個(gè)雙向鏈表谆趾，鏈表不同于數(shù)組躁愿，數(shù)組的內(nèi)存分配是連續(xù)的，要獲取某個(gè)位置的對(duì)象直接調(diào)用數(shù)組的位置即可沪蓬，但是鏈表不同彤钟，鏈表的內(nèi)存分配只是在邏輯上是連續(xù)的，這就決定了要讀取一個(gè)對(duì)象的速度會(huì)比數(shù)組要慢許多跷叉。鏈表中要讀取一個(gè)對(duì)象逸雹，首先要定位當(dāng)前對(duì)象的位置，需要遍歷一次鏈表云挟，通過對(duì)象的equals方法找到當(dāng)前對(duì)象的位置梆砸。知道對(duì)象的位置之后，鏈表的內(nèi)存在物理上是不連續(xù)的园欣，不能像數(shù)組一樣直接通過數(shù)組的位置去取當(dāng)前的對(duì)象帖世，而是要通過又一次遍歷去找到對(duì)應(yīng)的位置從而返回相應(yīng)的對(duì)象。這其中的兩次遍歷會(huì)有相應(yīng)的性能損耗沸枯，當(dāng)前在第二次訪問的時(shí)候只做了查找優(yōu)化處理日矫，實(shí)際上只需要循環(huán) size/2 次。 之所以比數(shù)組要慢绑榴，是慢在了第二次遍歷的時(shí)間
在讀取對(duì)象的速度上哪轿，這是數(shù)組優(yōu)于鏈表的地方
由于是鏈表，在其上添加或刪除一個(gè)對(duì)象時(shí)就變得相當(dāng)簡單了翔怎，要在A與B之間添加一個(gè)C對(duì)象窃诉，只需要將A的下一個(gè)指向指向C，C的前一個(gè)指向指向A赤套，C的下一個(gè)指向指向B褐奴，B的前一個(gè)指向指向C就可以了，刪除一個(gè)對(duì)象原理相同于毙。相對(duì)于數(shù)組的各種復(fù)制與移動(dòng)，性能上會(huì)有很大的提升辅搬，這也是鏈表在添加與刪除數(shù)據(jù)時(shí)要優(yōu)于數(shù)組的原因唯沮。
在添加與刪除對(duì)象的性能與速度上，鏈表要明顯優(yōu)于數(shù)組
需要注意的是LinkedList實(shí)現(xiàn)了Dqueue接口堪遂，使得LinkedList具備了類似于隊(duì)列與棧的功能介蛉，隊(duì)列功能對(duì)應(yīng)的方法為 poll方法（出隊(duì)） ： 移除第一個(gè)元素，頭部元素溶褪，peek方法只是獲取第一個(gè)元素币旧，但并不移除改元素。offer方法（入隊(duì)）：將元素添加到鏈表的末尾猿妈。棧功能實(shí)現(xiàn)的方法為pop（出棧）：移除鏈表的第一個(gè)元素吹菱，push（入棧）：將元素添加到鏈表的頭部
LinkedList總結(jié)
LinkedList底層的實(shí)現(xiàn)是個(gè)雙向鏈表巍虫，其實(shí)現(xiàn)了List與Dqueue接口，所以LinkedList兼具有隊(duì)列與棧的功能,在數(shù)據(jù)的插入與刪除上鳍刷，其性能要遠(yuǎn)優(yōu)于ArrayList占遥，其具體原因是：LinkedList添加與刪除元素只需要重置元素之間的關(guān)系（即前一個(gè)與后一個(gè)的關(guān)聯(lián)）的關(guān)聯(lián)打斷即可，而arrayList則涉及到一系列的元素移動(dòng)输瓜。但是在數(shù)據(jù)的查找方面瓦胎，LinkedList是要比ArrayList性能要差的。其具體原因在于尤揣，數(shù)組（ArrayList）的內(nèi)存地址是連續(xù)的搔啊，知道元素的位置，直接去取位置的元素即可北戏，而LinkedList則要先找到元素的位置负芋，然后通過折半查找從靠近元素一段開始遍歷，也就是說最差的情況是LinkedList查找元素要比ArrayList多遍歷列表長度的一半最欠。
1.3 Vector
Vector一般沒什么可說的示罗，vector是一個(gè)線程安全的數(shù)組集合，因?yàn)関ector中的大部分方法都通過synchronized 關(guān)鍵字進(jìn)行了同步處理芝硬。除了線程安全之外蚜点，它跟ArrayList沒什么區(qū)別“枰酰考慮到線程同步帶來的性能開銷绍绘，在不考慮同步的情況下一般優(yōu)先考慮ArrayList。
set 系列 (確定性迟赃，互斥性陪拘，無序性)
A collection that contains no duplicate elements. set集合中不允許有重復(fù)的元素出現(xiàn)，也就是不允許有a.equals(b)的元素存在纤壁，當(dāng)然也只能有一個(gè)null左刽。一句話來說就是，在set中不會(huì)出現(xiàn)重復(fù)的元素
2.1 HashSet
HashSet的底層操作是操作一個(gè)HashMap對(duì)象酌媒，HashSet'能保證數(shù)據(jù)的唯一性欠痴，但不保證數(shù)據(jù)的有序性。為了保證數(shù)據(jù)的唯一性秒咨，是用對(duì)象的hash地址與equals來確定key的唯一性喇辽。如果hashcode與equals都保持一致，則視為是同一個(gè)對(duì)象（驗(yàn)證了重寫了equals方法一般會(huì)重寫hashcode方法的說法）雨席，而hashSet是用存儲(chǔ)的對(duì)象作為key保存的菩咨，說到底HashSet的數(shù)據(jù)是存在hashMap的key中，所以要遍歷HashSet中元素的個(gè)數(shù)只需要遍歷HashMap的keySet就可以了。別的就沒什么好說的了抽米，具體hashmap是怎么存儲(chǔ)的到后面再說特占。（順便提一下，到現(xiàn)在為止我都沒明白hashSet存在正在的意義是什么缨硝，既然HashMap都能搞定為什么還要HashSet這個(gè)數(shù)據(jù)結(jié)構(gòu)摩钙？）。
Map 系列
map的核心思想是存儲(chǔ)鍵值對(duì)查辩，通過鍵查找值胖笛。與set一樣，map里面的key必須保持唯一性宜岛，如果同樣的key存入map則新的值會(huì)覆蓋上一次的值长踊。
3.1 HashMap
hashMap的重點(diǎn)是散列算法（hash（）方法），散列算法的好壞直接決定hashMap的性能萍倡。核心是resize（） 與 紅黑樹身弊，其底層的實(shí)現(xiàn)用鏈地址法 通過 數(shù)組與單向鏈表來存儲(chǔ)數(shù)據(jù)拟烫，也就說在底層hashmap是數(shù)組與鏈表的結(jié)合體贮竟，數(shù)組用來存放key通過hash方法生成的值，鏈表用來存儲(chǔ)真正的鍵值對(duì)耍缴。
在源碼中 hash的算法是這樣的戴而，簡單而高效：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
我們一起來回一下hashMap存儲(chǔ)數(shù)據(jù)的過程凑术，主要分為以下幾個(gè)步驟：
1.首先判斷用于存放鍵值對(duì)單向鏈表的數(shù)組是否為空，如果為空則先調(diào)用resize方法擴(kuò)容
2.然后通過hash算法獲取數(shù)組位置并且判斷當(dāng)前位置是否已經(jīng)存在數(shù)據(jù)（鏈表元素）所意，如果沒有淮逊，創(chuàng)建鏈表
3.如果當(dāng)前位置存在鏈表，則遍歷該鏈表扶踊，如果鏈表中元素的key與當(dāng)前元素的key相同泄鹏，則只是覆蓋當(dāng)前key關(guān)鍵字對(duì)應(yīng)的值。
4.如果當(dāng)前鏈表中不存在當(dāng)前的key秧耗，則先判斷當(dāng)前鏈表是否已經(jīng)轉(zhuǎn)換為紅黑樹备籽，如果是則直接將元素插入紅黑樹（紅黑樹是一顆平衡二叉樹，不會(huì)有重復(fù)的元素分井，后面會(huì)單獨(dú)詳細(xì)說）
5.如果當(dāng)前鏈表沒有轉(zhuǎn)換為紅黑樹胶台，則遍歷當(dāng)前鏈表，如果在鏈表元素大于8之前找到了當(dāng)前的key則覆蓋杂抽，如果添加到鏈表尾部剛好大于8則需要進(jìn)行紅黑樹轉(zhuǎn)換的操作
上面就是往HashMap中添加一個(gè)元素的全部過程。下面來看看添加的源碼：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//如果當(dāng)前數(shù)組為空韩脏，創(chuàng)建數(shù)組
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);//如果當(dāng)前數(shù)組位置為空缩麸，創(chuàng)建一個(gè)新節(jié)點(diǎn)
else {//如果當(dāng)前位置存在元素
Node<K,V> e; K k;
if (p.hash == hash &&//如果當(dāng)前key的對(duì)應(yīng)的對(duì)象是同一個(gè)對(duì)象（hashcode與equals方法都相等），直接覆蓋當(dāng)前key對(duì)應(yīng)的值
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)//如果當(dāng)前是鏈表是紅黑樹赡矢，直接插入紅黑樹
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//如果鏈表元素大于8杭朱，轉(zhuǎn)換為紅黑樹
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key//如果當(dāng)前的key在鏈表中存在阅仔，直接覆蓋key對(duì)應(yīng)的值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);//此處是LinkedHashMap中有用到
return oldValue;
}
}
//如果是數(shù)組中添加元素，走此處弧械，如果數(shù)組空間不夠八酒，需要重新擴(kuò)容
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
下面來看看最核心的resize方法，hashMap的擴(kuò)容與arrayList的擴(kuò)容還是有點(diǎn)區(qū)別的刃唐，arrayList的擴(kuò)容只是將原數(shù)組的數(shù)據(jù)全數(shù)拷貝到新的數(shù)組中羞迷，而HashMap中的擴(kuò)容卻要復(fù)雜的多。我們來看看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;
}
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 { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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) {
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 { // preserve order
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;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
擴(kuò)容的條件是:當(dāng)map中包含的Entry的數(shù)量大于等于threshold = loadFactor(0.75) * capacity的時(shí)候画饥，且新建的Entry剛好落在一個(gè)非空的桶上衔瓮，此刻觸發(fā)擴(kuò)容機(jī)制，將其容量擴(kuò)大為2倍抖甘。
3.2 LinkedHashMap
LinkedHashMap的底層實(shí)現(xiàn)依舊是HashMap只是在hashmap的基礎(chǔ)上用一個(gè)雙向鏈表將添加到鏈表中的元素連接起來热鞍，形成了一個(gè)邏輯上的雙向鏈表，從而使添加進(jìn)hashmap的元素有了邏輯上的順序衔彻，其余的與hashmap沒有區(qū)別薇宠。LinkedHashMap與hashmap是一個(gè)典型的裝飾模式的應(yīng)用。
3.3 ArrayMap（android 中特有,為了節(jié)約空間而生）
在以往android開發(fā)中艰额，我們常常用key-value存儲(chǔ)數(shù)據(jù)時(shí)澄港，隨手就會(huì)打出HashMap的代碼，當(dāng)數(shù)據(jù)量較小時(shí)悴晰，這種方法還不錯(cuò)還可以慢睡，當(dāng)數(shù)據(jù)量比較多的時(shí)候，如果是PC機(jī)上铡溪，也還闊以漂辐。但是如果使用設(shè)備是手機(jī)等移動(dòng)設(shè)備，這是就要慎重了棕硫。手機(jī)內(nèi)存不像PC內(nèi)存那樣髓涯，手機(jī)內(nèi)存很寶貴，稍有不慎哈扮，可能就會(huì)引發(fā)OOM問題纬纪。那當(dāng)數(shù)據(jù)量比較多，又需要在手機(jī)端開發(fā)滑肉，這個(gè)時(shí)候包各，我們就可以用ArrayMap替代HashMap。ArrayMap相比傳統(tǒng)的HashMap速度要慢靶庙，因?yàn)椴檎曳椒ㄊ嵌址ㄎ食⑶耶?dāng)你刪除或者添加數(shù)據(jù)時(shí)，會(huì)對(duì)空間重新調(diào)整，在使用大量數(shù)據(jù)時(shí)护姆，效率低于50%矾端。可以說ArrayMap是犧牲了時(shí)間換區(qū)空間卵皂。但在寫手機(jī)app時(shí)秩铆，適時(shí)的使用ArrayMap，會(huì)給內(nèi)存使用帶來可觀的提升灯变。
上面說了ArrayMap的出現(xiàn)時(shí)為了節(jié)省內(nèi)存空間殴玛，那么在性能方面是要比hashmap差的，這個(gè)也就是實(shí)現(xiàn)了傳統(tǒng)意義上的時(shí)間換空間柒凉。
3.4 ConcurrentHashMap
HashMap在多線程環(huán)境下是線程不安全的族阅，在resize的再哈希的時(shí)候會(huì)導(dǎo)致鏈表死循環(huán)，當(dāng)然在多線程環(huán)境下膝捞，java官方也提供了類似hashTable與synchronizedMap來保證線程安全性坦刀，但其效率非常低下。在JDK1.5 以后蔬咬，官方提供了一個(gè)線程安全的ConcurrentHashMap類鲤遥。在ConcurrentHashMap中，無論是讀操作還是寫操作都能保證很高的性能：在進(jìn)行讀操作時(shí)(幾乎)不需要加鎖林艘，而在寫操作時(shí)通過鎖分段技術(shù)只對(duì)所操作的段加鎖而不影響客戶端對(duì)其它段的訪問盖奈。特別地，在理想狀態(tài)下狐援，ConcurrentHashMap 可以支持 16 個(gè)線程執(zhí)行并發(fā)寫操作（如果并發(fā)級(jí)別設(shè)為16）钢坦，及任意數(shù)量線程的讀操作。
