ArrayList、LinkedList述么、HashMap是Java開發(fā)中非常常見的數(shù)據(jù)類型蝌数。它們的區(qū)別也非常明顯的，在Java中也非常具有代表性度秘。在Java中顶伞，常見的數(shù)據(jù)結(jié)構(gòu)是：數(shù)組、鏈表剑梳，其他數(shù)據(jù)結(jié)構(gòu)基本就是這兩者的組合唆貌。
復(fù)習(xí)一下數(shù)組、鏈表的特征垢乙。
數(shù)組：在內(nèi)存中連續(xù)的地址塊锨咙，查找按照下標(biāo)來尋址，查找快速追逮。但是插入元素和刪除元素慢酪刀，需要移動元素。
鏈表：內(nèi)存中邏輯上可以連接到一起的一組節(jié)點钮孵。每個節(jié)點除了存儲本身骂倘，還存儲了下一個元素的地址。查找元素需要依次找找各個元素油猫，查找慢稠茂，插入和刪除元素只需要修改元素指向即可。
結(jié)合這兩種數(shù)據(jù)結(jié)構(gòu)的特征情妖，就不難理解ArrayList睬关、LinkedList、HashMap的各種操作了毡证。
ArrayList
數(shù)組
ArrayList的底層實現(xiàn)就是數(shù)組电爹，根據(jù)數(shù)組的特征就很好理解ArrayList的各個特性了。
下面是ArrayList中最基本的兩個變量：存儲對象的數(shù)組和數(shù)組大小料睛。
/**
?* The array buffer into which the elements of the ArrayList are stored.
?* The capacity of the ArrayList is the length of this array buffer. Any
?* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
?* will be expanded to DEFAULT_CAPACITY when the first element is added.
?*/
transientObject[] elementData;?// non-private to simplify nested class access
/**
?* The size of the ArrayList (the number of elements it contains).
?*
?* @serial
?*/
privateintsize;
在執(zhí)行add操作前丐箩，會首先檢查數(shù)組大小是否足以容納新的元素，如果不夠恤煞，就進行擴容屎勘，擴容的公式是：新的數(shù)組大小=(老的數(shù)組大小*3)/2 + 1，例如初始時數(shù)組大小為10居扒，第一次擴容后概漱，數(shù)組大小就為16，再擴容一次變?yōu)?5喜喂。
Fail-Fast 機制
在操作元素的方法中瓤摧，例如add方法和remove方法中，會看到modCount++操作玉吁。這個modCount變量是記錄什么的照弥？
查看modCount的定義，modCount是在AbstractList中定義的进副，其說明如下：
/**
?* The number of times this list has been <i>structurally modified</i>.
?* Structural modifications are those that change the size of the
?* list, or otherwise perturb it in such a fashion that iterations in
?* progress may yield incorrect results.
?*
?* <p>This field is used by the iterator and list iterator implementation
?* returned by the {@code iterator} and {@code listIterator} methods.
?* If the value of this field changes unexpectedly, the iterator (or list
?* iterator) will throw a {@code ConcurrentModificationException} in
?* response to the {@code next}, {@code remove}, {@code previous},
?* {@code set} or {@code add} operations.? This provides
?* <i>fail-fast</i> behavior, rather than non-deterministic behavior in
?* the face of concurrent modification during iteration.
?*
?* <p><b>Use of this field by subclasses is optional.</b> If a subclass
?* wishes to provide fail-fast iterators (and list iterators), then it
?* merely has to increment this field in its {@code add(int, E)} and
?* {@code remove(int)} methods (and any other methods that it overrides
?* that result in structural modifications to the list).? A single call to
?* {@code add(int, E)} or {@code remove(int)} must add no more than
?* one to this field, or the iterators (and list iterators) will throw
?* bogus {@code ConcurrentModificationExceptions}.? If an implementation
?* does not wish to provide fail-fast iterators, this field may be
?* ignored.
?*/
protectedtransientintmodCount =?0;
modCount記錄是List的結(jié)構(gòu)變化次數(shù)这揣，就是List大小變化的次數(shù)，如果在遍歷List的時候影斑，發(fā)現(xiàn)modCount發(fā)生變化曾沈，則拋出異常ConcurrentModificationException。
例如下面的代碼鸥昏，定義了一個Array List塞俱，向其中增加元素，然后遍歷元素吏垮，在遍歷元素過程中障涯，刪除了一個元素。
publicclassArrayListRemoveTest {
??publicstaticvoidmain(String[] args) {
????List lstString =?newArrayList<String>();
????lstString.add("hello");
????Iterator<String> iterator = lstString.iterator();
????while(iterator.hasNext()) {
??????String item = iterator.next();
??????if(item.equals("hello")) {
????????lstString.remove(item);
??????}
????}
??}
}
運行后會拋出異常：
根據(jù)報錯堆棧膳汪，next方法會調(diào)用checkForComodification方法唯蝶，在checkForComodification方法中拋出異常。
finalvoidcheckForComodification() {
????if(modCount != expectedModCount)
????????thrownewConcurrentModificationException();
}
代碼中會比較當(dāng)前的modCount和expectedModCount的值遗嗽，expectedModCount的值是在執(zhí)行Iterator<String> iterator = lstString.iterator();時粘我，在Itr的構(gòu)造函數(shù)中賦值的，是原始的List結(jié)構(gòu)變化次數(shù)。在執(zhí)行remove方法后征字，List的大小發(fā)生了變化都弹，則modCount發(fā)生了變化，兩次modCount不同匙姜，拋出異常畅厢。做這個檢查的原因，是要保持單線程的唯一操作氮昧。這就是Fail-Fast機制框杜。
LinkedList
鏈表
LinkedList的底層實現(xiàn)就是鏈表，插入和刪除只需要改變節(jié)點指向袖肥，效率高咪辱。隨機訪問需要依次找到各個節(jié)點，慢椎组。
LinkedList在類中包含了 first 和 last 兩個指針(Node)油狂。Node 中包含了上一個節(jié)點和下一個節(jié)點的引用，這樣就構(gòu)成了雙向的鏈表庐杨。
transientintsize =?0;
transientNode first;?//鏈表的頭指針
transientNode last;?//尾指針
//存儲對象的結(jié)構(gòu) Node, LinkedList的內(nèi)部類
privatestaticclassNode<E> {
????E item;
????Node next;?// 指向下一個節(jié)點
????Node prev;?//指向上一個節(jié)點
????Node(Node<E> prev, E element, Node<E> next) {
????????this.item = element;
????????this.next = next;
????????this.prev = prev;
????}
}
在新增節(jié)點時选调，只需要創(chuàng)建一個Node，指向這個Node即可灵份。刪除節(jié)點仁堪，修改上一個節(jié)點的prev指向即可。
HashMap
數(shù)組+鏈表
HashMap是Java數(shù)據(jù)結(jié)構(gòu)中兩大結(jié)構(gòu)數(shù)組和鏈表的組合填渠。其結(jié)構(gòu)圖如下：
?可以看出弦聂，HashMap底層是數(shù)組，數(shù)組中的每一項又是一個鏈表氛什。
當(dāng)程序試圖將一個key-value對放入HashMap中時莺葫，程序首先根據(jù)該 key 的 hashCode() 返回值決定該 Entry 在數(shù)組中的存儲位置，即數(shù)組下標(biāo)枪眉。如果數(shù)組該位置上沒有元素捺檬，就直接將該元素放到此數(shù)組中的該位置上。如果兩個 Entry 的 key 的 hashCode() 返回值相同贸铜，那它們的存儲位置相同（即碰撞）堡纬。再調(diào)用equals，如果這兩個 Entry 的 key 通過 equals 比較返回 true蒿秦，新添加 Entry 的 value 將覆蓋集合中原有 Entry 的 value烤镐，但key不會覆蓋，就是value替換棍鳖。如果這兩個 Entry 的 key 通過 equals 比較返回 false炮叶，新添加的 Entry 將與集合中原有 Entry 形成 Entry 鏈，而且新添加的 Entry 位于 Entry 鏈的頭部。
簡單地說镜悉，HashMap 在底層將 key-value 當(dāng)成一個整體進行處理祟辟，這個整體就是一個 Entry 對象。HashMap 底層采用一個 Entry[] 數(shù)組來保存所有的 key-value 對积瞒，當(dāng)需要存儲一個 Entry 對象時川尖，會根據(jù) hash 算法來決定其在數(shù)組中的存儲位置登下，再根據(jù) equals 方法決定其在該數(shù)組位置上的鏈表中的存儲位置茫孔；當(dāng)需要取出一個Entry 時，也會根據(jù) hash 算法找到其在數(shù)組中的存儲位置被芳，再根據(jù) equals 方法從該位置上的鏈表中取出該Entry缰贝。
歡迎工作一到五年的Java工程師朋友們加入Java架構(gòu)開發(fā)： 854393687
群內(nèi)提供免費的Java架構(gòu)學(xué)習(xí)資料（里面有高可用、高并發(fā)畔濒、高性能及分布式剩晴、Jvm性能調(diào)優(yōu)、Spring源碼侵状，MyBatis赞弥，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多個知識點的架構(gòu)資料）合理利用自己每一分每一秒的時間來學(xué)習(xí)提升自己，不要再用"沒有時間“來掩飾自己思想上的懶惰趣兄！趁年輕绽左，使勁拼，給未來的自己一個交代艇潭！
