- HashMap
- ConcurrentHashMap
- TreeMap
- LinkedHashMap
- WeakHashMap
- IdentityHashMap
HashMap
ConcurrentHashMap
TreeMap
非哈希表刨晴，為紅黑樹結(jié)構(gòu)，即平衡二叉排序樹垛玻。時(shí)間復(fù)雜度為 O(logN)
key 需要實(shí)現(xiàn) Comparable 接口
- TreeSet 使用了 TreeMap
// 二叉排序樹遍歷
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); // 值相同則覆蓋并結(jié)束
} while (t != null);
// 新增節(jié)點(diǎn)
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 平衡樹
fixAfterInsertion(e);
LinkedHashMap
繼承自 HashMap 并重寫 HashMap 中的方法割捅，實(shí)現(xiàn)對(duì)鏈表的維護(hù)
- LinkedHashSet 使用了 LinkedHashMap
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
WeakHashMap
Entry 繼承自 WeakReference，通過查詢 ReferenceQueue 移除被回收的 Entry
get帚桩、put亿驾、size 等方法均會(huì)觸發(fā)對(duì) ReferenceQueue 的查詢與移除 Entry
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
// 新建 Entry 時(shí)指定 ReferenceQueue，JVM 回收時(shí)會(huì)將該對(duì)象放入 queue
Entry(Object key, V value,
ReferenceQueue<Object> queue,
int hash, Entry<K,V> next) {
super(key, queue);
this.value = value;
this.hash = hash;
this.next = next;
}
}
IdentityHashMap
判斷key值的相同账嚎，通過 == (即引用相同) 而非 equals
因此對(duì)于值相同但不同引用的 key莫瞬，均會(huì)保存
val map = new IdentityHashMap<Object, String>();
val a = new Object();
val b = new Object();
map.put(a, "a");
map.put(b, "b");
assert map.get(a) == "a";
assert map.get(b) == "b";
val c = a;
map.put(c, "c");
assert map.get(c) == map.get(a);
assert map.get(c) == "c";
