【大厂面试题系列】：JDK7、8 HashMap的get()、p

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;
}