手撕系列之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;
}
复制代码

2、为什么长度总是2的幂次方?

当使用时,默认是2的幂次方——16,扩容时直接2倍。
当设定某个size时,会查找距离此值最近的2的幂次方。
比如 给出 18 —— 32。

(n – 1) & hash 代表计算的数组中索引位置

等价于取模的运算,但性能更高
此时n需要是2的幂次方,使得计算出的索引位置尽量散列,
尽量减少hash碰撞

3、hashmap是线程安全的,多线程使用1.7版本,会引发什么问题?

1.7版本,只有数组+链表,且链表的插入逻辑是头插法。
在多线程环境中,可能因为逆序形成环形链表,引发死循环。

4、红黑树

二叉树 -> 二叉排序/查找树 -> 二叉平衡树

左子树的节点都小于根节点
右子树的节点都大于根节点

二叉平衡树,是一种自平衡的二叉查找树

红黑树 , 金字塔尖的二叉树 ,查找效率 logN
10亿数据而言,多少次找到目标数据? 30

概念

  1. 节点是红色或黑色的
  2. 根节点一定是黑色的
  3. 叶子节点都是黑色的
  4. 红色节点的子节点都是黑色的 (红黑穿插)
  5. 从任一节点到叶子节点的所有简单路径,都包含相同数目的黑色节点。

自平衡策略:旋转和变色
1)变色 —— 红变黑、黑变红
2)旋转
左旋转 右旋转

左旋,影响的是旋转节点和右子树的结构
右旋,影响的是旋转节点和左子树的结构

节点之间的关系:
父节点、祖父节点、叔父节点

假设要插入的节点是X , 父节点P、祖父节点G、叔父节点U
插入原则:新插入的节点一律为红色,可以简化自平衡的过程。

不同场景:
1)如果X是根节点,插入到根节点中,将红色变为黑色

2)如果X的父节点是黑色的
如果X在左侧,不需变化
如果X在右侧,此时需要先左旋,再变色。

3)如果X的父节点是红色的,再根据叔父节点的颜色,查看要进行哪种操作?

原文 

https://juejin.im/post/5efede875188252e3f65d863

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 手撕系列之HashMap源码

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址