Java Map 和 Set 全面解析
在Java編程中，Map 和 Set 是兩個(gè)非常重要的集合接口，它們?cè)跀?shù)據(jù)存儲(chǔ)和操作方面發(fā)揮著重要作用。無(wú)論是日常開(kāi)發(fā)還是技術(shù)面試，對(duì)這兩個(gè)接口的理解和應(yīng)用都是不可或缺的。
詳解Map集合
Map接口定義概覽
Map即映射集，是線上就是將對(duì)應(yīng)的key映射到對(duì)應(yīng)value上，由此構(gòu)成一個(gè)數(shù)學(xué)上的映射的概念，該適合存儲(chǔ)不可重復(fù)鍵值對(duì)類(lèi)型的元素，key不可重復(fù)，value可重復(fù)，我們可以通過(guò)key找到對(duì)應(yīng)的value:
An object that maps keys to values. A map cannot contain duplicate keys; each key can map to at most one value.
HashMap(重點(diǎn))
JDK1.8的HashMap默認(rèn)是由數(shù)組+鏈表/紅黑樹(shù)組成，通過(guò)key算得hash尋址從而定位到Map底層數(shù)組的索引位置。在進(jìn)行put操作時(shí)，若沖突時(shí)使用拉鏈法解決沖突，如下面這段代碼所示，當(dāng)相同索引位置存儲(chǔ)的是鏈表時(shí)，它會(huì)進(jìn)行for循環(huán)定位到相同hash值的索引位置的尾節(jié)點(diǎn)進(jìn)行追加。當(dāng)鏈表長(zhǎng)度大于8且數(shù)組長(zhǎng)度大于64的情況下，鏈表會(huì)進(jìn)行樹(shù)化變成紅黑樹(shù)，減少元素搜索時(shí)間。
注意 : 若長(zhǎng)度小于64鏈表長(zhǎng)度大于8只會(huì)HashMap底層數(shù)組的擴(kuò)容操作，對(duì)此我們給出Map進(jìn)行put操作時(shí)將元素添加到鏈表結(jié)尾的代碼段，可以看到當(dāng)鏈表元素大于等于8時(shí)會(huì)嘗試調(diào)用treeifyBin進(jìn)行樹(shù)化操作：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//......
for (int binCount = 0; ; ++binCount) {
//遍歷找到空位嘗試插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果鏈表元素加上本次插入元素大于8( TREEIFY_THRESHOLD )時(shí)，則嘗試進(jìn)行樹(shù)化操作
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//.......
}
//......
}對(duì)應(yīng)我們步入treeifyBin即可直接印證我們的邏輯，當(dāng)?shù)讓訑?shù)組空間小于64時(shí)只會(huì)進(jìn)行數(shù)組擴(kuò)容，而非針對(duì)當(dāng)前bucket的樹(shù)化操作：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//若當(dāng)前數(shù)組空間小于64則直接會(huì)進(jìn)行數(shù)組空間擴(kuò)容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {//反之進(jìn)行樹(shù)化操作
TreeNode<K,V> hd = null, tl = null;
do {
//......
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}詳解Hashtable核心添加操作
Hashtable底層也是由數(shù)組+鏈表(主要用于解決沖突)組成的，操作時(shí)都會(huì)上鎖，可以保證線程安全，底層數(shù)組是 Hashtable 的主體，在插入發(fā)生沖突時(shí)，會(huì)通過(guò)拉鏈法即將節(jié)點(diǎn)追加到同索引位置的節(jié)點(diǎn)后面：
public synchronized V put(K key, V value) {
//......
//插入元素尋址操作
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
//修改操作時(shí)，通過(guò)遍歷對(duì)應(yīng)index位置的鏈表完成覆蓋操作
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
//發(fā)生沖突時(shí)，會(huì)將節(jié)點(diǎn)追加到同索引位置的節(jié)點(diǎn)后面
addEntry(hash, key, value, index);
return null;詳解Set集合
Set基本核心概念
Set集合不可包重復(fù)的元素，即如果兩個(gè)元素在equals方法下判定為相等就只能存儲(chǔ)其中一個(gè)，這意味著該集合也最多包含一個(gè)null的元素，它常用于一些需要進(jìn)行去重的場(chǎng)景。
//HashSet底層復(fù)用了Map的put方法，value統(tǒng)一使用PRESENT對(duì)象
private static final Object PRESENT = new Object();
public boolean add(E e) {
// 返回null說(shuō)明當(dāng)前插入時(shí)并沒(méi)有覆蓋相同元素
return map.put(e, PRESENT)==null;
}Set有兩種我們比較熟悉的實(shí)現(xiàn)：
- HashSet:HashSet要求數(shù)據(jù)唯一，但是存儲(chǔ)是無(wú)序的(底層通過(guò)Hash算法實(shí)現(xiàn)尋址)，所以基于面向?qū)ο笏枷霃?fù)用原則，Java設(shè)計(jì)者就通過(guò)聚合關(guān)系封裝HashMap，基于HashMap的key實(shí)現(xiàn)了HashSet：
//HashSet底層復(fù)用了Map的put方法，value統(tǒng)一使用PRESENT對(duì)象
private static final Object PRESENT = new Object();
public boolean add(E e) {
// 返回null說(shuō)明當(dāng)前插入時(shí)并沒(méi)有覆蓋相同元素
return map.put(e, PRESENT)==null;
}- LinkedHashSet:LinkedHashSet即通過(guò)聚合封裝LinkedHashMap實(shí)現(xiàn)的。
- TreeSet:TreeSet底層也是TreeMap，一種基于紅黑樹(shù)實(shí)現(xiàn)的有序樹(shù)O(logN)級(jí)別的黑平衡樹(shù)：
A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
對(duì)應(yīng)的從源碼中我們也可以看出TreeSet底層是對(duì)TreeMap的復(fù)用：
public TreeSet() {
this(new TreeMap<E,Object>());
}HashMap 和 Hashtable 的區(qū)別(重點(diǎn))
針對(duì)該問(wèn)題，筆者建議從以下5個(gè)角度進(jìn)行探討：
(1) 從線程安全角度：HashMap 操作是線程不安全、Hashtable 是線程安全，這一點(diǎn)我們已經(jīng)在上文中源碼進(jìn)行了相應(yīng)的介紹，這里就不多做贅述了。
(2) 從底層數(shù)據(jù)結(jié)構(gòu)角度：HashMap 初始情況是數(shù)組+鏈表，特定情況下會(huì)變數(shù)組+紅黑樹(shù)，Hashtable 則是數(shù)組+鏈表。
(3) 從保存數(shù)值角度：HashMap 允許null鍵或null值，而Hashtable則不允許null的value，這一點(diǎn)我們可以直接查看的Hashtable的put方法：
public synchronized V put(K key, V value) {
// 如果value為空則拋出空指針異常
if (value == null) {
throw new NullPointerException();
}
//......
}(4) 從初始容量角度考慮：HashMap默認(rèn)16，對(duì)此我們可以通過(guò)直接查看源碼的定義印證這一點(diǎn)：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16同時(shí)HashMap進(jìn)行擴(kuò)容時(shí)都是基于當(dāng)前容量*2，這一點(diǎn)我們可以直接通過(guò)resize印證：
final Node<K,V>[] resize() {
//......
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//基于原有數(shù)組容量*2得到新的數(shù)組空間完成map底層數(shù)組擴(kuò)容
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//......
}Hashtable 默認(rèn)的初始大小為 11，之后每次擴(kuò)充，容量變?yōu)樵瓉?lái)的 2n+1：
//初始化容量為11
public Hashtable() {
this(11, 0.75f);
}
//擴(kuò)容方法
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
//擴(kuò)容的容量基于原有空間的2倍+1
int newCapacity = (oldCapacity << 1) + 1;
//......
}(5) 從性能角度考慮：Hashtable 針對(duì)沖突總是通過(guò)拉鏈法解決問(wèn)題，長(zhǎng)此以往可能會(huì)導(dǎo)致節(jié)點(diǎn)查詢(xún)復(fù)雜度退化為O(n)相較于HashMap在達(dá)到空間閾值時(shí)通過(guò)紅黑樹(shù)進(jìn)行bucket優(yōu)化來(lái)說(shuō)性能表現(xiàn)會(huì)遜色很多。
HashMap 和 HashSet有什么區(qū)別
HashSet 聚合了HashMap ，通俗來(lái)說(shuō)就是將HashMap 的key作為自己的值存儲(chǔ)來(lái)使用：
//HashSet底層本質(zhì)是通過(guò)內(nèi)部聚合的map完成元素插入操作
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}HashMap 和 TreeMap 有什么區(qū)別
類(lèi)圖如下，TreeMap 底層是有序樹(shù)，所以對(duì)于需要查找最大值或者最小值等場(chǎng)景，TreeMap 相比HashMap更有優(yōu)勢(shì)。因?yàn)樗^承了NavigableMap接口和SortedMap 接口。
如下源碼所示，我們需要拿最大值或者最小值可以用這種方式或者最大值或者最小值：
Object o = new Object();
//創(chuàng)建并添加元素
TreeMap<Integer, Object> treeMap = new TreeMap<>();
treeMap.put(3213, o);
treeMap.put(434, o);
treeMap.put(432, o);
treeMap.put(2, o);
treeMap.put(432, o);
treeMap.put(31, o);
//順序打印
System.out.println(treeMap);
//拿到第一個(gè)key
System.out.println(treeMap.firstKey());
//拿到最后一個(gè)key
System.out.println(treeMap.lastEntry());輸出結(jié)果：
{2=231, 31=231, 432=231, 434=231, 3213=231}
2
3213=231HashSet實(shí)現(xiàn)去重插入的底層工作機(jī)制了解嘛？
當(dāng)你把對(duì)象加入HashSet時(shí)其底層執(zhí)行步驟為：
- HashSet 會(huì)先計(jì)算對(duì)象的hashcode值定位到bucket。
- 若bucket存在元素，則與其hashcode 值作比較，如果沒(méi)有相符的 hashcode，HashSet 會(huì)認(rèn)為對(duì)象沒(méi)有重復(fù)出現(xiàn)，直接允許插入了。
- 但是如果發(fā)現(xiàn)有相同 hashcode 值的對(duì)象，這時(shí)會(huì)調(diào)用equals()方法來(lái)檢查 hashcode 相等的對(duì)象是否真的相同。
- 如果兩者相同，HashSet就會(huì)將其直接覆蓋返回插入前的值。
對(duì)此我們給出HashSet底層的去重的實(shí)現(xiàn)，本質(zhì)上就算map的putVal方法：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//......
//bucet不存在元素則直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//若存在元素，且hash、key、equals相等則覆蓋元素并返回舊元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
//......
//若存在元素，且hash、key、equals相等則覆蓋元素并返回舊元素
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;
//......
return oldValue;
}
}
//......
return null;
}HashSet、LinkedHashSet 和 TreeSet 使用場(chǎng)景
- HashSet：可在不要求元素有序但唯一的場(chǎng)景。
- LinkedHashSet：可用于要求元素唯一、插入或者訪問(wèn)有序性的場(chǎng)景，或者FIFO的場(chǎng)景。
- TreeSet：要求支持有序性且按照自定義要求進(jìn)行排序的元素不可重復(fù)的場(chǎng)景。
