「我是大廠面試官」—— Java 集合，你肯定會(huì)被問(wèn)到這些
文章收錄在 GitHub JavaKeeper ，N線互聯(lián)網(wǎng)開(kāi)發(fā)必備技能兵器譜
作為一位小菜 ”一面面試官“，面試過(guò)程中，我肯定會(huì)問(wèn) Java 集合的內(nèi)容，同時(shí)作為求職者，也肯定會(huì)被問(wèn)到集合，所以整理下 Java 集合面試題
說(shuō)說(shuō)常見(jiàn)的集合有哪些吧？
HashMap說(shuō)一下，其中的Key需要重寫hashCode()和equals()嗎？
HashMap中key和value可以為null嗎？允許幾個(gè)為null呀？
HashMap線程安全嗎?ConcurrentHashMap和hashTable有什么區(qū)別？
List和Set說(shuō)一下，現(xiàn)在有一個(gè)ArrayList，對(duì)其中的所有元素按照某一屬性大小排序，應(yīng)該怎么做？
ArrayList 和 Vector 的區(qū)別
list 可以刪除嗎，遍歷的時(shí)候可以刪除嗎，為什么
面向?qū)ο笳Z(yǔ)言對(duì)事物的體現(xiàn)都是以對(duì)象的形式，所以為了方便對(duì)多個(gè)對(duì)象的操作，需要將對(duì)象進(jìn)行存儲(chǔ)，集合就是存儲(chǔ)對(duì)象最常用的一種方式，也叫容器。
從上面的集合框架圖可以看到，Java 集合框架主要包括兩種類型的容器
- 一種是集合（Collection），存儲(chǔ)一個(gè)元素集合
- 另一種是圖（Map），存儲(chǔ)鍵/值對(duì)映射。
Collection 接口又有 3 種子類型，List、Set 和 Queue，再下面是一些抽象類，最后是具體實(shí)現(xiàn)類，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。
集合框架是一個(gè)用來(lái)代表和操縱集合的統(tǒng)一架構(gòu)。所有的集合框架都包含如下內(nèi)容：
接口：是代表集合的抽象數(shù)據(jù)類型。例如 Collection、List、Set、Map 等。之所以定義多個(gè)接口，是為了以不同的方式操作集合對(duì)象
實(shí)現(xiàn)（類）：是集合接口的具體實(shí)現(xiàn)。從本質(zhì)上講，它們是可重復(fù)使用的數(shù)據(jù)結(jié)構(gòu)，例如：ArrayList、LinkedList、HashSet、HashMap。
算法：是實(shí)現(xiàn)集合接口的對(duì)象里的方法執(zhí)行的一些有用的計(jì)算，例如：搜索和排序。這些算法被稱為多態(tài)，那是因?yàn)橄嗤姆椒梢栽谙嗨频慕涌谏嫌兄煌膶?shí)現(xiàn)。
說(shuō)說(shuō)常用的集合有哪些吧？
Map 接口和 Collection 接口是所有集合框架的父接口：
- Collection接口的子接口包括：Set、List、Queue
- List是有序的允許有重復(fù)元素的Collection，實(shí)現(xiàn)類主要有：ArrayList、LinkedList、Stack以及Vector等
- Set是一種不包含重復(fù)元素且無(wú)序的Collection，實(shí)現(xiàn)類主要有：HashSet、TreeSet、LinkedHashSet等
- Map沒(méi)有繼承Collection接口，Map提供key到value的映射。實(shí)現(xiàn)類主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap 以及 Properties 等
ArrayList 和 Vector 的區(qū)別
相同點(diǎn)：
-
ArrayList 和 Vector 都是繼承了相同的父類和實(shí)現(xiàn)了相同的接口（都實(shí)現(xiàn)了List，有序、允許重復(fù)和null）
extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable 底層都是數(shù)組（Object[]）實(shí)現(xiàn)的
初始默認(rèn)長(zhǎng)度都為10
不同點(diǎn)：
同步性：Vector 中的 public 方法多數(shù)添加了 synchronized 關(guān)鍵字、以確保方法同步、也即是 Vector 線程安全、ArrayList 線程不安全
性能：Vector 存在 synchronized 的鎖等待情況、需要等待釋放鎖這個(gè)過(guò)程、所以性能相對(duì)較差
-
擴(kuò)容大?。篈rrayList在底層數(shù)組不夠用時(shí)在原來(lái)的基礎(chǔ)上擴(kuò)展 0.5 倍，Vector默認(rèn)是擴(kuò)展 1 倍
擴(kuò)容機(jī)制，擴(kuò)容方法其實(shí)就是新創(chuàng)建一個(gè)數(shù)組，然后將舊數(shù)組的元素都復(fù)制到新數(shù)組里面。其底層的擴(kuò)容方法都在 grow() 中（基于JDK8）
-
ArrayList 的 grow()，在滿足擴(kuò)容條件時(shí)、ArrayList以1.5 倍的方式在擴(kuò)容（oldCapacity >> 1 ，右移運(yùn)算，相當(dāng)于除以 2，結(jié)果為二分之一的 oldCapacity）
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //newCapacity = oldCapacity + O.5*oldCapacity,此處擴(kuò)容0.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); 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); } -
Vector 的 grow()，Vector 比 ArrayList多一個(gè)屬性，擴(kuò)展因子capacityIncrement，可以擴(kuò)容大小。當(dāng)擴(kuò)容容量增量大于0時(shí)、新數(shù)組長(zhǎng)度為原數(shù)組長(zhǎng)度+擴(kuò)容容量增量、否則新數(shù)組長(zhǎng)度為原數(shù)組長(zhǎng)度的2倍
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; // int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); }
-
ArrayList 與 LinkedList 區(qū)別
- 是否保證線程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保證線程安全；
- 底層數(shù)據(jù)結(jié)構(gòu)： Arraylist 底層使用的是 Object 數(shù)組；LinkedList 底層使用的是雙向循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)；
-
插入和刪除是否受元素位置的影響：
-
ArrayList 采用數(shù)組存儲(chǔ)，所以插入和刪除元素的時(shí)間復(fù)雜度受元素位置的影響。 比如：執(zhí)行
add(E e)方法的時(shí)候， ArrayList 會(huì)默認(rèn)在將指定的元素追加到此列表的末尾，這種情況時(shí)間復(fù)雜度就是O(1)。但是如果要在指定位置 i 插入和刪除元素的話（add(intindex,E element)）時(shí)間復(fù)雜度就為 O(n-i)。因?yàn)樵谶M(jìn)行上述操作的時(shí)候集合中第 i 和第 i 個(gè)元素之后的(n-i)個(gè)元素都要執(zhí)行向后位/向前移一位的操作。 - LinkedList 采用鏈表存儲(chǔ)，所以插入，刪除元素時(shí)間復(fù)雜度不受元素位置的影響，都是近似
，而數(shù)組為近似
。
- ArrayList 一般應(yīng)用于查詢較多但插入以及刪除較少情況，如果插入以及刪除較多則建議使用 LinkedList
-
ArrayList 采用數(shù)組存儲(chǔ)，所以插入和刪除元素的時(shí)間復(fù)雜度受元素位置的影響。 比如：執(zhí)行
-
是否支持快速隨機(jī)訪問(wèn)： LinkedList 不支持高效的隨機(jī)元素訪問(wèn)，而 ArrayList 實(shí)現(xiàn)了 RandomAccess 接口，所以有隨機(jī)訪問(wèn)功能。快速隨機(jī)訪問(wèn)就是通過(guò)元素的序號(hào)快速獲取元素對(duì)象(對(duì)應(yīng)于
get(intindex)方法)。 - 內(nèi)存空間占用： ArrayList 的空間浪費(fèi)主要體現(xiàn)在在 list 列表的結(jié)尾會(huì)預(yù)留一定的容量空間，而 LinkedList 的空間花費(fèi)則體現(xiàn)在它的每一個(gè)元素都需要消耗比 ArrayList 更多的空間（因?yàn)橐娣胖苯雍罄^和直接前驅(qū)以及數(shù)據(jù)）。
高級(jí)工程師的我，可不得看看源碼，具體分析下：
ArrayList工作原理其實(shí)很簡(jiǎn)單，底層是動(dòng)態(tài)數(shù)組，每次創(chuàng)建一個(gè) ArrayList 實(shí)例時(shí)會(huì)分配一個(gè)初始容量（沒(méi)有指定初始容量的話，默認(rèn)是 10），以add方法為例，如果沒(méi)有指定初始容量，當(dāng)執(zhí)行add方法，先判斷當(dāng)前數(shù)組是否為空，如果為空則給保存對(duì)象的數(shù)組分配一個(gè)最小容量，默認(rèn)為10。當(dāng)添加大容量元素時(shí)，會(huì)先增加數(shù)組的大小，以提高添加的效率；
LinkedList 是有序并且支持元素重復(fù)的集合，底層是基于雙向鏈表的，即每個(gè)節(jié)點(diǎn)既包含指向其后繼的引用也包括指向其前驅(qū)的引用。鏈表無(wú)容量限制，但雙向鏈表本身使用了更多空間，也需要額外的鏈表指針操作。按下標(biāo)訪問(wèn)元素
get(i)/set(i,e)要悲劇的遍歷鏈表將指針移動(dòng)到位(如果i>數(shù)組大小的一半，會(huì)從末尾移起)。插入、刪除元素時(shí)修改前后節(jié)點(diǎn)的指針即可，但還是要遍歷部分鏈表的指針才能移動(dòng)到下標(biāo)所指的位置，只有在鏈表兩頭的操作add()，addFirst()，removeLast()或用iterator()上的remove()能省掉指針的移動(dòng)。此外 LinkedList 還實(shí)現(xiàn)了 Deque（繼承自Queue接口）接口，可以當(dāng)做隊(duì)列使用。
不會(huì)囊括所有方法，只是為了學(xué)習(xí)，記錄思想。
ArrayList 和 LinkedList 兩者都實(shí)現(xiàn)了 List 接口
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
構(gòu)造器
ArrayList 提供了 3 個(gè)構(gòu)造器，①無(wú)參構(gòu)造器 ②帶初始容量構(gòu)造器 ③參數(shù)為集合構(gòu)造器
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 創(chuàng)建初始容量的數(shù)組
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
}
}
public ArrayList() {
// 默認(rèn)為空數(shù)組
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) { //...}
}
LinkedList 提供了 2 個(gè)構(gòu)造器，因?yàn)榛阪湵?，所以也就沒(méi)有初始化大小，也沒(méi)有擴(kuò)容的機(jī)制，就是一直在前面或者后面插插插~~
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
// LinkedList 既然作為鏈表，那么肯定會(huì)有節(jié)點(diǎn)
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;
}
}
插入
ArrayList:
public boolean add(E e) {
// 確保數(shù)組的容量，保證可以添加該元素
ensureCapacityInternal(size + 1); // Increments modCount!!
// 將該元素放入數(shù)組中
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 如果數(shù)組是空的，那么會(huì)初始化該數(shù)組
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// DEFAULT_CAPACITY 為 10,所以調(diào)用無(wú)參默認(rèn) ArrayList 構(gòu)造方法初始化的話，默認(rèn)的數(shù)組容量為 10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 確保數(shù)組的容量，如果不夠的話，調(diào)用 grow 方法擴(kuò)容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//擴(kuò)容具體的方法
private void grow(int minCapacity) {
// 當(dāng)前數(shù)組的容量
int oldCapacity = elementData.length;
// 新數(shù)組擴(kuò)容為原來(lái)容量的 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新數(shù)組擴(kuò)容容量還是比最少需要的容量還要小的話，就設(shè)置擴(kuò)充容量為最小需要的容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判斷新數(shù)組容量是否已經(jīng)超出最大數(shù)組范圍，MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 復(fù)制元素到新的數(shù)組中
elementData = Arrays.copyOf(elementData, newCapacity);
}
當(dāng)然也可以插入指定位置，還有一個(gè)重載的方法 add(int index, E element)
public void add(int index, E element) {
// 判斷 index 有沒(méi)有超出索引的范圍
rangeCheckForAdd(index);
// 和之前的操作是一樣的，都是保證數(shù)組的容量足夠
ensureCapacityInternal(size + 1); // Increments modCount!!
// 將指定位置及其后面數(shù)據(jù)向后移動(dòng)一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 將該元素添加到指定的數(shù)組位置
elementData[index] = element;
// ArrayList 的大小改變
size++;
}
可以看到每次插入指定位置都要移動(dòng)元素，效率較低。
再來(lái)看 LinkedList 的插入，也有插入末尾，插入指定位置兩種，由于基于鏈表，肯定得先有個(gè) 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;
}
}
public boolean add(E e) {
// 直接往隊(duì)尾加元素
linkLast(e);
return true;
}
void linkLast(E e) {
// 保存原來(lái)鏈表尾部節(jié)點(diǎn)，last 是全局變量，用來(lái)表示隊(duì)尾元素
final Node<E> l = last;
// 為該元素 e 新建一個(gè)節(jié)點(diǎn)
final Node<E> newNode = new Node<>(l, e, null);
// 將新節(jié)點(diǎn)設(shè)為隊(duì)尾
last = newNode;
// 如果原來(lái)的隊(duì)尾元素為空，那么說(shuō)明原來(lái)的整個(gè)列表是空的，就把新節(jié)點(diǎn)賦值給頭結(jié)點(diǎn)
if (l == null)
first = newNode;
else
// 原來(lái)尾結(jié)點(diǎn)的后面為新生成的結(jié)點(diǎn)
l.next = newNode;
// 節(jié)點(diǎn)數(shù) +1
size++;
modCount++;
}
public void add(int index, E element) {
// 檢查 index 有沒(méi)有超出索引范圍
checkPositionIndex(index);
// 如果追加到尾部，那么就跟 add(E e) 一樣了
if (index == size)
linkLast(element);
else
// 否則就是插在其他位置
linkBefore(element, node(index));
}
//linkBefore方法中調(diào)用了這個(gè)node方法，類似二分查找的優(yōu)化
Node<E> node(int index) {
// assert isElementIndex(index);
// 如果 index 在前半段，從前往后遍歷獲取 node
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 如果 index 在后半段，從后往前遍歷獲取 node
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// 保存 index 節(jié)點(diǎn)的前節(jié)點(diǎn)
final Node<E> pred = succ.prev;
// 新建一個(gè)目標(biāo)節(jié)點(diǎn)
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
// 如果是在開(kāi)頭處插入的話
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
獲取
ArrayList 的 get() 方法很簡(jiǎn)單，就是在數(shù)組中返回指定位置的元素即可，所以效率很高
public E get(int index) {
// 檢查 index 有沒(méi)有超出索引的范圍
rangeCheck(index);
// 返回指定位置的元素
return elementData(index);
}
LinkedList 的 get() 方法，就是在內(nèi)部調(diào)用了上邊看到的 node() 方法，判斷在前半段還是在后半段，然后遍歷得到即可。
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
HashMap的底層實(shí)現(xiàn)
什么時(shí)候會(huì)使用HashMap？他有什么特點(diǎn)？
你知道HashMap的工作原理嗎？
你知道get和put的原理嗎？equals()和hashCode()的都有什么作用？
你知道hash的實(shí)現(xiàn)嗎？為什么要這樣實(shí)現(xiàn)？
如果HashMap的大小超過(guò)了負(fù)載因子(load factor)定義的容量，怎么辦？
HashMap 在 JDK 7 和 JDK8 中的實(shí)現(xiàn)方式略有不同。分開(kāi)記錄。
深入 HahsMap 之前，先要了解的概念
-
initialCapacity：初始容量。指的是 HashMap 集合初始化的時(shí)候自身的容量。可以在構(gòu)造方法中指定；如果不指定的話，總?cè)萘磕J(rèn)值是 16 。需要注意的是初始容量必須是 2 的冪次方。（1.7中，已知HashMap中將要存放的KV個(gè)數(shù)的時(shí)候，設(shè)置一個(gè)合理的初始化容量可以有效的提高性能）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 size：當(dāng)前 HashMap 中已經(jīng)存儲(chǔ)著的鍵值對(duì)數(shù)量，即
HashMap.size()。loadFactor：加載因子。所謂的加載因子就是 HashMap (當(dāng)前的容量/總?cè)萘? 到達(dá)一定值的時(shí)候，HashMap 會(huì)實(shí)施擴(kuò)容。加載因子也可以通過(guò)構(gòu)造方法中指定，默認(rèn)的值是 0.75 。舉個(gè)例子，假設(shè)有一個(gè) HashMap 的初始容量為 16 ，那么擴(kuò)容的閥值就是 0.75 * 16 = 12 。也就是說(shuō)，在你打算存入第 13 個(gè)值的時(shí)候，HashMap 會(huì)先執(zhí)行擴(kuò)容。
threshold：擴(kuò)容閥值。即 擴(kuò)容閥值 = HashMap 總?cè)萘?* 加載因子。當(dāng)前 HashMap 的容量大于或等于擴(kuò)容閥值的時(shí)候就會(huì)去執(zhí)行擴(kuò)容。擴(kuò)容的容量為當(dāng)前 HashMap 總?cè)萘康膬杀丁１热?，?dāng)前 HashMap 的總?cè)萘繛?16 ，那么擴(kuò)容之后為 32 。
table：Entry 數(shù)組。我們都知道 HashMap 內(nèi)部存儲(chǔ) key/value 是通過(guò) Entry 這個(gè)介質(zhì)來(lái)實(shí)現(xiàn)的。而 table 就是 Entry 數(shù)組。
JDK1.7 實(shí)現(xiàn)
JDK1.7 中 HashMap 由 數(shù)組+鏈表 組成（“鏈表散列” 即數(shù)組和鏈表的結(jié)合體），數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的（HashMap 采用 “拉鏈法也就是鏈地址法” 解決沖突），如果定位到的數(shù)組位置不含鏈表（當(dāng)前 entry 的 next 指向 null ）,那么對(duì)于查找，添加等操作很快，僅需一次尋址即可；如果定位到的數(shù)組包含鏈表，對(duì)于添加操作，其時(shí)間復(fù)雜度依然為 O(1)，因?yàn)樽钚碌?Entry 會(huì)插入鏈表頭部，即需要簡(jiǎn)單改變引用鏈即可，而對(duì)于查找操作來(lái)講，此時(shí)就需要遍歷鏈表，然后通過(guò) key 對(duì)象的 equals 方法逐一比對(duì)查找。
所謂 “拉鏈法” 就是將鏈表和數(shù)組相結(jié)合。也就是說(shuō)創(chuàng)建一個(gè)鏈表數(shù)組，數(shù)組中每一格就是一個(gè)鏈表。若遇到哈希沖突，則將沖突的值加到鏈表中即可。
源碼解析
構(gòu)造方法
《阿里巴巴 Java 開(kāi)發(fā)手冊(cè)》推薦集合初始化時(shí)，指定集合初始值大小。（說(shuō)明：HashMap 使用HashMap(int initialCapacity) 初始化）建議原因： https://www.zhihu.com/question/314006228/answer/611170521
// 默認(rèn)的構(gòu)造方法使用的都是默認(rèn)的初始容量和加載因子
// DEFAULT_INITIAL_CAPACITY = 16，DEFAULT_LOAD_FACTOR = 0.75f
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// 可以指定初始容量，并且使用默認(rèn)的加載因子
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
// 對(duì)初始容量的值判斷
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);
// 設(shè)置加載因子
this.loadFactor = loadFactor;
threshold = initialCapacity;
// 空方法
init();
}
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
HashMap 的前 3 個(gè)構(gòu)造方法最后都會(huì)去調(diào)用 HashMap(int initialCapacity, float loadFactor) 。在其內(nèi)部去設(shè)置初始容量和加載因子。而最后的 init() 是空方法，主要給子類實(shí)現(xiàn)，比如LinkedHashMap。
put() 方法
public V put(K key, V value) {
// 如果 table 數(shù)組為空時(shí)先創(chuàng)建數(shù)組，并且設(shè)置擴(kuò)容閥值
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果 key 為空時(shí)，調(diào)用 putForNullKey 方法特殊處理
if (key == null)
return putForNullKey(value);
// 計(jì)算 key 的哈希值
int hash = hash(key);
// 根據(jù)計(jì)算出來(lái)的哈希值和當(dāng)前數(shù)組的長(zhǎng)度計(jì)算在數(shù)組中的索引
int i = indexFor(hash, table.length);
// 先遍歷該數(shù)組索引下的整條鏈表
// 如果該 key 之前已經(jīng)在 HashMap 中存儲(chǔ)了的話，直接替換對(duì)應(yīng)的 value 值即可
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//先判斷hash值是否一樣，如果一樣，再判斷key是否一樣，不同對(duì)象的hash值可能一樣
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 如果該 key 之前沒(méi)有被存儲(chǔ)過(guò)，那么就進(jìn)入 addEntry 方法
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
// 當(dāng)前容量大于或等于擴(kuò)容閥值的時(shí)候，會(huì)執(zhí)行擴(kuò)容
if ((size >= threshold) && (null != table[bucketIndex])) {
// 擴(kuò)容為原來(lái)容量的兩倍
resize(2 * table.length);
// 重新計(jì)算哈希值
hash = (null != key) ? hash(key) : 0;
// 重新得到在新數(shù)組中的索引
bucketIndex = indexFor(hash, table.length);
}
// 創(chuàng)建節(jié)點(diǎn)
createEntry(hash, key, value, bucketIndex);
}
//擴(kuò)容，創(chuàng)建了一個(gè)新的數(shù)組，然后把數(shù)據(jù)全部復(fù)制過(guò)去，再把新數(shù)組的引用賦給 table
void resize(int newCapacity) {
Entry[] oldTable = table; //引用擴(kuò)容前的Entry數(shù)組
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //擴(kuò)容前的數(shù)組大小如果已經(jīng)達(dá)到最大(2^30)了
threshold = Integer.MAX_VALUE; //修改閾值為int的最大值(2^31-1)，這樣以后就不會(huì)擴(kuò)容了
return;
}
// 創(chuàng)建新的 entry 數(shù)組
Entry[] newTable = new Entry[newCapacity];
// 將舊 entry 數(shù)組中的數(shù)據(jù)復(fù)制到新 entry 數(shù)組中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 將新數(shù)組的引用賦給 table
table = newTable;
// 計(jì)算新的擴(kuò)容閥值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了舊的Entry數(shù)組
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍歷舊的Entry數(shù)組
Entry<K,V> e = src[j]; //取得舊Entry數(shù)組的每個(gè)元素
if (e != null) {
src[j] = null;//釋放舊Entry數(shù)組的對(duì)象引用（for循環(huán)后，舊的Entry數(shù)組不再引用任何對(duì)象）
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); //??！重新計(jì)算每個(gè)元素在數(shù)組中的位置
e.next = newTable[i]; //標(biāo)記[1]
newTable[i] = e; //將元素放在數(shù)組上
e = next; //訪問(wèn)下一個(gè)Entry鏈上的元素
} while (e != null);
}
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
// 取出table中下標(biāo)為bucketIndex的Entry
Entry<K,V> e = table[bucketIndex];
// 利用key、value來(lái)構(gòu)建新的Entry
// 并且之前存放在table[bucketIndex]處的Entry作為新Entry的next
// 把新創(chuàng)建的Entry放到table[bucketIndex]位置
table[bucketIndex] = new Entry<>(hash, key, value, e);
// 當(dāng)前 HashMap 的容量加 1
size++;
}
最后的 createEntry() 方法就說(shuō)明了當(dāng)hash沖突時(shí)，采用的拉鏈法來(lái)解決hash沖突的，并且是把新元素是插入到單邊表的表頭。
get() 方法
public V get(Object key) {
// 如果 key 是空的，就調(diào)用 getForNullKey 方法特殊處理
if (key == null)
return getForNullKey();
// 獲取 key 相對(duì)應(yīng)的 entry
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
//找到對(duì)應(yīng) key 的數(shù)組索引，然后遍歷鏈表查找即可
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
// 計(jì)算 key 的哈希值
int hash = (key == null) ? 0 : hash(key);
// 得到數(shù)組的索引，然后遍歷鏈表，查看是否有相同 key 的 Entry
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
// 沒(méi)有的話，返回 null
return null;
}
JDK1.8 實(shí)現(xiàn)
JDK 1.7 中，如果哈希碰撞過(guò)多，拉鏈過(guò)長(zhǎng)，極端情況下，所有值都落入了同一個(gè)桶內(nèi)，這就退化成了一個(gè)鏈表。通過(guò) key 值查找要遍歷鏈表，效率較低。 JDK1.8在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹(shù)，以減少搜索時(shí)間。
TreeMap、TreeSet以及 JDK1.8 之后的 HashMap 底層都用到了紅黑樹(shù)。紅黑樹(shù)就是為了解決二叉查找樹(shù)的缺陷，因?yàn)槎娌檎覙?shù)在某些情況下會(huì)退化成一個(gè)線性結(jié)構(gòu)。
源碼解析
構(gòu)造方法
JDK8 構(gòu)造方法改動(dòng)不是很大
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
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);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
確定哈希桶數(shù)組索引位置（hash 函數(shù)的實(shí)現(xiàn)）
//方法一：
static final int hash(Object key) { //jdk1.8 & jdk1.7
int h;
// h = key.hashCode() 為第一步 取hashCode值
// h ^ (h >>> 16) 為第二步 高位參與運(yùn)算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//方法二：
static int indexFor(int h, int length) { //jdk1.7的源碼，jdk1.8沒(méi)有提取這個(gè)方法，而是放在了其他方法中，比如 put 的p = tab[i = (n - 1) & hash]
return h & (length-1); //第三步 取模運(yùn)算
}
HashMap定位數(shù)組索引位置，直接決定了hash方法的離散性能。Hash算法本質(zhì)上就是三步：取key的hashCode值、高位運(yùn)算、取模運(yùn)算。
為什么要這樣呢？
HashMap 的長(zhǎng)度為什么是2的冪次方?
目的當(dāng)然是為了減少哈希碰撞，使 table 里的數(shù)據(jù)分布的更均勻。
-
HashMap 中桶數(shù)組的大小 length 總是2的冪，此時(shí)，
h & (table.length -1)等價(jià)于對(duì) length 取模h%length。但取模的計(jì)算效率沒(méi)有位運(yùn)算高，所以這是是一個(gè)優(yōu)化。假設(shè)h = 185，table.length-1 = 15(0x1111)，其實(shí)散列真正生效的只是低 4bit 的有效位，所以很容易碰撞。img -
圖中的 hash 是由鍵的 hashCode 產(chǎn)生。計(jì)算余數(shù)時(shí)，由于 n 比較小，hash 只有低4位參與了計(jì)算，高位的計(jì)算可以認(rèn)為是無(wú)效的。這樣導(dǎo)致了計(jì)算結(jié)果只與低位信息有關(guān)，高位數(shù)據(jù)沒(méi)發(fā)揮作用。為了處理這個(gè)缺陷，我們可以上圖中的 hash 高4位數(shù)據(jù)與低4位數(shù)據(jù)進(jìn)行異或運(yùn)算，即
hash ^ (hash >>> 4)。通過(guò)這種方式，讓高位數(shù)據(jù)與低位數(shù)據(jù)進(jìn)行異或，以此加大低位信息的隨機(jī)性，變相的讓高位數(shù)據(jù)參與到計(jì)算中。此時(shí)的計(jì)算過(guò)程如下：img在 Java 中，hashCode 方法產(chǎn)生的 hash 是 int 類型，32 位寬。前16位為高位，后16位為低位，所以要右移16位，即
hash ^ (hash >>> 16)。這樣還增加了hash 的復(fù)雜度，進(jìn)而影響 hash 的分布性。
HashMap 的長(zhǎng)度為什么是2的冪次方？
為了能讓HashMap存取高效，盡量減少碰撞，也就是要盡量把數(shù)據(jù)分配均勻，Hash值的范圍是-2147483648到2147483647，前后加起來(lái)有40億的映射空間，只要哈希函數(shù)映射的比較均勻松散，一般應(yīng)用是很難出現(xiàn)碰撞的，但一個(gè)問(wèn)題是40億的數(shù)組內(nèi)存是放不下的。所以這個(gè)散列值是不能直接拿來(lái)用的。用之前需要先對(duì)數(shù)組長(zhǎng)度取模運(yùn)算，得到余數(shù)才能用來(lái)存放位置也就是對(duì)應(yīng)的數(shù)組小標(biāo)。這個(gè)數(shù)組下標(biāo)的計(jì)算方法是(n-1)&hash，n代表數(shù)組長(zhǎng)度
這個(gè)算法應(yīng)該如何設(shè)計(jì)呢？
我們首先可能會(huì)想到采用%取余的操作來(lái)實(shí)現(xiàn)。但是，重點(diǎn)來(lái)了。
取余操作中如果除數(shù)是2的冪次則等價(jià)于其除數(shù)減一的與操作，也就是說(shuō)hash%length=hash&(length-1)，但前提是length是2的n次方，并且采用&運(yùn)算比%運(yùn)算效率高，這也就解釋了HashMap的長(zhǎng)度為什么是2的冪次方。
put() 方法
public V put(K key, V value) {
// 對(duì)key的hashCode()做hash
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;
// tab為空則創(chuàng)建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 計(jì)算index，并對(duì)null做處理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 節(jié)點(diǎn)key存在，直接覆蓋value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 判斷該鏈為紅黑樹(shù)
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);
//鏈表長(zhǎng)度大于8轉(zhuǎn)換為紅黑樹(shù)進(jì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;
// 超過(guò)最大容量 就擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
resize() 擴(kuò)容
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) {
// 超過(guò)最大值就不再擴(kuò)充了，就只好隨你碰撞了
if (oldCap >= MAXIMUM_CAPACITY) {
//修改閾值為int的最大值(2^31-1)，這樣以后就不會(huì)擴(kuò)容了
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 沒(méi)超過(guò)最大值，就擴(kuò)充為原來(lái)的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 { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計(jì)算新的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;
// 把每個(gè)bucket都移動(dòng)到新的buckets中
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 鏈表優(yōu)化重hash的代碼塊
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;
}
get() 方法
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;
//定位鍵值對(duì)所在桶的位置
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) {
// 如果 first 是 TreeNode 類型，則調(diào)用黑紅樹(shù)查找方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 在鏈表中查找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
Hashtable
Hashtable 和 HashMap 都是散列表，也是用”拉鏈法“實(shí)現(xiàn)的哈希表。保存數(shù)據(jù)和 JDK7 中的 HashMap 一樣，是 Entity 對(duì)象，只是 Hashtable 中的幾乎所有的 public 方法都是 synchronized 的，而有些方法也是在內(nèi)部通過(guò) synchronized 代碼塊來(lái)實(shí)現(xiàn)，效率肯定會(huì)降低。且 put() 方法不允許空值。
HashMap 和 Hashtable 的區(qū)別
線程是否安全： HashMap 是非線程安全的，HashTable 是線程安全的；HashTable 內(nèi)部的方法基本都經(jīng)過(guò)
synchronized修飾。（如果你要保證線程安全的話就使用 ConcurrentHashMap 吧?。?；效率： 因?yàn)榫€程安全的問(wèn)題，HashMap 要比 HashTable 效率高一點(diǎn)。另外，HashTable 基本被淘汰，不要在代碼中使用它；
對(duì)Null key 和Null value的支持： HashMap 中，null 可以作為鍵，這樣的鍵只有一個(gè)，可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為 null。。但是在 HashTable 中 put 進(jìn)的鍵值只要有一個(gè) null，直接拋出 NullPointerException。
-
初始容量大小和每次擴(kuò)充容量大小的不同 ：
① 創(chuàng)建時(shí)如果不指定容量初始值，Hashtable 默認(rèn)的初始大小為11，之后每次擴(kuò)充，容量變?yōu)樵瓉?lái)的2n+1。HashMap 默認(rèn)的初始化大小為16。之后每次擴(kuò)充，容量變?yōu)樵瓉?lái)的2倍。
② 創(chuàng)建時(shí)如果給定了容量初始值，那么 Hashtable 會(huì)直接使用你給定的大小，而 HashMap 會(huì)將其擴(kuò)充為2的冪次方大小。也就是說(shuō) HashMap 總是使用2的冪次方作為哈希表的大小,后面會(huì)介紹到為什么是2的冪次方。
底層數(shù)據(jù)結(jié)構(gòu)： JDK1.8 以后的 HashMap 在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹(shù)，以減少搜索時(shí)間。Hashtable 沒(méi)有這樣的機(jī)制。
HashMap的迭代器（
Iterator）是fail-fast迭代器，但是 Hashtable的迭代器（enumerator）不是 fail-fast的。如果有其它線程對(duì)HashMap進(jìn)行的添加/刪除元素，將會(huì)拋出ConcurrentModificationException，但迭代器本身的remove方法移除元素則不會(huì)拋出異常。這條同樣也是 Enumeration 和 Iterator 的區(qū)別。
ConcurrentHashMap
HashMap在多線程情況下，在put的時(shí)候，插入的元素超過(guò)了容量（由負(fù)載因子決定）的范圍就會(huì)觸發(fā)擴(kuò)容操作，就是rehash，這個(gè)會(huì)重新將原數(shù)組的內(nèi)容重新hash到新的擴(kuò)容數(shù)組中，在多線程的環(huán)境下，存在同時(shí)其他的元素也在進(jìn)行put操作，如果hash值相同，可能出現(xiàn)同時(shí)在同一數(shù)組下用鏈表表示，造成閉環(huán)，導(dǎo)致在get時(shí)會(huì)出現(xiàn)死循環(huán)，所以HashMap是線程不安全的。
Hashtable，是線程安全的，它在所有涉及到多線程操作的都加上了synchronized關(guān)鍵字來(lái)鎖住整個(gè)table，這就意味著所有的線程都在競(jìng)爭(zhēng)一把鎖，在多線程的環(huán)境下，它是安全的，但是無(wú)疑是效率低下的。
JDK1.7 實(shí)現(xiàn)
Hashtable 容器在競(jìng)爭(zhēng)激烈的并發(fā)環(huán)境下表現(xiàn)出效率低下的原因，是因?yàn)樗性L問(wèn) Hashtable 的線程都必須競(jìng)爭(zhēng)同一把鎖，那假如容器里有多把鎖，每一把鎖用于鎖容器其中一部分?jǐn)?shù)據(jù)，那么當(dāng)多線程訪問(wèn)容器里不同數(shù)據(jù)段的數(shù)據(jù)時(shí)，線程間就不會(huì)存在鎖競(jìng)爭(zhēng)，，這就是ConcurrentHashMap所使用的鎖分段技術(shù)。
在 JDK1.7版本中，ConcurrentHashMap 的數(shù)據(jù)結(jié)構(gòu)是由一個(gè) Segment 數(shù)組和多個(gè) HashEntry 組成。Segment 數(shù)組的意義就是將一個(gè)大的 table 分割成多個(gè)小的 table 來(lái)進(jìn)行加鎖。每一個(gè) Segment 元素存儲(chǔ)的是 HashEntry數(shù)組+鏈表，這個(gè)和 HashMap 的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)一樣。
ConcurrentHashMap 類中包含兩個(gè)靜態(tài)內(nèi)部類 HashEntry 和 Segment。
HashEntry 用來(lái)封裝映射表的鍵值對(duì)，Segment 用來(lái)充當(dāng)鎖的角色，每個(gè) Segment 對(duì)象守護(hù)整個(gè)散列映射表的若干個(gè)桶。每個(gè)桶是由若干個(gè) HashEntry 對(duì)象鏈接起來(lái)的鏈表。一個(gè) ConcurrentHashMap 實(shí)例中包含由若干個(gè) Segment 對(duì)象組成的數(shù)組。每個(gè) Segment 守護(hù)著一個(gè) HashEntry 數(shù)組里的元素，當(dāng)對(duì) HashEntry 數(shù)組的數(shù)據(jù)進(jìn)行修改時(shí)，必須首先獲得它對(duì)應(yīng)的 Segment 鎖。
Segment 類
Segment 類繼承于 ReentrantLock 類，從而使得 Segment 對(duì)象能充當(dāng)可重入鎖的角色。一個(gè) Segment 就是一個(gè)子哈希表，Segment 里維護(hù)了一個(gè) HashEntry 數(shù)組，并發(fā)環(huán)境下，對(duì)于不同 Segment 的數(shù)據(jù)進(jìn)行操作是不用考慮鎖競(jìng)爭(zhēng)的。
從源碼可以看到，Segment 內(nèi)部類和我們上邊看到的 HashMap 很相似。也有負(fù)載因子，閾值等各種屬性。
static final class Segment<K,V> extends ReentrantLock implements Serializable {
static final int MAX_SCAN_RETRIES =
Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
transient volatile HashEntry<K,V>[] table;
transient int count;
transient int modCount; //記錄修改次數(shù)
transient int threshold;
final float loadFactor;
Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
this.loadFactor = lf;
this.threshold = threshold;
this.table = tab;
}
//put 方法會(huì)有加鎖操作，
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
// ...
}
@SuppressWarnings("unchecked")
private void rehash(HashEntry<K,V> node) {
// ...
}
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
//...
}
private void scanAndLock(Object key, int hash) {
//...
}
final V remove(Object key, int hash, Object value) {
//...
}
final boolean replace(K key, int hash, V oldValue, V newValue) {
//...
}
final V replace(K key, int hash, V value) {
//...
}
final void clear() {
//...
}
}
HashEntry 類
HashEntry 是目前我們最小的邏輯處理單元。一個(gè)ConcurrentHashMap 維護(hù)一個(gè) Segment 數(shù)組，一個(gè)Segment維護(hù)一個(gè) HashEntry 數(shù)組。
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value; // value 為 volatie 類型，保證可見(jiàn)
volatile HashEntry<K,V> next;
//...
}
ConcurrentHashMap 類
默認(rèn)的情況下，每個(gè)ConcurrentHashMap 類會(huì)創(chuàng)建16個(gè)并發(fā)的 segment，每個(gè) segment 里面包含多個(gè) Hash表，每個(gè) Hash 鏈都是由 HashEntry 節(jié)點(diǎn)組成的。
public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
implements ConcurrentMap<K, V>, Serializable {
//默認(rèn)初始容量為 16，即初始默認(rèn)為 16 個(gè)桶
static final int DEFAULT_INITIAL_CAPACITY = 16;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//默認(rèn)并發(fā)級(jí)別為 16。該值表示當(dāng)前更新線程的估計(jì)數(shù)
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
static final int RETRIES_BEFORE_LOCK = 2;
final int segmentMask; //段掩碼,主要為了定位Segment
final int segmentShift;
final Segment<K,V>[] segments; //主干就是這個(gè)分段鎖數(shù)組
//構(gòu)造器
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
//MAX_SEGMENTS 為1<<16=65536，也就是最大并發(fā)數(shù)為65536
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// 2的sshif次方等于ssize，例:ssize=16,sshift=4;ssize=32,sshif=5
int sshift = 0;
// ssize 為segments數(shù)組長(zhǎng)度，根據(jù)concurrentLevel計(jì)算得出
int ssize = 1;
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
cap <<= 1;
// 創(chuàng)建segments數(shù)組并初始化第一個(gè)Segment，其余的Segment延遲初始化
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
}
put() 方法
- **定位segment并確保定位的Segment已初始化 **
- 調(diào)用 Segment的 put 方法。
public V put(K key, V value) {
Segment<K,V> s;
//concurrentHashMap不允許key/value為空
if (value == null)
throw new NullPointerException();
//hash函數(shù)對(duì)key的hashCode重新散列，避免差勁的不合理的hashcode，保證散列均勻
int hash = hash(key);
//返回的hash值無(wú)符號(hào)右移segmentShift位與段掩碼進(jìn)行位運(yùn)算，定位segment
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
get() 方法
get方法無(wú)需加鎖，由于其中涉及到的共享變量都使用volatile修飾，volatile可以保證內(nèi)存可見(jiàn)性，所以不會(huì)讀取到過(guò)期數(shù)據(jù)
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}
JDK1.8 實(shí)現(xiàn)
ConcurrentHashMap 在 JDK8 中進(jìn)行了巨大改動(dòng)，光是代碼量就從1000多行增加到6000行！1.8摒棄了Segment(鎖段)的概念，采用了 CAS + synchronized 來(lái)保證并發(fā)的安全性。
可以看到，和HashMap 1.8的數(shù)據(jù)結(jié)構(gòu)很像。底層數(shù)據(jù)結(jié)構(gòu)改變?yōu)椴捎脭?shù)組+鏈表+紅黑樹(shù)的數(shù)據(jù)形式。
和HashMap1.8相同的一些地方
- 底層數(shù)據(jù)結(jié)構(gòu)一致
- HashMap初始化是在第一次put元素的時(shí)候進(jìn)行的，而不是init
- HashMap的底層數(shù)組長(zhǎng)度總是為2的整次冪
- 默認(rèn)樹(shù)化的閾值為 8，而鏈表化的閾值為 6
- hash算法也很類似，但多了一步
& HASH_BITS，該步是為了消除最高位上的負(fù)符號(hào)，hash的負(fù)在ConcurrentHashMap中有特殊意義表示在擴(kuò)容或者是樹(shù)節(jié)點(diǎn)
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
一些關(guān)鍵屬性
private static final int MAXIMUM_CAPACITY = 1 << 30; //數(shù)組最大大小 同HashMap
private static final int DEFAULT_CAPACITY = 16;//數(shù)組默認(rèn)大小
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //數(shù)組可能最大值，需要與toArray（）相關(guān)方法關(guān)聯(lián)
private static final int DEFAULT_CONCURRENCY_LEVEL = 16; //兼容舊版保留的值，默認(rèn)線程并發(fā)度，類似信號(hào)量
private static final float LOAD_FACTOR = 0.75f;//默認(rèn)map擴(kuò)容比例，實(shí)際用(n << 1) - (n >>> 1)代替了更高效
static final int TREEIFY_THRESHOLD = 8; // 鏈表轉(zhuǎn)樹(shù)閥值，大于8時(shí)
static final int UNTREEIFY_THRESHOLD = 6; //樹(shù)轉(zhuǎn)鏈表閥值，小于等于6（tranfer時(shí)，lc、hc=0兩個(gè)計(jì)數(shù)器分別++記錄原bin、新binTreeNode數(shù)量，<=UNTREEIFY_THRESHOLD 則untreeify(lo)）。【僅在擴(kuò)容tranfer時(shí)才可能樹(shù)轉(zhuǎn)鏈表】
static final int MIN_TREEIFY_CAPACITY = 64;
private static final int MIN_TRANSFER_STRIDE = 16;//擴(kuò)容轉(zhuǎn)移時(shí)的最小數(shù)組分組大小
private static int RESIZE_STAMP_BITS = 16;//本類中沒(méi)提供修改的方法 用來(lái)根據(jù)n生成位置一個(gè)類似時(shí)間戳的功能
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; // 2^15-1，help resize的最大線程數(shù)
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; // 32-16=16，sizeCtl中記錄size大小的偏移量
static final int MOVED = -1; // hash for forwarding nodes（forwarding nodes的hash值）、標(biāo)示位
static final int TREEBIN = -2; // hash for roots of trees（樹(shù)根節(jié)點(diǎn)的hash值）
static final int RESERVED = -3; // ReservationNode的hash值
static final int HASH_BITS = 0x7fffffff; // 用在計(jì)算hash時(shí)進(jìn)行安位與計(jì)算消除負(fù)hash
static final int NCPU = Runtime.getRuntime().availableProcessors(); // 可用處理器數(shù)量
/* ---------------- Fields -------------- */
transient volatile Node<K,V>[] table; //裝載Node的數(shù)組，作為ConcurrentHashMap的數(shù)據(jù)容器，采用懶加載的方式，直到第一次插入數(shù)據(jù)的時(shí)候才會(huì)進(jìn)行初始化操作，數(shù)組的大小總是為2的冪次方。
private transient volatile Node<K,V>[] nextTable; //擴(kuò)容時(shí)使用，平時(shí)為null，只有在擴(kuò)容的時(shí)候才為非null
/**
* 實(shí)際上保存的是hashmap中的元素個(gè)數(shù) 利用CAS鎖進(jìn)行更新但它并不用返回當(dāng)前hashmap的元素個(gè)數(shù)
*/
private transient volatile long baseCount;
/**
*該屬性用來(lái)控制table數(shù)組的大小，根據(jù)是否初始化和是否正在擴(kuò)容有幾種情況：
*當(dāng)值為負(fù)數(shù)時(shí)：如果為-1表示正在初始化，如果為-N則表示當(dāng)前正有N-1個(gè)線程進(jìn)行擴(kuò)容操作；
*當(dāng)值為正數(shù)時(shí)：如果當(dāng)前數(shù)組為null的話表示table在初始化過(guò)程中，sizeCtl表示為需要新建數(shù)組的長(zhǎng)度；若已經(jīng)初始化了，表示當(dāng)前數(shù)據(jù)容器（table數(shù)組）可用容量也可以理解成臨界值（插入節(jié)點(diǎn)數(shù)超過(guò)了該臨界值就需要擴(kuò)容），具體指為數(shù)組的長(zhǎng)度n 乘以 加載因子loadFactor；當(dāng)值為0時(shí)，即數(shù)組長(zhǎng)度為默認(rèn)初始值。
*/
private transient volatile int sizeCtl;
put() 方法
- 首先會(huì)判斷 key、value是否為空，如果為空就拋異常！
-
spread()方法獲取hash，減小hash沖突 - 判斷是否初始化table數(shù)組，沒(méi)有的話調(diào)用
initTable()方法進(jìn)行初始化 - 判斷是否能直接將新值插入到table數(shù)組中
- 判斷當(dāng)前是否在擴(kuò)容，
MOVED為-1說(shuō)明當(dāng)前ConcurrentHashMap正在進(jìn)行擴(kuò)容操作，正在擴(kuò)容的話就進(jìn)行協(xié)助擴(kuò)容 - 當(dāng)table[i]為鏈表的頭結(jié)點(diǎn)，在鏈表中插入新值，通過(guò)synchronized (f)的方式進(jìn)行加鎖以實(shí)現(xiàn)線程安全性。
- 在鏈表中如果找到了與待插入的鍵值對(duì)的key相同的節(jié)點(diǎn)，就直接覆蓋
- 如果沒(méi)有找到的話，就直接將待插入的鍵值對(duì)追加到鏈表的末尾
- 當(dāng)table[i]為紅黑樹(shù)的根節(jié)點(diǎn)，在紅黑樹(shù)中插入新值/覆蓋舊值
- 根據(jù)當(dāng)前節(jié)點(diǎn)個(gè)數(shù)進(jìn)行調(diào)整，否需要轉(zhuǎn)換成紅黑樹(shù)(個(gè)數(shù)大于等于8，就會(huì)調(diào)用
treeifyBin方法將tabel[i]第i個(gè)散列桶拉鏈轉(zhuǎn)換成紅黑樹(shù)) - 對(duì)當(dāng)前容量大小進(jìn)行檢查，如果超過(guò)了臨界值（實(shí)際大小*加載因子）就進(jìn)行擴(kuò)容
final V putVal(K key, V value, boolean onlyIfAbsent) {
// key 和 value 均不允許為 null
if (key == null || value == null) throw new NullPointerException();
// 根據(jù) key 計(jì)算出 hash 值
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 判斷是否需要進(jìn)行初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// f 即為當(dāng)前 key 定位出的 Node，如果為空表示當(dāng)前位置可以寫入數(shù)據(jù)，利用 CAS 嘗試寫入，失敗則自旋保證成功
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 如果當(dāng)前位置的 hashcode == MOVED == -1,則需要進(jìn)行擴(kuò)容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// 如果都不滿足，則利用 synchronized 鎖寫入數(shù)據(jù)
else {
// 剩下情況又分兩種，插入鏈表、插入紅黑樹(shù)
V oldVal = null;
//采用同步內(nèi)置鎖實(shí)現(xiàn)并發(fā)控制
synchronized (f) {
if (tabAt(tab, i) == f) {
// 如果 fh=f.hash >=0，當(dāng)前為鏈表，在鏈表中插入新的鍵值對(duì)
if (fh >= 0) {
binCount = 1;
//遍歷鏈表，如果找到對(duì)應(yīng)的 node 節(jié)點(diǎn)，修改 value,否則直接在鏈表尾部加入節(jié)點(diǎn)
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 當(dāng)前為紅黑樹(shù)，將新的鍵值對(duì)插入到紅黑樹(shù)中
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
// 插入完鍵值對(duì)后再根據(jù)實(shí)際大小看是否需要轉(zhuǎn)換成紅黑樹(shù)
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 對(duì)當(dāng)前容量大小進(jìn)行檢查，如果超過(guò)了臨界值（實(shí)際大小*加載因子）就需要擴(kuò)容
addCount(1L, binCount);
return null;
}
我們可以發(fā)現(xiàn)JDK8中的實(shí)現(xiàn)也是鎖分離的思想，只是鎖住的是一個(gè)Node，而不是JDK7中的Segment，而鎖住Node之前的操作是無(wú)鎖的并且也是線程安全的，建立在之前提到的原子操作上。
get() 方法
get方法無(wú)需加鎖，由于其中涉及到的共享變量都使用volatile修飾，volatile可以保證內(nèi)存可見(jiàn)性，所以不會(huì)讀取到過(guò)期數(shù)據(jù)
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
// 判斷數(shù)組是否為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 判斷node 節(jié)點(diǎn)第一個(gè)元素是不是要找的，如果是直接返回
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// // hash小于0,說(shuō)明是特殊節(jié)點(diǎn)（TreeBin或ForwardingNode）調(diào)用find
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
// 不是上面的情況,那就是鏈表了,遍歷鏈表
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
Hashtable 和 ConcurrentHashMap 的區(qū)別
ConcurrentHashMap 和 Hashtable 的區(qū)別主要體現(xiàn)在實(shí)現(xiàn)線程安全的方式上不同。
- 底層數(shù)據(jù)結(jié)構(gòu)： JDK1.7的 ConcurrentHashMap 底層采用 分段的數(shù)組+鏈表 實(shí)現(xiàn)，JDK1.8 采用的數(shù)據(jù)結(jié)構(gòu)和HashMap1.8的結(jié)構(gòu)類似，數(shù)組+鏈表/紅黑二叉樹(shù)。Hashtable 和 JDK1.8 之前的 HashMap 的底層數(shù)據(jù)結(jié)構(gòu)類似都是采用 數(shù)組+鏈表 的形式，數(shù)組是 HashMap 的主體，鏈表則是主要為了解決哈希沖突而存在的；
-
實(shí)現(xiàn)線程安全的方式（重要）：
- 在JDK1.7的時(shí)候，ConcurrentHashMap（分段鎖） 對(duì)整個(gè)桶數(shù)組進(jìn)行了分割分段(Segment)，每一把鎖只鎖容器其中一部分?jǐn)?shù)據(jù)，多線程訪問(wèn)容器里不同數(shù)據(jù)段的數(shù)據(jù)，就不會(huì)存在鎖競(jìng)爭(zhēng)，提高并發(fā)訪問(wèn)率。（默認(rèn)分配16個(gè)Segment，比Hashtable效率提高16倍。） 到了 JDK1.8 的時(shí)候已經(jīng)摒棄了Segment的概念，而是直接用 Node 數(shù)組+鏈表/紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，并發(fā)控制使用 synchronized 和 CAS 來(lái)操作。（JDK1.6以后 對(duì) synchronized鎖做了很多優(yōu)化） 整個(gè)看起來(lái)就像是優(yōu)化過(guò)且線程安全的 HashMap，雖然在 JDK1.8 中還能看到 Segment 的數(shù)據(jù)結(jié)構(gòu)，但是已經(jīng)簡(jiǎn)化了屬性，只是為了兼容舊版本；
- Hashtable(同一把鎖) :使用 synchronized 來(lái)保證線程安全，效率非常低下。當(dāng)一個(gè)線程訪問(wèn)同步方法時(shí)，其他線程也訪問(wèn)同步方法，可能會(huì)進(jìn)入阻塞或輪詢狀態(tài)，如使用 put 添加元素，另一個(gè)線程不能使用 put 添加元素，也不能使用 get，競(jìng)爭(zhēng)越激烈效率越低。
Java快速失?。╢ail-fast）和安全失敗（fail-safe）區(qū)別
快速失?。╢ail—fast）
在用迭代器遍歷一個(gè)集合對(duì)象時(shí)，如果遍歷過(guò)程中對(duì)集合對(duì)象的內(nèi)容進(jìn)行了修改（增加、刪除、修改），則會(huì)拋出ConcurrentModificationException。
原理：迭代器在遍歷時(shí)直接訪問(wèn)集合中的內(nèi)容，并且在遍歷過(guò)程中使用一個(gè) modCount 變量。集合在被遍歷期間如果內(nèi)容發(fā)生變化，就會(huì)改變 modCount 的值。每當(dāng)?shù)魇褂?hashNext()/next() 遍歷下一個(gè)元素之前，都會(huì)檢測(cè) modCount 變量是否為 expectedmodCount 值，是的話就返回遍歷；否則拋出異常，終止遍歷。
注意：這里異常的拋出條件是檢測(cè)到 modCount！=expectedmodCount 這個(gè)條件。如果集合發(fā)生變化時(shí)修改modCount 值剛好又設(shè)置為了 expectedmodCount 值，則異常不會(huì)拋出。因此，不能依賴于這個(gè)異常是否拋出而進(jìn)行并發(fā)操作的編程，這個(gè)異常只建議用于檢測(cè)并發(fā)修改的bug。
場(chǎng)景：java.util包下的集合類都是快速失敗的，不能在多線程下發(fā)生并發(fā)修改（迭代過(guò)程中被修改）。
安全失?。╢ail—safe）
采用安全失敗機(jī)制的集合容器，在遍歷時(shí)不是直接在集合內(nèi)容上訪問(wèn)的，而是先復(fù)制原有集合內(nèi)容，在拷貝的集合上進(jìn)行遍歷。
原理：由于迭代時(shí)是對(duì)原集合的拷貝進(jìn)行遍歷，所以在遍歷過(guò)程中對(duì)原集合所作的修改并不能被迭代器檢測(cè)到，所以不會(huì)觸發(fā) Concurrent Modification Exception。
缺點(diǎn)：基于拷貝內(nèi)容的優(yōu)點(diǎn)是避免了Concurrent Modification Exception，但同樣地，迭代器并不能訪問(wèn)到修改后的內(nèi)容，即：迭代器遍歷的是開(kāi)始遍歷那一刻拿到的集合拷貝，在遍歷期間原集合發(fā)生的修改迭代器是不知道的。
場(chǎng)景：java.util.concurrent包下的容器都是安全失敗，可以在多線程下并發(fā)使用，并發(fā)修改。
快速失敗和安全失敗是對(duì)迭代器而言的。 快速失?。寒?dāng)在迭代一個(gè)集合的時(shí)候，如果有另外一個(gè)線程在修改這個(gè)集合，就會(huì)拋出ConcurrentModification異常，java.util下都是快速失敗。 安全失?。涸诘鷷r(shí)候會(huì)在集合二層做一個(gè)拷貝，所以在修改集合上層元素不會(huì)影響下層。在java.util.concurrent下都是安全失敗
如何避免fail-fast ？
- 在單線程的遍歷過(guò)程中，如果要進(jìn)行remove操作，可以調(diào)用迭代器 ListIterator 的 remove 方法而不是集合類的 remove方法。看看 ArrayList中迭代器的 remove方法的源碼，該方法不能指定元素刪除，只能remove當(dāng)前遍歷元素。
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = ArrayList.this.modCount; //
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
- 使用并發(fā)包(
java.util.concurrent)中的類來(lái)代替 ArrayList 和 hashMap- CopyOnWriterArrayList 代替 ArrayList
- ConcurrentHashMap 代替 HashMap
Iterator 和 Enumeration 區(qū)別
在Java集合中，我們通常都通過(guò) “Iterator(迭代器)” 或 “Enumeration(枚舉類)” 去遍歷集合。
public interface Enumeration<E> {
boolean hasMoreElements();
E nextElement();
}
public interface Iterator<E> {
boolean hasNext();
E next();
void remove();
}
- 函數(shù)接口不同，Enumeration只有2個(gè)函數(shù)接口。通過(guò)Enumeration，我們只能讀取集合的數(shù)據(jù)，而不能對(duì)數(shù)據(jù)進(jìn)行修改。Iterator只有3個(gè)函數(shù)接口。Iterator除了能讀取集合的數(shù)據(jù)之外，也能數(shù)據(jù)進(jìn)行刪除操作。
-
Iterator支持 fail-fast機(jī)制，而Enumeration不支持。Enumeration 是JDK 1.0添加的接口。使用到它的函數(shù)包括Vector、Hashtable等類，這些類都是JDK 1.0中加入的，Enumeration存在的目的就是為它們提供遍歷接口。Enumeration本身并沒(méi)有支持同步，而在Vector、Hashtable實(shí)現(xiàn)Enumeration時(shí)，添加了同步。
而Iterator 是JDK 1.2才添加的接口，它也是為了HashMap、ArrayList等集合提供遍歷接口。Iterator是支持fail-fast機(jī)制的：當(dāng)多個(gè)線程對(duì)同一個(gè)集合的內(nèi)容進(jìn)行操作時(shí)，就可能會(huì)產(chǎn)生fail-fast事件
Comparable 和 Comparator接口有何區(qū)別？
Java中對(duì)集合對(duì)象或者數(shù)組對(duì)象排序，有兩種實(shí)現(xiàn)方式：
-
對(duì)象實(shí)現(xiàn)Comparable 接口
-
Comparable 在 java.lang 包下，是一個(gè)接口，內(nèi)部只有一個(gè)方法 compareTo()
public interface Comparable<T> { public int compareTo(T o); } Comparable 可以讓實(shí)現(xiàn)它的類的對(duì)象進(jìn)行比較，具體的比較規(guī)則是按照 compareTo 方法中的規(guī)則進(jìn)行。這種順序稱為 自然順序。
實(shí)現(xiàn)了 Comparable 接口的 List 或則數(shù)組可以使用
Collections.sort()或者Arrays.sort()方法進(jìn)行排序
-
-
定義比較器，實(shí)現(xiàn) Comparator接口
-
Comparator 在 java.util 包下，也是一個(gè)接口，JDK 1.8 以前只有兩個(gè)方法：
public interface Comparator<T> { public int compare(T lhs, T rhs); public boolean equals(Object object); }
-
comparable相當(dāng)于內(nèi)部比較器。comparator相當(dāng)于外部比較器
區(qū)別：
Comparator 位于
java.util包下，而 Comparable 位于java.lang包下Comparable 接口的實(shí)現(xiàn)是在類的內(nèi)部（如 String、Integer已經(jīng)實(shí)現(xiàn)了 Comparable 接口，自己就可以完成比較大小操作），Comparator 接口的實(shí)現(xiàn)是在類的外部（可以理解為一個(gè)是自已完成比較，一個(gè)是外部程序?qū)崿F(xiàn)比較）
-
實(shí)現(xiàn) Comparable 接口要重寫 compareTo 方法, 在 compareTo 方法里面實(shí)現(xiàn)比較。一個(gè)已經(jīng)實(shí)現(xiàn)Comparable 的類的對(duì)象或數(shù)據(jù)，可以通過(guò) Collections.sort(list) 或者 Arrays.sort(arr)實(shí)現(xiàn)排序。通過(guò) Collections.sort(list,Collections.reverseOrder()) 對(duì)list進(jìn)行倒序排列。
image -
實(shí)現(xiàn)Comparator需要重寫 compare 方法
image
HashSet
HashSet是用來(lái)存儲(chǔ)沒(méi)有重復(fù)元素的集合類，并且它是無(wú)序的。HashSet 內(nèi)部實(shí)現(xiàn)是基于 HashMap ，實(shí)現(xiàn)了 Set 接口。
從 HahSet 提供的構(gòu)造器可以看出，除了最后一個(gè) HashSet 的構(gòu)造方法外，其他所有內(nèi)部就是去創(chuàng)建一個(gè) Hashap 。沒(méi)有其他的操作。而最后一個(gè)構(gòu)造方法不是 public 的，所以不對(duì)外公開(kāi)。
HashSet如何檢查重復(fù)
HashSet的底層其實(shí)就是HashMap，只不過(guò)我們HashSet是實(shí)現(xiàn)了Set接口并且把數(shù)據(jù)作為K值，而V值一直使用一個(gè)相同的虛值來(lái)保存，HashMap的K值本身就不允許重復(fù)，并且在HashMap中如果K/V相同時(shí)，會(huì)用新的V覆蓋掉舊的V，然后返回舊的V。
Iterater 和 ListIterator 之間有什么區(qū)別？
- 我們可以使用Iterator來(lái)遍歷Set和List集合，而ListIterator只能遍歷List
- ListIterator有add方法，可以向List中添加對(duì)象，而Iterator不能
- ListIterator和Iterator都有hasNext()和next()方法，可以實(shí)現(xiàn)順序向后遍歷，但是ListIterator有hasPrevious()和previous()方法，可以實(shí)現(xiàn)逆向（順序向前）遍歷。Iterator不可以
- ListIterator可以定位當(dāng)前索引的位置，nextIndex()和previousIndex()可以實(shí)現(xiàn)。Iterator沒(méi)有此功能
- 都可實(shí)現(xiàn)刪除操作，但是 ListIterator可以實(shí)現(xiàn)對(duì)象的修改，set()方法可以實(shí)現(xiàn)。Iterator僅能遍歷，不能修改
參考與感謝
所有內(nèi)容都是基于源碼閱讀和各種大佬之前總結(jié)的知識(shí)整理而來(lái)，輸入并輸出，奧利給。
https://www.javatpoint.com/java-arraylist
https://www.runoob.com/java/java-collections.html
https://www.javazhiyin.com/21717.html
https://yuqirong.me/2018/01/31/LinkedList內(nèi)部原理解析/
https://youzhixueyuan.com/the-underlying-structure-and-principle-of-hashmap.html
《HashMap源碼詳細(xì)分析》http://www.tianxiaobo.com/2018/01/18/HashMap-源碼詳細(xì)分析-JDK1-8/
《ConcurrentHashMap1.7源碼分析》https://www.cnblogs.com/chengxiao/p/6842045.html
