Java1.8 hashmap 源码阅读1
2019-06-23 本文已影响0人
zydmayday
建议先看下文章中提供的源码，然后再看解释可以加深理解。
内部静态变量
DEFAULT_INITIAL_CAPACITY
默认初始化容量
DEFAULT_LOAD_FACTOR
默认负载因子
TREEIFY_THRESHOLD
二叉树阈值
UNTREEIFY_THRESHOLD
取消二叉树阈值
MIN_TREEIFY_CAPACITY
二叉树化所需要的最小容量
内部类，Node<K, V>
好像内部存储的hash没用到。
hashCode
计算hash值，
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
静态方法
static final inti hash(Object key)
计算key的hash值。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
static Class<?> comparableClassFor(Object x)
TODO
在二叉树中使用到
static int compareComparables(Class<?> kc, Object k, Object x)
TODO
也是在二叉树中用到
static final int tableSizeFor(int cap)
传入容量cap，返回比传入的容量cap大的最小二次幂。
变量
table
最终存储数据的地方
entrySet
TODO
一个缓存用的set
size
容量大小当前
modCount
TODO
操作数，貌似是线程安全用的
threshold
resize的阈值
loadFactor
负载因子
公有方法
构造方法
public HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity)
public HashMap()
public HashMap(Map<? extends K, ? extends V> m)
pubMapEntries(Map<? extends K, ? extends V> m, boolean evict)
一次性放入多组键值对，也可以叫做键值对的复制。
- 如果table没有初始化则进行初始化，根据传入的m计算最大容量（根据负载因子）
- 如果table初始化了，则判断是否会大于阈值，大于阈值则resize
- for遍历m，完成数据的复制
注意：putVal函数
public int size()
返回map的容量
public boolean isEmpty()
返回map是否为空
public V get(Object key)
通过调用内部方法getNode来获取数据
final Node<K, V> getNode(int hash, Object key)
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;
}
- 如果table为null或者长度为0，或者计算的index的对应值为null，则返回null（没有匹配）
- 否则检查第一个值，如果keys也相等则说明找到，返回
- 否则检查是不是TreeNode，如果是则调用getTreeNode
- 否则遍历链表后找到值后返回
public boolean containsKey(Object key)
调用内部方法getNode，判断是否包含key
public V put(K key, V value)
调用内部方法putVal来实现
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
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;
}
很重要，用来往table里放东西的方法。
- 检查table，必要时做初始化（resize）
- 计算index，如果不和任何hash冲突，则新建Node
- 否则查看是否是同一个key（hash也相同），如果是则覆写
- 否则发生撞库，判断是否是TreeNode，如果是则调用putTreeval方法
- 否则遍历链表，如果在链表中有相同的hash和key，则覆写
- 否则插入链表链尾，如果插入后超过阈值，则Treeify
- 如果onlyIfAbsent是true的话，则不更新旧值
- 如果size大于阈值，则调用resize
onlyIfAbsent: 只有当不存在时才更新
evict:
还有一些钩子函数
- afterNodeAccess
- afterNodeInsertion
final Node<K, V>[] resize()
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
resize是很重要的一个内部使用的函数，
主要是用来处理数据结构的初始化，以及在增删Node的时候，
通过resize来保持数据结构的合理性。
table为内部保存数据的数据结构。
流程的大概总结：
- 计算当前容量，如果已经大于等于最大容量，则没必要resize，直接返回
- 如果当前容量的两倍小于最大容量，并且大于初始容量，则当前阈值和容量翻倍
- 如果容量为零，但是阈值不为零，则将容量设置为阈值的值
- 否则的话则初始化容量和阈值
- 如果阈值还是零的话，则用当前阈值和负载因子计算新的阈值
到此为止，阈值和容量的事情我们搞定了
下面开始把旧的table中的Node放到新的table中去。
- 对于每一个table中的Node，计算新的index
- 还是老样子，如果是单个节点，则直接放进新table中
- 如果是TreeNode，则调用tree的方法，split
- 否则插入链表，因为resize之后，每个元素都可能出现在不同的位置上，所以判断插入的位置，然后建立两个链表
判断方式：(e.hash & oldCap) == 0
解释：因为resize之后，左移一位，相当于最高位左移一位，因此如果e.hash & oldCap为零的话，
说明e.hash的高位上没有1，因此就算newCap和e.hash并运算结果也不会改变。
用此方法可以判断每个e到底属于哪个链表，
只可能有两种，一种是保持原来的链表，一种是进入新的链表。
final void treeifyBin(Node<K, V>[] tab, int hash)
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);
}
}
链表到树结构的转换
- 如果传入的tab不符合要求，则resize
- 否则，计算index找到对应元素，开始treeify
- 调用内部方法
replacementTreeNode新建一个TreeNode - 创建树头hd，之后对于新的节点，他的prev指向上一轮的旧节点，旧节点的next指向新节点
- 创建红黑树，
treeify，之后细讲
public void putAll(Map<? extends K, ? extends V> m)
调用内部的函数putMapEntries。
public V remove(Object key)
继续封装，调用内部的removeNode方法。
返回被删除的元素
final Node<K, V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean moveable)
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;
}
参数好多。。
先说下参数
- hash，对应的哈希值
- key，对应的key值，这个是唯一的
- value，对应的value
- matchValue，配合value使用的，只删除value也相同的Node
- moveable，用在tree中
具体的逻辑
- 如果符合条件（table不为空，hash对应的位置有数据之类），则正式开始
- 找到要删除的Node，和putVal差不多，单值，红黑树或者链表，找到为止
- 如果找到的node不为空，且value相同（matchValue），则根据node类型删除
- 如果是TreeNode，调用removeTreeNode方法
- 如果是firstNode，则tabl[index] = node.next
- 否则p.next = node.next，经典的链表删除元素的方法
钩子函数：afterNodeRemoval
public void clear()
清空所有的元素，tab[i] = null
public boolean containsValue(Object value)
因为每一个Node都有next属性，
所以对table遍历，再对node遍历即可找到是否包含value的node。
