HashMap
HashMap是數(shù)組加上單鏈表的形式
# 構(gòu)造函數(shù)
public HashMap() {
// 4, 0.75f
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
# put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 哈希算法, 不討論
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
// 初始化數(shù)組容器, 長(zhǎng)度為4
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
// 計(jì)算哈希值
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
// int i = 哈希值 & (數(shù)組長(zhǎng)度-1); 是為了不超出下標(biāo)
int i = indexFor(hash, table.length);
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 匹配 對(duì)應(yīng)的key, 和哈希值
// 如果匹配到覆蓋原值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 沒(méi)有匹配到, 鏈表中添加新的節(jié)點(diǎn)
addEntry(hash, key, value, i);
return null;
}
// key 為 NULL 時(shí)的方法
private V putForNullKey(V value) {
// e 賦值為 tabel[0], 可見(jiàn)將 key為 null, 分配到了數(shù)組中的0下標(biāo)
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
// e 不為空, 并且key == null時(shí), 覆蓋舊value
if (e.key == null) {
V oldValue = e.value;
e.value = value;
// 給子類重寫(xiě), 空方法
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// int hash, K key, V value, int bucketIndex
addEntry(0, null, value, 0);
return null;
}
// 給鏈表添加元素
void addEntry(int hash, K key, V value, int bucketIndex) {
// 當(dāng)存儲(chǔ)的元素 >= 閾值(默認(rèn)為3) 并且數(shù)組當(dāng)前下標(biāo)中的元素不等于空
if ((size >= threshold) && (null != table[bucketIndex])) {
// 以原數(shù)組長(zhǎng)度的2倍擴(kuò)容
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
// bucketIndex為要放進(jìn)容器的下標(biāo)
// 創(chuàng)建 Entry插入到 table數(shù)組 bucketIndex下標(biāo)鏈表中的頭部
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> e = table[bucketIndex];
// 哈希值, key, value, next指針
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}
// 擴(kuò)容數(shù)組
void resize(int newCapacity) {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
// 將原有數(shù)據(jù)遷移到擴(kuò)容后的數(shù)組當(dāng)中
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
// 外不循環(huán), 遍歷遠(yuǎn)table元素
for (HashMapEntry<K,V> e : table) {
// 內(nèi)部循環(huán), 遍歷table元素中的鏈表
while(null != e) {
HashMapEntry<K,V> next = e.next;
// 根據(jù)新的數(shù)組長(zhǎng)度重新計(jì)算下標(biāo)
int i = indexFor(e.hash, newCapacity);
// 相當(dāng)于將 Node e插入到當(dāng)前下標(biāo)鏈表中的頭部
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
# get
public V get(Object key) {
if (key == null)
return getForNullKey();
// 根據(jù)key 獲取對(duì)應(yīng)的 Entry
Map.Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
// 獲取 key 為 NULL的 value
private V getForNullKey() {
if (size == 0) {
return null;
}
// 在 下標(biāo)為0的 鏈表中循環(huán)查找
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
final Map.Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
// 遍歷鏈表
for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
// 匹配 哈希值和 key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
# remove
public V remove(Object key) {
Map.Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.getValue());
}
final Map.Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
HashMapEntry<K,V> prev = table[i];
HashMapEntry<K,V> e = prev;
while (e != null) {
HashMapEntry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
// prev == e 表明第一次循環(huán)就中標(biāo)
if (prev == e)
table[i] = next;
else
// 前一個(gè)Node 連接 nextNode
prev.next = next;
// 子類重寫(xiě), 空方法
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
# entrySet()
// entrySet() 和 keySet() 都是一個(gè)意思
private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
// EntrySet
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
HashMapEntry<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
// 外部循環(huán)遍歷 tab 數(shù)組
for (int i = 0; i < tab.length; ++i) {
// 內(nèi)部循環(huán) 遍歷鏈表
// 規(guī)則是從 下標(biāo) 0開(kāi)始遍歷鏈表, 鏈表結(jié)束后 在遍歷下標(biāo)1 ...
for (HashMapEntry<K,V> e = tab[i]; e != null; e = e.next) {
action.accept(e);
// 等號(hào)不成立, 說(shuō)明出現(xiàn)了并發(fā)錯(cuò)誤
if (modCount != mc) {
throw new ConcurrentModificationException();
}
}
}
}
}
// HashIterator
// KeySet 調(diào)用 iterator 會(huì)調(diào)用該方法獲取Entry, 在調(diào)用getKey
// 規(guī)則也和 foreach() 一樣也是從下標(biāo)0開(kāi)始 遍歷
final Map.Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
HashMapEntry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
HashMapEntry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
LinkedHashMap
LinkedHashMap繼承于HashMap, 利用雙向循環(huán)鏈表保證順序
# init
void init() {
// 初始化header, before和after都指向自己
header = new LinkedHashMapEntry<>(-1, null, null, null);
header.before = header.after = header;
}
# put
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> old = table[bucketIndex];
LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old);
table[bucketIndex] = e;
// 到上面和 HashMap一樣, 插入到當(dāng)前下標(biāo)鏈表的頭部
e.addBefore(header);
size++;
}
// 該方法傳入 header
// 如果說(shuō)雙向循環(huán)鏈表中 header為頭部, 那么這里就是插入到隊(duì)尾
private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
// 新元素 after 指向 header
after = existingEntry;
// 新元素 before 指向隊(duì)尾, 也有可能是header
before = existingEntry.before;
// 原隊(duì)尾元素 after 指向新元素
before.after = this;
// header.before 指向新元素
after.before = this;
}
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
// 因?yàn)槊總€(gè)元素之前都有鏈表關(guān)系, 所以這里沒(méi)有必要雙重循環(huán), 數(shù)組和鏈表
// 元素 e 從header.after開(kāi)始
for (LinkedHashMapEntry<K,V> e = header.after; e != header; e = e.after) {
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];
newTable[index] = e;
}
}
# remove()
void recordRemoval(HashMap<K,V> m) {
remove();
}
private void remove() {
before.after = after;
after.before = before;
}
# foreach()
public void forEach(BiConsumer<? super K, ? super V> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
// header.after 開(kāi)始直到 header為止, header不參與
for (LinkedHashMapEntry<K,V> e = header.after; modCount == mc && e != header; e = e.after)
action.accept(e.key, e.value);
if (modCount != mc)
throw new ConcurrentModificationException();
}
