java是什么造就了Hashmap。putIfAbsent比Containeskey快,然后是put?
问题
HashMap方法putIfAbsent如何能够以比调用containsKey(x)Previor更快的方式有条件地执行put
例如,如果你没有使用putIfAbsent,你可以使用:
if(!map.containsKey(x)){
map.put(x,someValue);
}
我以前认为putIfAbsent是调用containsKey,然后在HashMap上放置put的方便方法。但在运行基准测试后,putIfAbsent的速度明显快于使用containsKey和Put。我看了看java。util源代码,尝试看看这是如何实现的,但这对我来说有点太神秘了。有人知道putIfAbsent在时间复杂度更高的情况下是如何工作的吗?这是我基于运行一些代码测试的假设,在这些测试中,当使用putIfAbsent时,我的代码运行速度提高了50%。它似乎可以避免调用get(),但如何避免呢
示例
if(!map.containsKey(x)){
map.put(x,someValue);
}
VS
map.putIfAbsent(x,somevalue)
Hashmap的Java源代码。putIfAbsent
@Override
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, 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;
}
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;
}
# 1 楼答案
看看埃兰的答案。。。我想更简洁地回答这个问题
put
和putIfAbsent
都使用相同的助手方法putVal
。但是使用put
的客户机无法利用它的许多参数,这些参数允许put if present行为。公共方法putIfAbsent
公开了这一点。因此,使用putIfAbsent
与将要与containsKey结合使用的put
具有相同的潜在时间复杂性。使用containsKey
就变成了浪费其核心是,put和
putIfAbsent
都在使用私有函数putVal
# 2 楼答案
putIfAbsent
的HashMap
实现只搜索一次键,如果没有找到键,它会将值放入相关的bin(已经找到了)。这就是putVal
所做的另一方面,使用
map.containsKey(x)
后跟map.put(x,someValue)
在Map
中执行两次密钥查找,这需要更多时间请注意}和
put
也调用putVal
(put
调用putVal(hash(key), key, value, false, true)
,而putIfAbsent
调用putVal(hash(key), key, value, true, true)
),因此putIfAbsent
与只调用put
具有相同的性能,这比同时调用{put
要快