转载

手撕系列之HashMap源码

哈希、散列、杂凑本质上，把任意长度的输入，通过算法，变换成固定长度的输出是一种压缩

二、hashcode

Object类提供的方法，返回的是对象的内存地址转化为整数的结果

三、HashMap（1.8版本）

键值对的数据存储

数据结构：数组 + 链表 + 红黑树

HashMap map = new HashMap(); map.put("小飘",20);

1、map的put方法底层原理：

1）根据key值计算hash,得出在数组中对应的索引位置 2）如果此位置为空，直接将节点存入如果此位置不为空，此种情况叫哈希碰撞且此时的结构是链表，将节点插入到链表尾部（尾插法）

碰撞的可能性由两点决定： a) 数组大小和要存储数据的大小的比例 b) 哈希算法自身的散列程度

重要参数：初始容量 size, 数组大小 = 16 加载因子，loadFactor，用来衡量数组有多满的尺度默认为0.75 是时间和空间成本的折中容纳数据的极限值 16*0.75 = 12 threshold 达到此阈值需扩容

扩容直接扩容2倍，重新计算数据对应的索引位置，resize非常消耗性能。

如果此时的结构是红黑树，就将节点插入其中。

如果此时是链表结构，且节点数量大于8，转化为红黑树。本质上是为了提高查询效率。如果此时是红黑树，且节点数量小于6，再转化为链表。

注意：链表还是红黑树，本质上为了快速查询和使用的。

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;
    // (n - 1) & hash 代表计算的数组中索引位置
    // 如果此处为空  直接存储新节点    
    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);
                    // 如果节点数量大于8  转化为红黑树
                    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;
}
复制代码