如有转载请注明出处 https://www.jianshu.com/p/f4b5a7025f86

粗略说一说

HashMap主要是由数组+链表数据结构实现的，数组存储链表，而链表中存储了上一个节点地址、下一个节点地址、key和value的值，在jdk1.8中加入了红黑树，当链表的长度超过一定阈值的时候会转换成红黑树。

接下来我们就详细挖一下每一部分都做了什么。

get(Object key)

当我们要获取hashMap中的value时，需要根据key来调用get方法，那我们看一看get方法做了什么操作。

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

在return中我们可以看到通过getNode方法获取链表中的某一个node节点，如果node不为空则返回node中的value，如果node为null则返回null。
在getNode方法中第一个参数是对key的hashCode进行了hash处理，hash是通过散列算法将一些长度不一样的数据转换成长度一样的数据。一般通过加法，位运算，乘法来获取hash。

举个例子：
aa  -> aadb
bbb -> bbbc
c   -> cedc
那我们来看看hash(key)是如何生成的？
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }
Object的hashCode()通过将物理地址进行hash，然后将hash值右移16位让高位的参加运算再进行按照位的异或来生成的，这样能保证生成的数据更加散列。

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

(n - 1) & hash 可以得到hash值在数组中的下标，按位与得到的是0-n-1范围内的值

假设key得到的hash值为2135657,他的二进制是
0000 0000 0010 0000 1001 0110 0110 1001
当前数组的长度是9，那么n-1为8，他的二进制是
0000 0000 0000 0000 0000 0000 0000 1000
进行&运算之后得到的就是8，当前的key对应的hash值就在数组中的8位置

之后的操作就比较简单了，先判断链表中的第一个节点的key是否相同，如果是对象就判断地址是否相同，如果地址不相同在判断里面存的值是否相同，如果链表的第一个节点不匹配，那么就判断是否是红黑二叉树，如果是的话就在树中进行查找，如果不是树结构就接着找链表后面的节点。