HashMap源码解析

之前面试的时候发现很多的公司对于hashMap的源码这一块问的比较多，所以自己在看HashMap源码的时候就整理了一下如果能够帮到你们理解那就很开心了

HashMap的底层数据结构

image.png
这里我们可以看到当我们调用HashMap的put方法的时候实际上是调用的putVal方法，在这个方法中我们看到有一个数组 Node<K,V>[] tab，还有一个Node<K,V> p，看第一行的if判断我们看到这里使用了一个HashMap的类对象，table，而这个table是什么呢？我们继续看
image.png
然后我们看到这个table也是一个node的集合
image.png
而这个node呢实际上是一个链表，所以我们长期说的HashMap的底层就是链表加上数组的结构
理论上这样回答是没有问题的，我们可以对这个问题进行更深入的去了解一下
image.png

ps：关于这个put方法等一下来解析

这里先说截图的意思，这里的意思是当此时的这个节点如果在数组中有相同的hash的值的时候，并且这个节点的key对应的key值在这个队列中对应的链表里没有相同的对象而且此时数组对应的不是TreeNode结构的时候遍历这个数组对应得链表结构
当链表的长度大于等于TREEIFY_THRESHOLD（因为此处的binCount是从0开始的，所以其实也就是链表长度等于TREEIFY_THRESHOLD）

image.png

所以也就是当数组对应的链表大于等于8的时候他就调用treeifyBin(tab, hash)方法
所以我们再看看这个方法

image.png
image.png
这里的操作是将数组中的hashn值对应的链表替换为红黑树，并将原来列表中的值赋值给红黑树
总结，一般来是链表加数组的内存模型，当其中某一个数组对应的链表长度等于8的时候此时这个数组对应的就不是链表结而是红黑树结构了，当使用remove方法将某一个数组对应的树结构删除少于等于6个元素的时候又会变成连边结构

ps：这里对应树结构变成链表结构在后续的remove讲解

HashMap的put方法是怎么实现的

我们先看源码代码：

image.png

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;   //这里是定义了一个node的数组，一个node和两个int的数
        if ((tab = table) == null || (n = tab.length) == 0)//这里是将当前的map的table赋值给tab，如果当前map的table不存在或者
            n = (tab = resize()).length;  //长度为0就初始化table并且把初始化的table的长度赋值给int 类型的n
        if ((p = tab[i = (n - 1) & hash]) == null) //这里是通过hash值的寻找数组中的槽位（此处的(n-1)&hash是为了减少hash碰撞）
            tab[i] = newNode(hash, key, value, null);//如果找到数组中的槽位并且为空就把新的kv结构的节点放到链表中
        else {    //以下则是表示key对应的hash在数组中的槽位有值
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p; //如果当前插入的元素的key值和原数组中对应的key值相同就替换掉
            else if (p instanceof TreeNode)//如果key值不同并且当前的数组对应的是一个红黑树
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//往当前节点的红黑树插入值
            else {
                for (int binCount = 0; ; ++binCount) { //如果不满足之前的两个结果那就遍历当前的链表
                    if ((e = p.next) == null) {//如果下一个元素为空就把传入的kv转化成node放入下一个节点
                        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; //如果遍历链表找到相同的key值则替换掉
                }
            }
            if (e != null) { // existing mapping for key  //此处如果之前有值赋值给e就将插入的这个值的kv转化成node放入map中
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value; //替换原来的值
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

总结：

1.计算关于key的hashcode值（与Key.hashCode的高16位做异或运算）

2.如果散列表为空时，调用resize()初始化散列表

3.如果没有发生碰撞，直接添加元素到散列表中去

4.如果发生了碰撞(hashCode值相同)，进行三种判断

4.1:若key地址相同或者equals后内容相同，则替换旧值

4.2:如果是红黑树结构，就调用树的插入方法

4.3：链表结构，循环遍历直到链表中某个节点为空，尾插法进行插入，插入之后判断链表个数是否到达变成红黑树的阙值8；也可以遍历到有节点与插入元素的哈希值和内容相同，进行覆盖。

5.如果桶满了大于阀值，则resize进行扩容

remove方法

image.png

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) { //如果hashmap的不为空，长度不为0，并且能够在数组中有相同的hash值
            Node<K,V> node = null, e; K k; V v;        //否则返回null
            if (p.hash == hash &&  这后面的逻辑就是在数组的底层和列表中和树结构中去寻找key值对应得元素
                ((k = p.key) == key || (key != null && key.equals(k)))) 
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) { //找到元素之后删除元素并且维护树结构和链表结构
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;//没有对应的元素返回null
    }