首先说一下HashMap存储结构,数组、链表、树这三种数据结构形成了hashMap。

存储结构下图所示,根据key的hash与table长度确定table位置,同一个位置的key以链表形式存储,超过一定限制链表转为树。

数组的具体存取规则是tab[(n-1) & hash],其中tab为node数组,n为数组的长度,hash为key的hash值。

//链表中数据的临界值,如果达到8,就进行resize扩展,如果数组大于64则转换为树.

staticfinalint TREEIFY_THRESHOLD =8;

//如果链表的数据小于6,则从树转换为链表.

staticfinalintUNTREEIFY_THRESHOLD=6;

//如果数组的size大于64,则把链表进行转化为树

staticfinalint MIN_TREEIFY_CAPACITY =64

//根据key匹配Node,如果匹配不到key,则返回defaultValue

@Overridepublic V getOrDefault(Object key, V defaultValue){Node<K,V> e;return(e = getNode(hash(key), key))==null? defaultValue : e.value;}

//根据key匹配Node,如果匹配不到则增加key-value,返回null,如果匹配到Node,如果oldValue不等于null则不进行value覆盖,返回oldValue

@Overridepublic V putIfAbsent(K key, V value){return putVal(hash(key), key, value,true,true);}

//根据key匹配node,如果value也相同则删除

@Override

public boolean remove(Object key, Object value) {

return removeNode(hash(key), key, value, true, true) != null;

}

//根据key匹配node,如果value也相同则使用newValue覆盖返回true,否则返回false

@Override

public boolean replace(K key, V oldValue, V newValue) {

Node e; V v;

if ((e = getNode(hash(key), key)) != null &&

((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {

e.value = newValue;

afterNodeAccess(e);

return true;

}

return false;

}

//根据key做匹配Node,(匹配不到则新建然后重排)如果Node有value,则直接返回oldValue,如果没有value则根据Function接口的apply方法获取value,返回value。

//Function接口的apply的入参为key,调用computeIfAbsent时重写Function接口可以根据key进行逻辑处理,apply的返回值即为要存储的value。

@Override

public V computeIfAbsent(K key,

Functionsuper K, ? extends V> mappingFunction) {

if (mappingFunction == null)

throw new NullPointerException();

int hash = hash(key);

Node[] tab; Node first; int n, i;

int binCount = 0;

TreeNode t = null;

Node old = null;

if (size > threshold || (tab = table) == null ||

(n = tab.length) == 0)

n = (tab = resize()).length;

if ((first = tab[i = (n – 1) & hash]) != null) {

//如果已经转为树,按照树的规则进行处理

if (first instanceof TreeNode)

old = (t = (TreeNode)first).getTreeNode(hash, key);

else {

Node e = first; K k;

//查找整个链表,找到对应的key

do {

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k)))) {

old = e;

break;

}

++binCount;

} while ((e = e.next) != null);

}

V oldValue;

if (old != null && (oldValue = old.value) != null) {

afterNodeAccess(old);

return oldValue;

}

}

//根据重写逻辑计算返回value

V v = mappingFunction.apply(key);

if (v == null) {

return null;

} else if (old != null) {

old.value = v;

afterNodeAccess(old);

return v;

}

else if (t != null)

t.putTreeVal(this, tab, hash, key, v);

else {

//如果匹配不到则table加入数据

tab[i] = newNode(hash, key, v, first);

if (binCount >= TREEIFY_THRESHOLD – 1)

treeifyBin(tab, hash);

}

++modCount;

++size;

afterNodeInsertion(true);

return v;

}

//V computeIfPresent(K key,BiFunction remappingFunction):根据key做匹配,如果匹配不上则返回null,匹配上根据BiFunction的apply方法获取value,返回value。BiFunction接口的apply的入参为key、oldValue,调用computeIfPresent时重写Function接口可以根据key和oldValue进行逻辑处理,apply的返回值如果为null则删除该节点,否则即为要存储的value。

public V computeIfPresent(K key,

BiFunctionsuper K, ? super V, ? extends V> remappingFunction) {

if (remappingFunction == null)

throw new NullPointerException();

Node e; V oldValue;

int hash = hash(key);

if ((e = getNode(hash, key)) != null &&

(oldValue = e.value) != null) {

//使用key和原value作为入参

V v = remappingFunction.apply(key, oldValue);

if (v != null) {

e.value = v;

afterNodeAccess(e);

return v;

}

else

removeNode(hash, key, null, false, true);

}

return null;

}

//V compute(K key,BiFunction remappingFunction):根据key做匹配,根据BiFunction的apply返回做存储的value。匹配到Node做value替换,匹配不到新增node。apply的返回值如果为null则删除该节点,否则即为要存储的value。

@Override

public V compute(K key,

BiFunctionsuper K, ? super V, ? extends V> remappingFunction) {

if (remappingFunction == null)

throw new NullPointerException();

int hash = hash(key);

Node[] tab; Node first; int n, i;

int binCount = 0;

TreeNode t = null;

Node old = null;

if (size > threshold || (tab = table) == null ||

(n = tab.length) == 0)

n = (tab = resize()).length;

if ((first = tab[i = (n – 1) & hash]) != null) {

if (first instanceof TreeNode)

old = (t = (TreeNode)first).getTreeNode(hash, key);

else {

Node e = first; K k;

do {

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k)))) {

old = e;

break;

}

++binCount;

} while ((e = e.next) != null);

}

}

V oldValue = (old == null) ? null : old.value;

//使用key和原value作为入参

V v = remappingFunction.apply(key, oldValue);

if (old != null) {

if (v != null) {

old.value = v;

afterNodeAccess(old);

}

else

removeNode(hash, key, null, false, true);

}

else if (v != null) {

if (t != null)

t.putTreeVal(this, tab, hash, key, v);

else {

tab[i] = newNode(hash, key, v, first);

if (binCount >= TREEIFY_THRESHOLD – 1)

treeifyBin(tab, hash);

}

++modCount;

++size;

afterNodeInsertion(true);

}

return v;

}

// V merge(K key, V value,BiFunction remappingFunction):功能大部分与compute相同,不同之处在于BiFunction中apply的参数,入参为oldValue、value,调用merge时根据两个value进行逻辑处理并返回value。

@Override

public V merge(K key, V value,

BiFunctionsuper V, ? super V, ? extends V> remappingFunction) {

if (value == null)

throw new NullPointerException();

if (remappingFunction == null)

throw new NullPointerException();

int hash = hash(key);

Node[] tab; Node first; int n, i;

int binCount = 0;

TreeNode t = null;

Node old = null;

if (size > threshold || (tab = table) == null ||

(n = tab.length) == 0)

n = (tab = resize()).length;

if ((first = tab[i = (n – 1) & hash]) != null) {

if (first instanceof TreeNode)

old = (t = (TreeNode)first).getTreeNode(hash, key);

else {

Node e = first; K k;

do {

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k)))) {

old = e;

break;

}

++binCount;

} while ((e = e.next) != null);

}

}

if (old != null) {

V v;

if (old.value != null)

//使用新老value作为入参

v = remappingFunction.apply(old.value, value);

else

v = value;

if (v != null) {

old.value = v;

afterNodeAccess(old);

}

else

removeNode(hash, key, null, false, true);

return v;

}

if (value != null) {

if (t != null)

t.putTreeVal(this, tab, hash, key, value);

else {

tab[i] = newNode(hash, key, value, first);

if (binCount >= TREEIFY_THRESHOLD – 1)

treeifyBin(tab, hash);

}

++modCount;

++size;

afterNodeInsertion(true);

}

return value;

}

// void forEach(BiConsumer action):调用此方法时实现BiConsumer接口重写void accept(Object o, Object o2)方法,其中o为key,o2为value,可根据自己的实现对map中所有数据进行处理。

@Override

public void forEach(BiConsumersuper K, ? super V> action) {

Node[] tab;

if (action == null)

throw new NullPointerException();

if (size > 0 && (tab = table) != null) {

int mc = modCount;

for (int i = 0; i < tab.length; ++i) {

for (Node e = tab[i]; e != null; e = e.next)

action.accept(e.key, e.value);

}

if (modCount != mc)

throw new ConcurrentModificationException();

}

}

// void replaceAll(BiFunction function):调用此方法时重写BiFunction的Object apply(Object o, Object o2)方法,其中o为key,o2为value,根据重写方法逻辑进行重新赋值。

@Override

public void replaceAll(BiFunctionsuper K, ? super V, ? extends V> function) {

Node[] tab;

if (function == null)

throw new NullPointerException();

if (size > 0 && (tab = table) != null) {

int mc = modCount;

for (int i = 0; i < tab.length; ++i) {

for (Node e = tab[i]; e != null; e = e.next) {

e.value = function.apply(e.key, e.value);

}

}

if (modCount != mc)

throw new ConcurrentModificationException();

}

}

computeIfAbsent、computeIfPresent、compute对比

computeIfAbsent:如果key已存在,返回oldVlaue;不存在创建,返回新创建value

computeIfPresent:如果key不存在,返回null;如果已存在,value为null则删除此节点,不为null替换节点value并返回此value。

compute:如果key不存在,新建key进行存储;如果key存在,value为null则删除此节点,不为null替换节点value并返回此value。

发表回复

您的电子邮箱地址不会被公开。