文章目录
-
- Map 接口方法实现
-
- 查询操作
-
- 1. size
- 2. isEmpty
- 3. containsKey
-
- hash()
- getNode
- 4. containsValue
- 5. get
- 修改操作
-
- 1. put
-
- putVal
- resize
- 2. remove
-
- `removeNode`
- 批量操作
-
- 1. putAll
-
- `putMapEntries`
- 2. clear
- 视图(未完成)
- 比较和散列(未完成)
翻译来源 java.util.HashMap JDK1.8
HashMap API 所有翻译,请查看翻译目录。
Map 接口方法实现
查询、修改、批量、视图、比较和散列
查询操作
1. size
2. isEmpty
、
size()
两个方法,与JDK1.7中的方法完全相同,详细内容请看此处。
isEmpty()
3. containsKey
如果该map包含指定键的映射,则返回
true
。
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
JDK1.8 中使用替代了JDK1.7中的
Node
,这两个内部类都实现了
Entry
接口
Map.Entry<K,V>
hash()
计算
key.hashCode()
并使用的异或(
XORs
)将哈希的高位扩展到低位。因为该表使用2次幂掩码,所以仅在当前掩码之上的位上变化的散列集合总是会发生碰撞。(已知的例子包括在小表中保存连续整数的浮点数键集。)因此,我们应用了一个转换,向下传播更高位的影响。位扩展的速度、效用和质量之间存在权衡(a tradeoff between)。由于许多常见的散列集已经合理分布(因此不会从扩展中获益),并且因为我们使用树来处理容器中的大量冲突,所以我们只是以最便宜的方式对一些移位的位进行异或,以减少系统损失,以及合并最高位的影响,否则,由于表的界限,这些位将永远不会用于索引计算。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
getNode
实现
Map.get
和相关方法。
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;
Node<K,V> first, e;
int n;
K k;
// 确定 table 存在,数组长度不为0,
// 并定位槽
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 && // 尝试匹配每个后继条目 Entry
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;// 没有匹配节点,返回null
}
4. containsValue
如果该map将一个或多个键映射到指定值,则返回true。
public boolean containsValue(Object value) {
Node<K,V>[] tab;
V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) { // 遍历数组
// 遍历槽上链表
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true; //只要有一个匹配,就立即返回 true
}
}
}
// 表不存在, 或者size<=0,
// 或者遍历完毕,没有匹配中,
// 则返回 false
return false;
}
与JDK1.7的不同点在于,没有区别对等
value == null
的情况,详细内容请看此处。
另外,JDK1.7 中不用判断
是否存在,因为创建
table
时,至少默认为空表。
HashMap
5. get
方法描述与JDK1.7完全相同,详细内容请看此处。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
与JDK1.7的不同点在于,没有区别对等 key == null
的情况。
修改操作
1. put
将指定的值与该map中的指定键相关联。如果该map先前包含该键的一个映射,则替换旧值。
public V put(K key, V value) {
// key的hash、key键、value值、是否不更改现有值、是否不是创建模式
return putVal(hash(key), key, value, false, true);
}
putVal
实现
Map.put
和相关方法。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
// 确保 table 存在,且数组有长度
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) { // 键的已有映射
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)//替换value
e.value = value;
afterNodeAccess(e);
return oldValue; // 返回上一个值
}
}
// 键不存在
++modCount; // 结构化修改计数
if (++size > threshold) // 是否扩容
resize();
afterNodeInsertion(evict);
return null;// 上一个值不存在,返回null
}
resize
初始化或加倍表的大小。如果为空,则按照字段阈值中保持的初始容量目标进行分配。否则,因为我们正在使用2的幂扩展,所以每个bin中的元素必须要么保持相同的索引,要么在新表中以一个2的幂的偏移移动。
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; // 新阈值 加倍 threshold
}
else if (oldThr > 0) // 初始化表大小,初始容量被置为阈值(构造时,指定了初始容量的情况)
newCap = oldThr;
else { // 初始化表大小,零初始阈值表示使用默认值(构造时,未指定初始容量的情况)
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 { // 有后继元素,维持秩序,尾插法
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 本质是多判断一位。
// 假设, e.hash = ob1010, oldCap = ob1000, newCap = oldCap<<1 = ob10000
// 槽位计算公式: e.hash & (cap-1);
// 原槽位:(0b1010 & 0b111 = ob10) => 2槽
// 是否移动到新槽位:(ob1010 & ob1000 = ob1000) => 移动到高位(2+8)槽
// 新槽位: (ob1010 & ob1111 = ob1010) 决定新槽位
if ((e.hash & oldCap) == 0) {// 高位是0,仍保留在低位槽
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {// 高位不是0,移动到高位槽
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;
}
2. remove
如果该map中存在指定键的映射,删除该映射。
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
removeNode
removeNode
实现
Map.remove
和相关方法。
如果
value
为true,则该参数是要匹配的值,否则,忽略。
matchValue
如果为true,则仅在值相等时删除
matchValue
如果为false,则在删除时不移动其他节点
movable
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;
// table 存在,数组长度不为0,且相应的槽上有值(译者按)
// 否则,直接返回 null。
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {// p 表示前一个节点
Node<K,V> node = null, // node 是匹配成功的节点
e; // 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; // key-value对的数量
afterNodeRemoval(node);
return node; //返回成功删除的节点
}
}
return null;
}
批量操作
1. putAll
复制指定map中的所有映射,到该map。这些映射将替换该map拥有的指定map中的当前任何键的任何映射。
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
putMapEntries
putMapEntries
实现
Map.putAll
和Map构造函数。
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();// 要插入条目数
// 确保指定的map中有值。
if (s > 0) {
if (table == null) { // 预先调整大小
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold) // 提前扩容,减少后期扩容时移动元素的可能性
resize();
// 逐条插入
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
2. clear
从该map中删除所有映射。此调用返回后,该map将为空。
public void clear() {
Node<K,V>[] tab;
modCount++;// 结构化修改的次数
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)// 每个槽位置 null
tab[i] = null;
}
}
注意:只是删除映射,没有缩表。
JDK1.7中,使用
置null,详细内容请看此处。
Arrays.fill(table, null);