HashMap(1.8)底层原理之get(key)分析

HashMap(1.8)底层原理之get(key)分析

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

我们都知道hashMap底层数据结构为:数组+单项链表+红黑树;

获取一个value值首先要获取当前key值所在的节点,得到该节点 e.value属性值即为目标值;

第一步:对key值进行hash运算,得到节点位置;(如何hash运算:获取key值得hashcode将其称为h值,然后对该h值>>>16无符号右移16将其称为h16,然后对这两个值进行异或运算 h^h16)。hash运算要经过三个步骤才能算出节点位置。

第二部:getNode(h,key); 有了结点位置,我们就可以进行下一步的运算;h即为数组的下标;

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

这个方法中有5个局部变量:

Node<K,V>[] tab;//hashmap中数组

Node<K,V> first, e;//目标节点的第一个元素、目标节点元素

int n; //数组长度

K k;//目标节点的key值

为什么要传两个值(int hash, Object key):存在hash冲突!

第一个if判断:满足三个条件 ->数组不为空 && 数组长度>0 && 目标节点存在 ;

                      如果满足这三个条件,可以得到一个数组元素,目标值即存在该元素之中;

第二个if判断:满足两个调节-> 第一个元素节点的下标与目标节点的下标一致&&key值一致;

                    这种情况存在当前数组元素只有一个节点,直接返回该数组元素值;

第三个if判断:第二if不满足时,表示该值存在一个链表中;

                        首先判断当前结点是否为红黑树,如果是红黑树,则进行红黑树取值操作;

                        如果是链表,便利链表获取目标值;

总结:hashmap底层是数组+链表+红黑树;获取value值总而言之就是通过key值hash运算、无符号位移运算以及异或运算获得数组下表位置;

            得到数组元素目标数据之后,即可得到一个链表,判断该链表第一个节点值是否为所求值,如果是直接返回,不是的话判断是否为红黑树,如果是红黑树,

            红黑树算法遍历求值;非红黑树,则do...while遍历链表; 

    

ps:语言表达不是很准确,望指正;