一、TreeMap
TreeMap封裝了紅黑樹，在代碼裡的展現就是private transient Entry<K,V> root; 也就是一個key，value鍵值對。具體的紅黑樹操作都在裡面，就不細講了。
1.1 put(k,v)
remove(k)也是和下面道理相似，了解就行。
public V put(K key, V value) {
// 獲得根結點
Entry<K,V> t = root;
// 如果根節點為空，那麼建立一個Entry()，指派為根節點
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
// 下面這段代碼目的是找出key應該插在那個父節點之下
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
// 如果使用者自定義了比較器
if (cpr != null) {
// 找到t == null ，那麼此時parent就是想要的父節點。
do {
parent = t;
cmp = cpr.compare(key, t.key);
// 判斷歸屬于左子樹還是右子樹。
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
// 如果已經存在這個key，那麼覆寫value
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
// 通過找出parent， 在此結點之下挂上新的結點， 紅黑樹調整都在Entry内部進行。
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
1.2 一幫以getEntry()方法為基礎的擷取元素的方法，其中包括containsKey()，get()，remove()等
// 根據key，找出對于的紅黑樹結點Entry<K,V>
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
1.3 一幫以getFirstEntry()，getLastEntry()為基礎的擷取頭和尾元素的方法，其中包括：firstKey()，lastKey()；firstEntry()，lastEntry()；pollFirstEntry()，pollLastEntry()；
//得到最左，即得到最小的key
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
final Entry<K,V> getLastEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.right != null)
p = p.right;
return p;
}
1.4 KeySet 和 EntrySet
由于map沒有Iterator，是以周遊需要借助Set
keySet儲存了map中的key作為集合，之後可以調用map.get(key)得到value對象。
public static void main(String[] args) {
TreeMap<Integer, Integer> map = new TreeMap<>();
map.put(1,2);
map.put(2,3);
map.put(4,5);
map.put(-1,-8);
map.put(-4,-9);
Set<Integer> keySet = map.keySet();
Iterator<Integer> it = keySet.iterator();
while (it.hasNext()) {
Integer key = it.next();
System.out.println(map.get(key));
}
}
map.entrySet()直接把紅黑樹的keySet取出來
由于取出來的Set上面已經是儲存在紅黑樹上的K,V，是以就可以直接通路K,V。
public static void main(String[] args) {
TreeMap<Integer, Integer> map = new TreeMap<>();
map.put(1,2);
map.put(2,3);
map.put(4,5);
map.put(-1,-8);
map.put(-4,-9);
Set<Map.Entry<Integer, Integer>> keySet = map.entrySet();
Iterator<Map.Entry<Integer, Integer>> it = keySet.iterator();
while (it.hasNext()) {
Map.Entry<Integer,Integer> entry = it.next();
System.out.println(entry.getValue());
}
}
兩種方法總結，keySet得到key後，還需要在到紅黑樹中跑一次二分，最終得到V； entrySet直接得到紅黑樹的keySet，那麼就能直接獲得值。是以entrySet的方法速度更快。
二、HashMap
2.1 hash解決沖突的方法
1）開發位址法
m是位址長度
di是增量，對di的取法有三種
線性探測再散列：di = 1 , 2 , 3 , … , m-1
平方/二次探測再散列：di = 1^2 , -1^2 , 2^2 , -2^2 , 3^2 , -3^2 , … , k^2 , -k^2
随機探測再散列 di 是一組僞随機數列
例如，已知哈希表長度m=11，哈希函數為：H（key）= key % 11，則H（47）=3，H（26）=4，H（60）=5，假設下一個關鍵字為69，則H（69）=3，與47沖突。如果用線性探測再散列處理沖突，下一個哈希位址為H1=（3 + 1）% 11 = 4，仍然沖突，再找下一個哈希位址為H2=（3 + 2）% 11 = 5，還是沖突，繼續找下一個哈希位址為H3=（3 + 3）% 11 = 6，此時不再沖突，将69填入5号單元，參圖8.26 (a)。如果用二次探測再散列處理沖突，下一個哈希位址為H1=（3 + 12）% 11 = 4，仍然沖突，再找下一個哈希位址為H2=（3 - 12）% 11 = 2，此時不再沖突，将69填入2号單元，參圖8.26 (b)。如果用僞随機探測再散列處理沖突，且僞随機數序列為：2，5，9，………，則下一個哈希位址為H1=（3 + 2）% 11 = 5，仍然沖突，再找下一個哈希位址為H2=（3 + 5）% 11 = 8，此時不再沖突，将69填入8号單元。
2）拉鍊法
每個桶維護一個連結清單
3）再哈希法
構造多個不同的哈希函數，當哈希位址Hi=RH1（key）發生沖突時，再計算Hi=RH2（key）……，直到沖突不再産生。這種方法不易産生聚集，但增加了計算時間。
4)建立公共溢出區
這種方法的基本思想是：将哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表
2.2 hashmap的源碼分析
cvte面試的時候被問到了hashmap的put(k,v)實作，可見hashmap的重要性
資料域
public class More ...HashMap extends AbstractMap
implements Map, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
// 預設的初始容量（容量為HashMap中槽的數目）是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量（必須是2的幂且小于2的30次方，傳入容量過大将被這個值替換）
static final int MAXIMUM_CAPACITY = 1 << 30;
// 預設加載因子，用于生成桶的大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 某個連結清單長度大于8，有可能轉換成紅黑樹
static final int TREEIFY_THRESHOLD = 8;
// 删除沖突節點後，hash相同的節點數目小于這個數，紅黑樹就恢複成連結清單
static final int UNTREEIFY_THRESHOLD = 6;
// 擴容的臨界值
static final int MIN_TREEIFY_CAPACITY = 64;
// 存儲元素的數組
transient Node[] table;
HashMap的key可以是null
table[0]存放了null的鍵值對。
HashMap中的結點Node
//繼承了Map.Entry<K,V> 每個結點上儲存 K,V對
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
// 重寫了hashcoed的計算方法
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 比較兩個結點是否相同
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
紅黑樹
封裝了紅黑樹，一大段代碼都是紅黑樹的操作，例如插入，删除，傳回頭節點，還有保持平衡性的調整。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
// 傳回根節點
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
容量大小capacity 和 加載因子 loadFactor
如果桶的數量 >= 容量（預設為16） * 加載因子(預設0.75) ， 那麼就進行擴容。
為什麼hashMap的實際容器大小是2^n
傳入capacity之後，實際的桶大小是 大于capactity的最近的2^n的數。
hash值的計算是這樣的 ： 調用了(length-1) & hash ，是以必須要保證leng = 2^n
對于length = 16, 對應二進制”1 0000”, length-1=”0 1111”
假設此時h = 17 .
(1) 使用”h % length”, 也就是”17 % 16”, 結果是1 .
(2) 使用”h & (length - 1)”, 也就是 “1 0001 & 0 1111”, 結果也是1 .
我們會發現, 因為”0 1111”低位都是”1”, 進行”&”操作, 就能成功保留”1 0001”對應的低位, 将高位的都丢棄, 低位是多少, 最後結果就是多少 .
剛好低位的範圍是”0~15”, 剛好是長度為length=16的所有索引 .
HashMap的四個構造函數
// 指定“容量大小”和"加載因子"
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(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 傳入子map，會根據子map的大小，目前容器進行調整大小， 最後指派到目前map上
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//傳入key的hash值，value，false，true
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab:哈希桶，是一個頭節點數組 ， n: 桶的大小 , p: key的哈希值，對于桶的位置i，該位置桶的頭節點
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) //如果哈希桶是空的
n = (tab = resize()).length; // 調用resize()，對哈希桶進行擴容
if ((p = tab[i = (n - 1) & hash]) == null) //如果 key的hash值，在桶中的位置是頭一次出現
tab[i] = newNode(hash, key, value, null); // 生成一個新的結點
else {
// 這類情況就需要順着桶的頭節點，一路摸下去，找到連結清單上存在的結點。
Node<K,V> e; K k;
// 結點存在
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) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
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
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
get方法
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
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) {
// 在樹中get
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
// 在連結清單中get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
rehash
rehash主要是在擴容的時候執行。 擴容的時候，newCap = oldCap << 1 ， 也就是*2 。
rehash做了哪些事呢？
第一步：擴容，<<1位
第二步：取出所有就的Node<K,V>[]oleTable ， 對于每個桶上面的每個結點，都需要挂到新的桶上，它根據新的容量進行下标計算，再把結點挂上去。
多線程執行rehash導緻的死鎖問題
假設桶1後面挂着的點是這樣的。
1）table[1] -> p1 -> p2;
2）線程1對table[1]進行重新挂點時，被中斷,那麼此時線程1的e和next分别如下
table[1] -> p1(e) -> p2(next);
do{
Entry<K,V> next = e.next;// <--假設線程一執行到這裡就被排程挂起了
inti = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}while (e != null);
3)此時線程2完成了rehash，把桶1改變了結構
由于用了頭插法，是以線程2執行完之後變成了這樣。
table[1] -> p2(next) -> p1(e)
4）這個時候線程1恢複執行，可以發現，e 和 next 構成了循環連結清單，陷入了死循環。
三、ConcurrentHashMap
HashMap線程安全有以下幾種選擇：
1）HashTable：内部調用synchronizaed 方法，對類進行上鎖
2）Collections.synchronizedMap(map) ：内部持有一個mutex，每個方法都對mutex進行上鎖，是以效果和1）差不多。
3）ConcurrentHashMap：分段鎖技術
分段鎖
早期
預設維護了16把鎖，把哈希表通過某種規則劃分成16組。多個線程通路同一組，那麼他們是互斥的。但是如果多個線程通路不同組，那麼他們就可以并發。
java8之後
利用CAS算法和synchronized對連結清單的頭節點上鎖實作同步
插入
ConcurrntHashMap學習這方面有助于了解并發程式設計
- size()方法和mappingCount()方法的異同，兩者計算是否準确？
- 多線程環境下如何進行擴容？
四、LinkedHashMap
父類就是HashMap
public LinkedHashMap() {
// 調用HashMap的構造方法，其實就是初始化Entry[] table
super();
// 這裡是指是否基于通路排序，預設為false
accessOrder = false;
}