共计 4791 个字符，预计需要花费 12 分钟才能阅读完成。
HashMap 是一个数组 + 链表 + 红黑树的构造
字段属性
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
// 序列化和反序列化时，通过该字段进行版本一致性验证
private static final long serialVersionUID = 362498820763181265L;
// 默认 HashMap 汇合初始容量为 16（必须是 2 的倍数）static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 汇合的最大容量，如果通过带参结构指定的最大容量超过此数，默认还是应用此数
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶 (bucket) 上的结点数大于这个值时会转成红黑树(JDK1.8 新增)
static final int TREEIFY_THRESHOLD = 8;
// 当桶 (bucket) 上的节点数小于这个值时会转成链表(JDK1.8 新增)
static final int UNTREEIFY_THRESHOLD = 6;
/**(JDK1.8 新增)
* 当汇合中的容量大于这个值时，表中的桶能力进行树形化，否则桶内元素太多时会扩容，* 而不是树形化 为了防止进行扩容、树形化抉择的抵触，这个值不能小于 4 * TREEIFY_THRESHOLD
*/
static final int MIN_TREEIFY_CAPACITY = 64;
// 保留数据的数组
transient Node<K,V>[] table;
//HashMap 中的动态外部类，用于存储数据
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;}
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;
}
}put
1.HashMap 在初始化的时候没有初始化 table，在第一次插入时须要初始化 table
2. 判断 table[i = (n – 1) & hash]是否为 null，如果为 null 阐明该地位没有值，直接插入就行
3. 如果不为 null，则要判断以后地位是链表还是红黑树，如果是红黑树则走红黑树插入，如果是链表走链表插入
4. 遍历链表，如果 key 值和 hash 值都统一，则间接退出循环
5. 如果曾经到了尾结点，则直接插入，并判断是否达到树化条件，如果长度大于 8 则要转为红黑树
6. 退出循环后判断雷同的 key 是否被笼罩，能笼罩间接笼罩，并返回后果
7. 插入实现后再判断 HashMap 的 size 是否大于 threshold，为真时要扩容
8.HashMap 返回后果，失常状况下是 null
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
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;
}
// 如果找到 key 统一，hash 也统一的
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;
}remove
1. 判断 table 是否为 null 和 tab[index = (n – 1) & hash]是否为 null
2. 判断首节点是否为指标节点，如果 key 值相等且 hash 相等阐明首节点就是要删除的节点，判断 node 是否为 null，而后如果是树节点就移除树节点，如果是链表 p.next = node.next; 将指针指向下一个节点
3. 如果不是首节点，则判断节点类型是否是树形节点，如果是，则获取树节点，并在上面 removeTreeNode 移除树节点
4. 如果是链表，则循环遍历，找到节点，并在上面移除
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;
}
get
1. 通过(n – 1) & hash 获取该 key 对应的数据的下标
2. 判断首节点是否为空, 为空则间接返回空
3. 再判断首节点.key 是否和目标值雷同, 雷同则间接返回(首节点不必辨别链表还是红黑树，反正都是间接返回)
4. 首节点.next 为空, 则间接返回空
5. 首节点是树形节点, 则进入红黑树数的取值流程, 并返回后果
6. 进入链表的取值流程, 并返回后果
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 && // always check first node
((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;
}为什么应用红黑树而不是其余的
红黑树遍历速度相比链表更快，和均衡二叉树统一，然而插入速度更快。
红黑树更多劣势在于插入和删除都能够保障树的构造变动在常数范畴，相比之下 avl 树最坏在删除状况下可能会须要向上旋转调整至树根。红黑树最坏也只需通过常数次旋转（插入最多 2 次旋转达到均衡、删除最多 3 次旋转达到均衡；所以红黑树最多三次旋转达到均衡），再加上至树根的重染色。
正文完
