DK7、8对于链表的插入：JDK7采用的是头插法，JDK8采用的是尾插法
JDK7
get()流程
1、先看key是否为null，如果为null的话则调用getForNullKey()方法（之后看，如果数组size为0，则返回bull，如果不为0，则获取数组下标为0的链表进行遍历来获取key为null的键值对，如果存在则返回key为null对应的value值，没有则返回null）
2、如果key不为null，则调用getEntry()方法获取key对应的Entry对象再返回其value值。（具体：先看entry数量(size)是否为0，为0就返回null，不为0就去获取key对应的hash值，再去遍历根据hash值得到的指定下标位置的链表，遍历过程中就是根据每一个节点去比较hash值和调用equals方法比较key，如果有即相同key就返回，遍历结束都没有就返回null）
put()流程
-
先去判断数组是否为空，如果为空就要进行初始化
-
再去看key是否为null，如果key为null，那么调用 putForNullKey() 方法，获取数组下标为0的链表进行遍历，遍历过程中如果存在key为null的entry，那么就会覆盖value并返回之前的value值，如果没有这样的key那么就会创建一个key为null，值为value的键值对然后返回null。
-
如果key不为null，那么计算出对应key的hash值和其对应的索引位置
-
然后获取这个索引所在的链表进行遍历，遍历过程让每一个节点和put进来的进行比较(具体：比较hash值和调用equals()方法比较key)，如果存在则覆盖value并返回之前的value值，遍历结束还没有就添加put进来的key、value键值对。
JDK8
get()流程
-
调用 hash 方法计算hash值（利用key的hashCode进行高16位异或低十六位运算）
-
调用getNode()方法如果数组为null则直接返回null
-
如果数组不为null，则进行位运算形式的取模运算得到索引位置
-
看索引位置上对应的第一个元素是否满足（比较hash值和调用equals方法比较key）
-
满足的话直接返回该节点，不满足的话先看是不是红黑树，是的话就调用红黑树的get方法，不是的话则进行do while循环比较，如果最后一个节点满足的话就返回，如果还不满足就返回null
map的get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
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;
}
put()流程
-
调用 hash 方法计算hash值（利用key的hashCode进行高16位异或低十六位运算）
-
再去看数组是否为空，为空的话就对数组进行初始化
-
利用计算出来的 hash 值计算索引位置（使用位运算进行的取模）
-
看计算出来的索引位置上的元素是否为null
-
如果为null的话就在该位置进行插入（插入之后进行 ++size 看容量是否超过阈值，如果超过的话进行扩容），如果不为null的话则发生了hash冲突
-
然后会就去和链表第一个元素进行比较（比较hash值和调用equals方法比较key），如果为true说明key相同，则使用一个中间值保存key、value最后会有一个非null判断来进行value值覆盖，然后返回旧的value值（map的put方法是有返回值的），如果为false，则看当前链表是否是红黑树，如果是的话则调用红黑树的put方法，如果不是红黑树，则进行链表的遍历比较，如果遍历到了最后一个节点还是没找到我们put进来的key，那就说明没有这个key则可以在链表尾部进行新节点添加（尾插法）。最后还是 ++size 看时候超过阈值，超过就扩容没有就算了，最后返回一个null值。
map的put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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;
}
网友评论