Java Map 和 Set 全面解析
在Java編程中，Map 和 Set 是兩個(gè)非常重要的集合接口，它們在數(shù)據(jù)存儲和操作方面發(fā)揮著重要作用。無論是日常開發(fā)還是技術(shù)面試，對這兩個(gè)接口的理解和應(yīng)用都是不可或缺的。
詳解Map集合
Map接口定義概覽
Map即映射集，是線上就是將對應(yīng)的key映射到對應(yīng)value上，由此構(gòu)成一個(gè)數(shù)學(xué)上的映射的概念，該適合存儲不可重復(fù)鍵值對類型的元素，key不可重復(fù)，value可重復(fù)，我們可以通過key找到對應(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ù)組+鏈表/紅黑樹組成，通過key算得hash尋址從而定位到Map底層數(shù)組的索引位置。在進(jìn)行put操作時(shí)，若沖突時(shí)使用拉鏈法解決沖突，如下面這段代碼所示，當(dāng)相同索引位置存儲的是鏈表時(shí)，它會進(jìn)行for循環(huán)定位到相同hash值的索引位置的尾節(jié)點(diǎn)進(jìn)行追加。當(dāng)鏈表長度大于8且數(shù)組長度大于64的情況下，鏈表會進(jìn)行樹化變成紅黑樹，減少元素搜索時(shí)間。
注意 : 若長度小于64鏈表長度大于8只會HashMap底層數(shù)組的擴(kuò)容操作，對此我們給出Map進(jìn)行put操作時(shí)將元素添加到鏈表結(jié)尾的代碼段，可以看到當(dāng)鏈表元素大于等于8時(shí)會嘗試調(diào)用treeifyBin進(jìn)行樹化操作：
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)行樹化操作
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//.......
}
//......
}對應(yīng)我們步入treeifyBin即可直接印證我們的邏輯，當(dāng)?shù)讓訑?shù)組空間小于64時(shí)只會進(jìn)行數(shù)組擴(kuò)容，而非針對當(dāng)前bucket的樹化操作：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//若當(dāng)前數(shù)組空間小于64則直接會進(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)行樹化操作
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í)都會上鎖，可以保證線程安全，底層數(shù)組是 Hashtable 的主體，在插入發(fā)生沖突時(shí)，會通過拉鏈法即將節(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í)，通過遍歷對應(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í)，會將節(jié)點(diǎn)追加到同索引位置的節(jié)點(diǎn)后面
addEntry(hash, key, value, index);
return null;詳解Set集合
Set基本核心概念
Set集合不可包重復(fù)的元素，即如果兩個(gè)元素在equals方法下判定為相等就只能存儲其中一個(gè)，這意味著該集合也最多包含一個(gè)null的元素，它常用于一些需要進(jìn)行去重的場景。
//HashSet底層復(fù)用了Map的put方法，value統(tǒng)一使用PRESENT對象
private static final Object PRESENT = new Object();
public boolean add(E e) {
// 返回null說明當(dāng)前插入時(shí)并沒有覆蓋相同元素
return map.put(e, PRESENT)==null;
}Set有兩種我們比較熟悉的實(shí)現(xiàn)：
- HashSet:HashSet要求數(shù)據(jù)唯一，但是存儲是無序的(底層通過Hash算法實(shí)現(xiàn)尋址)，所以基于面向?qū)ο笏枷霃?fù)用原則，Java設(shè)計(jì)者就通過聚合關(guān)系封裝HashMap，基于HashMap的key實(shí)現(xiàn)了HashSet：
//HashSet底層復(fù)用了Map的put方法，value統(tǒng)一使用PRESENT對象
private static final Object PRESENT = new Object();
public boolean add(E e) {
// 返回null說明當(dāng)前插入時(shí)并沒有覆蓋相同元素
return map.put(e, PRESENT)==null;
}- LinkedHashSet:LinkedHashSet即通過聚合封裝LinkedHashMap實(shí)現(xiàn)的。
- TreeSet:TreeSet底層也是TreeMap，一種基于紅黑樹實(shí)現(xiàn)的有序樹O(logN)級別的黑平衡樹：
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.
對應(yīng)的從源碼中我們也可以看出TreeSet底層是對TreeMap的復(fù)用：
public TreeSet() {
this(new TreeMap<E,Object>());
}HashMap 和 Hashtable 的區(qū)別(重點(diǎn))
針對該問題，筆者建議從以下5個(gè)角度進(jìn)行探討：
(1) 從線程安全角度：HashMap 操作是線程不安全、Hashtable 是線程安全，這一點(diǎn)我們已經(jīng)在上文中源碼進(jìn)行了相應(yīng)的介紹，這里就不多做贅述了。
(2) 從底層數(shù)據(jù)結(jié)構(gòu)角度：HashMap 初始情況是數(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，對此我們可以通過直接查看源碼的定義印證這一點(diǎn)：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16同時(shí)HashMap進(jìn)行擴(kuò)容時(shí)都是基于當(dāng)前容量*2，這一點(diǎn)我們可以直接通過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)樵瓉淼?nbsp;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 針對沖突總是通過拉鏈法解決問題，長此以往可能會導(dǎo)致節(jié)點(diǎn)查詢復(fù)雜度退化為O(n)相較于HashMap在達(dá)到空間閾值時(shí)通過紅黑樹進(jìn)行bucket優(yōu)化來說性能表現(xiàn)會遜色很多。
HashMap 和 HashSet有什么區(qū)別
HashSet 聚合了HashMap ，通俗來說就是將HashMap 的key作為自己的值存儲來使用：
//HashSet底層本質(zhì)是通過內(nèi)部聚合的map完成元素插入操作
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}HashMap 和 TreeMap 有什么區(qū)別
類圖如下，TreeMap 底層是有序樹，所以對于需要查找最大值或者最小值等場景，TreeMap 相比HashMap更有優(yōu)勢。因?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)你把對象加入HashSet時(shí)其底層執(zhí)行步驟為：
- HashSet 會先計(jì)算對象的hashcode值定位到bucket。
- 若bucket存在元素，則與其hashcode 值作比較，如果沒有相符的 hashcode，HashSet 會認(rèn)為對象沒有重復(fù)出現(xiàn)，直接允許插入了。
- 但是如果發(fā)現(xiàn)有相同 hashcode 值的對象，這時(shí)會調(diào)用equals()方法來檢查 hashcode 相等的對象是否真的相同。
- 如果兩者相同，HashSet就會將其直接覆蓋返回插入前的值。
對此我們給出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 使用場景
- HashSet：可在不要求元素有序但唯一的場景。
- LinkedHashSet：可用于要求元素唯一、插入或者訪問有序性的場景，或者FIFO的場景。
- TreeSet：要求支持有序性且按照自定義要求進(jìn)行排序的元素不可重復(fù)的場景。
