HashMap
属性
int DEFAULT_INITIAL_CAPACITY = 1 << 4; // table数组默认初始大小
int MAXIMUM_CAPACITY = 1 << 30; // table数组最大容量
int TREEIFY_THRESHOLD = 8; // bin达到8开始树化
int MIN_TREEIFY_CAPACITY = 64; // 树化时table需满足容量，否则说明碰撞过多，resize table
int UNTREEIFY_THRESHOLD = 6; // bin达到6开始去树化
int size; // 键值对数量
int threshold; // resize临界值，size > threshold开始扩容
float DEFAULT_LOAD_FACTOR = 0.75f; // 小于1：减少碰撞，空间换时间
float loadFactor;
Node<K,V>[] table; // Node数组
Set<Map.Entry<K,V>> entrySet; // 实体集合，Node实现Map.Entry<K,V>接口
int modCount; // 用于ConcurrentModificationException
Node
static class Node<K,V> implements Map.Entry<K,V>
final int hash;
final K key;
V value;
Node<K,V> next;
TreeNode
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>
// Node有的这个都有
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;
构造方法
HashMap() // 赋值默认负载因子
HashMap(int initialCapacity) // this(initialCapacity, DEFAULT_LOAD_FACTOR)
HashMap(int initialCapacity, float loadFactor)
this.loadFactor = loadFactor; // 负载因子
this.threshold = tableSizeFor(initialCapacity); // threshold
// cap的ceil 2次幂
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
resize
- 场景
- table为空： putVal
- ++size > threshold：putVal添加之后，其实放前面比较好(ConcurrentHashMap就是放前面)
- putMapEntries：待塞Map的size > threshold
- 树化时：table没有达到MIN_TREEIFY_CAPACITY(64)
- 机制
- table >= MAXIMUM_CAPACITY(2^30)，threshold = Integer.MAX_VALUE，table不变
- table > 0 && DEFAULT_INITIAL_CAPACITY <= table && 2 * table < MAXIMUM_CAPACITY
- table为空 && threshold > 0（构造方法传进初始容量，threshold = ceil 2次幂）
- table = threshold, threshold = table * loadFactor
- table为空 && threshold == 0（无参构造方法）
- table = DEFAULT_INITIAL_CAPACITY
- threshold = DEFAULT_INITIAL_CAPACITY * loadFactor
- 遍历table，处理每一个bin
- 单节点bin：&(oldCap-1) -> &(newCap-1)
- TreeNode：树拆分
- 多节点list，(e.hash & oldCap) == 0 ? lo : hi，lo放回原index，hi放到(原index+oldCap)
树拆分
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
添加
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 防止table过小时hash高位失效
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
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;
}
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
- table是否存在，不存在则resize生成一个table
- 判断table[hash & (n-1)]是否存在
- bin不存在，创建首节点
- bin存在
- 首节点命中
- 首节点p是TreeNode，调用((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)
- 非TreeNode，遍历list；添加后bin达树化容量，进行树化
- 根据++size是否超threshold决定resize
- afterNodeInsertion(evict) - LinkedHashMap
TreeNode添加
- final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v)
- 判断parent是否为空，来决定root是root()还是当前节点
- 比较hash，决定左右方向，dir -1代表左，dir 1代表右
- hash碰撞时
- 比较key，若key相等，则命中
- 利用compareTo进行比较，得到dir值
- 调用find(h, k, kc)
- dir = tieBreakOrder(k, pk);通过默认的hashCode来得到方向
- 找到叶子节点处，新建一个节点，并调用balanceInsertion和moveRootToFront
- 在以上的过程中，实际分两种大的情况，即命中和未命中；若是命中，会返回调用者一个节点，用于value的更新；若未命中，则返回null，那么调用者就不需要更新value，也即新增
树化
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
- final void treeify(Node<K,V>[] tab)
- 第一个作为root
- 其余，先进行方向确定，然后底部插入
- 利用root = balanceInsertion(root, x)进行平衡
- 确定方向过程中，发生hash碰撞，且无法通过compareTo决定时，调用dir = tieBreakOrder(k, pk);
- tieBreakOrder中使用原始hashCode做排名，这个信息在find时并没有用到，查询时在hash碰撞及compareTo失效时，采取递归
- static int tieBreakOrder(Object a, Object b)
- static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x)
- 插入x，x xp xpp xppl xppr分别为x的父亲和爷爷，步骤如下：
- x.red置true
- xp为null，那么x就是root（在treeify调用时感觉不会发生）
- xp非红，或者xpp为null，无需操作，直接返回root
- xp为红左
- 若xppr为红右，那么双红置黑红上移
- 若x为xp的右节点，那么左旋，再右旋
- xp为红右
- 若xppl为红左，那么双红置黑红上移
- 若x为xp的左节点，那么右旋，再左旋
- static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root)
- 如果root不是bin的第一节点，就把root拎出来放到第一个位置，具体操作如同对LinkedList操作一般
- static <K,V> boolean checkInvariants(TreeNode<K,V> t)
- 不是很懂什么意思，被moveRootToFront调用了，其中用了assert，实际部署中应该是无效的
取值
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null || (kc = comparableClassFor(k)) != null) && (dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
// 若是x实现了Comparable，则返回x的Class对象，否则返回null
static Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
if (((t = ts[i]) instanceof ParameterizedType)
&& ((p = (ParameterizedType)t).getRawType() == Comparable.class)
&& (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
// x非空 && x和kc同类型，返回k.compareTo(x)；若是类型不同，就没有compareTo的必要了
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 : ((Comparable)k).compareTo(x));
}
- find
- 根据hash判左右
- hash碰撞key不等，调key的compareTo
- 没有实现Comparable接口，递归右侧
删除
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
// 清空table元素，不删table
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
Set相关
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
Hashtable
public synchronized V get(Object key)
public synchronized boolean contains(Object value)
public synchronized boolean containsKey(Object key)
public synchronized V put(K key, V value)
public synchronized void putAll(Map<? extends K, ? extends V> t)
public synchronized V remove(Object key)
public synchronized void clear()
public synchronized Object clone()
public synchronized String toString()
TreeMap
概述
属性
private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
private transient int size = 0;
private transient int modCount = 0;
private transient EntrySet entrySet;
private transient KeySet<K> navigableKeySet;
private transient NavigableMap<K,V> descendingMap;
构造方法
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
添加
- public void putAll(Map<? extends K, ? extends V> map)
- 若属于SortedMap，调用buildFromSorted(mapSize, map.entrySet().iterator(), null, null);
- 否则调用super.putAll
- public V put(K key, V value)
- 先判断root是否为null，为null直接新建Entry，并返回null（表示未命中）
- 判断comparator是否为空
- comparator不为空，用compare方法去消耗树，直到遇到叶子节点；或者命中，命中时更新value并返回旧的value
- comparator为空，则用Comparable的compareTo（此处会有ClassCastException，不知道为什么没有处理，故意的？？？）去消耗树，直到遇到叶子节点；或者命中，命中时更新value并返回旧的value
- 创建一个节点，并根据cmp值放在左边或者右边
- fixAfterInsertion(e);//e是一个Entry；此处会左右旋修补
- size++ modCount++ 返回null（表示未命中）
取值
final Entry<K,V> getEntry(Object key) {
if (comparator != null)// Offload comparator-based version for sake of performance
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;//这里可能ClassCastException哦
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;
}
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
}
return null;
}
final Entry<K,V> getCeilingEntry(K key)
匹配项不存在时，先找大于该key的最小项，还不存在则返回null
final Entry<K,V> getHigherEntry(K key)
不寻找匹配项，其余同getCeilingEntry
final Entry<K,V> getFloorEntry(K key)
匹配项不存在是，先找小于该key的最大项，还不存在则返回null
final Entry<K,V> getLowerEntry(K key)
不寻找匹配项，其余同getFloorEntry
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
public boolean containsValue(Object value) {
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
if (valEquals(value, e.value))
return true;
return false;
}
删除
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
public void clear() {
modCount++;
size = 0;
root = null;
}
Set相关
public Set<K> keySet() {
return navigableKeySet();
}
public NavigableSet<K> navigableKeySet() {
KeySet<K> nks = navigableKeySet;
return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
}
public NavigableSet<K> descendingKeySet() {
return descendingMap().navigableKeySet();
}
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
