HashMap

作者: 无力韬韬 | 来源:发表于2020-11-23 20:58 被阅读0次

HashMap了解一下
HashMap源码
2018-03-12
HashMap源码理解
【16】 hashmap
HashMap源码分析
HashMap剖析
Java-HashMap 精讲原理篇
HashMap源码解析（HashMap类-构造方法）
HashMap源码解析JDK8

HashMap按照<key,value>键值对的方式来存储。
hashmap把键值对存入数组里，实际上数组里面存放的是Node类的实体，Node类是一个单向的链表结构，键值是Node实体中的两个属性，除此之外，他还有hash属性，代表hash值，以及next属性，代表链表的下一个节点。

public class test {
    public static void main(String[] args) {
        HashMap<Integer,Integer> map=new HashMap<>();
        map.put(1,1);
    }
}

put方法

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

put方法中调用了两个方法分别是putVal(),和hash()。

hash()方法
hash方法里的内容非常简单

        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

就是获取key的hashcode，将hashcode右移16位，得到这个值再和自身进行异或运算。
然后将这个值返回回去，（如果key是空直接返回0）。
为什么要进行异或运算，其实这一步就是将key的hashcode码的高位与低位进行混合运算，同时又保留了高位的值，用来加大低位的随机性。
加大低位的随机性可以降低哈希冲突的可能性，因为Node<K,V>存放在哪个桶是通过低位&length-1 得到的。

putVal()方法
在这个方法里面进行了数据存放的过程。

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

首先putVal方法获得要存入的键值，以及经过hash方法计算得到的hash值，另外两个boolean类型的参数暂时不关心。
第一步是判断table是否为空。

table

table就是map这个对象的一个数组，当进行了HashMap<>() map=new HashMap<>()的时候，table被定义出来,但是此时并没有初始化,所以table为空，所以可以得到当HashMap执行put方法时，才会有数组空间被开辟出来。
原因可能是为了节省空间，不用不开。

如果table为空或者table的长度为0就执行resize()方法，此时resize()方法会默认开辟一个长度为16的数组。
第二步，查看要存的位置是否不存在值，不存在则直接存进去，如果存在，就要分情况。
如果要存的值和已经有的值hash值相同，并且key也相同，就把原来的值覆盖掉,
例如

        map.put(1,1);
        map.put(1,2);
        System.out.println(map.get(1));

输出得到的结果就是2，1已经被覆盖掉了。
如果不满足上述情况并且要存放数的位置此时已经变成了红黑树，则把这个Node也转换成树的节点，然后放入树中。
如果不满足上述两种情况，则这个位置此时还是链表，就采用尾插法把要存放的值放入链表里，同时判断链表的长度是否大于8并且数组的长度是否大于64，如果都满足则要把链表转换成红黑树。