HashMap源码思考

HashMap源码阅读

本篇内容原本写于12月3日.现在整理了一下,发出来.

文档内容

看了下官方提供的文档,因为本身就经常用,常见的特性都知道.

key,value都支持null
有两个关键参数.负载因子和初始容量。
还有什么不同步,不保持key顺序,O1时间复杂度,同步该怎么做
等等

继承与实现

mapimpl_1543814425_591588101

很简单的几个接口.(这个图就是IDEA中类继承关系的截图.blog的图片一直是挂着的,之后会考虑修一下)

map接口

其中比较值得一提的是,map接口内部还有一个entry 接口,(接口内部还有一个子接口这个东西有点意思)

map接口中添加了大量的函数式接口,让原本非常轻巧的设计,在 jdk 8 之后负担重了好多.为了支持函数式方法不得不往interface中添加default方法.

初始化

初始化的过程中有一个小东西挺有意思的

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

这个方法是在指定capacity的时候,用于快速构造最接近的2^n数设计的,设计的有点巧妙的.

先说下特例. 当cap为1的时候,n为0, 经过了5步运算之后, 容量还是1.

cap-1 的目的是为了调和最后的n+1问题.

n+1为什么会出问题呢? 因为之前的5步计算的问题.上面这5步计算的目的是把最大的1之后的所有值都变成1(二进制角度看)

n |= n >>> 1;    0 1 0 0 | 0 0 1 0 = 0 1 1 0 = 6
n |= n >>> 2;    0 1 1 0 | 0 0 0 1 = 0 1 1 1 = 7

就像上面这个代码块,第一次右移1,然后就有两个1连着了,所以第二次计算就可以变成移动2位了.

一种2^n的操作技巧.

全是1 的时候,再通过最后的+1,实现2^n,就是下面这个代码块的意思.

3- 0011
4- 0100

为了实现这个,就需要先cap-1

函数的目的是找一个和比cap大的且最近的2^n数,按照上面这种方式写,稳定(固定5次),且能达到指数级别的增长速度.而且不会出错.这个技巧非常棒.

初始化过程就非常简单了,就是验证各种异常什么的,如果没有异常就给用上面的东西直接初始化了.

put()

这个方法先调用了一个对key的hash操作,这个操作也很有意思,也非常短

hash(key)

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

^运算是异或,也就是 不同为1,相同是0.

(h = key.hashCode()) ^ (h >>> 16) 这个代表什么意思呢?

意思就是把hashCode拆分成两部分, 前部分与0做异或, 后一半与高16位做异或.

为什么这么做呢?不清楚,就像其他的hash一样,不懂.

resize()

在put()执行的过程中,对整个对象数组进行了resize()操作,这个操作是之后的门槛和现在的容量进行重新扩容的方法

逻辑上就是先判断当前的容量和上次扩容产生的临界值进行对比.if讨论的方式是分成了几种,分别是当前容量0\默认值\正常值\最大值,关于临界值的讨论就只有0和其他了.

然后就是用这些东西生成新的临界值和容量,重新初始化一个新capacity长度的node节点数组.

余下的内容就是把旧节点,放到新节点里面了.

for循环旧数组,跳过null的节点
然后判断当前节点是怎么回事,有三种情况,单一的节点, 链表, 树节点这三种情况
```
//e是循环中当前的节点,newCap是新array的size
newTab[e.hash & (newCap - 1)] = e;
```

单一的当前节点这个很有意思,他就一句话,这个是如何保证不与newTab中其他的节点冲突呢?

这里面有一个这样的逻辑.

如果某一个节点与当前的节点,按照新的运算,导致位置冲突了,说明两个节点的hash是一样的.那么就说明这两个节点,在resize()之前就是冲突的.换句话说,之前的如果就是错误的.(我搜了一下好像没有人写过这个点)

还有另外一个点,为什么要要进行&运算呢?实际上与运算有这样一个好处.

与运算能把任意的数字降低到这比这两个数字都小的水平.

举个例子,某个数字的与5进行与运算,5的二进制是0101,不管某数字是多少,最终得到的结果只有5/4/1/0/这几个可能性

所以,java这边用cap-1做与运算的目的就是为了不管hash多大,都让它在新的数组容量范围内.

当然如果cap-1是4的话0100,那么运算完了的结果就只有4和0了,那么这将会导致大量的hash冲突,因此map在初始化的时候,才会考虑用2^n来做初始化,就是为了2^n-1在二进制的时候全是1,这样才能保证这里的与运算分配均匀,至于之后每次resize()都会以进行*2的扩容,就能把hash优势保持下去了

//翻倍扩容的核心代码
newCap = oldCap << 1

上面提到的链表的操作也很有意思,看起来很复杂实际上很简单.其中核心的难点是循环中的if判断条件

原本在一个链表的内容,和新的cap-1进行&运算之后,会有两种情况,一种情况是最高位是0,另一种情况是最高位是1,这个if就是为了拆分这两种情况的.

这里面一共有5个node,其中lo指的是与oldCap进行&预算,为0即就是2^n中的唯一是1的那个数字,hi正好相反.

其中head为了生成头,为了之后塞回table,tail为了尾部往后续,逻辑非常清晰.

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

而树节点部分,暂时先不看,至此扩容部分就已经看完了.比较有意思的点都说了.

然后我们回到 putVal() 方法,这个方法首先是看有没有初始化.

然后再看put对象对应的位置有没有东西,

没东西的话就直接放进去,有的话就复杂了,要检查当前是什么样子,怎么续.又或者是更新当前节点.

在数组中,经过&运算得到的位置不为空的话,那就判断key是否相同,相同就把value进行替换.

不相同的话,就复杂了,因为节点有可能有,有可能没有,有的话,有可能还要续到链表后面,太长的话还要改成treeNode,当然也简单,找得到就改,找不到就续上,续完了之后,还要验证下是否超过了链表和tree转换的长度,超长就转换成树

treeifyBin()

这个函数的作用是把链表转为树,其中有一个很有意思的约束叫做MIN_TREEIFY_CAPACITY最小树化容纳量,意思是,如果当前的table没有超过一定尺寸,就不进行树的方法

然后一个循环就把整个单链表包装成树节点的双向链表了,然后再调用TreeNode的treeify()方法把双向链表转为红黑树

TreeNode<K,V> hd = null, tl = null;
do {
    TreeNode<K,V> p = replacementTreeNode(e, null);
    if (tl == null)
        hd = p;
    else {
    //双向链表
        p.prev = tl;
        tl.next = p;
    }
    tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)//转换为树
    hd.treeify(tab);

如果在链表中找到了节点,而且还找到了相关的点的value,满足条件的话,就更新节点e的value,

很有意思的是,这里面有一个关于新节点的回调afterNodeAccess(e);.官方给的说法是给linkedHashmap用的,这个设计还是有意思.

这个做法是,在自己的class中,定义一个空方法,然后自己调用自己,如果有class继承的话,可以通过改写这个方法,来实现对原始final putVul() 的修改.这个技巧非常有趣

正常来说,一个final类型的方法是不可以被子类修改行为的,但是通过这个额外的插槽接口,就可以让子类改写父类中final的行为.

最后的位置,这个map就像其他的collection集合一样修改mod次数,修改size,然后对比临界值再进行扩容等等操作.

putAll()

putAll和初始化构造器的方法会调用实际的putMapEntries()进行执行,实际的执行策略非常简单.

它会直接比较临界值,进行数组的扩容操作,然后再循环把新的节点进行插入.

get()

get方法实际调用的是getNode(),通过hash和key来获取整个node,查询逻辑非常简单,和其他的处理节点的逻辑是一样的,当前这个是不是,不是的话,之后的是不是,找不到就null

remove()

依旧很简单,不过removeNode 首先是实现了一遍,get内部的操作,然后在进行匹配的时候通过一个matchValue变量来只是是否匹配value—-唯一值得学的一个点.

containsValue()

这个操作要对整个的map进行扫描,找到就返回true,比较慢

内部类

keySet()

这是一个抽象的内部类,一个map只有一个,初始化之后就不会有了,这个keySet只提供一些删除\迭代的操作,新增什么的完全不存在,

而且在修改的时候,直接调用原始对象,做一样的修改.

其他的一扫而过,就感觉十分乏味了,就是不停地迭代各种东西,

这个map中内部类很多,原因就在于,可以分别迭代map中的各种东西,key/value/entry这三个东西,都可以分别迭代,

目前看到比较有意思的一个点就是,在内部类中,不但实现了不同类型的子数组,还实现了不同的子数组的迭代器.迭代器是比较有意思的,因为只有这么一个核心迭代器,其他的迭代器都只重写了next()方法.

核心的迭代器是不停地迭代node节点,然后三个派生的迭代器分别是按照节点的key/value/node分别执行的.

treeNode

剩下就是一个treddnode 红黑树的实现了.500多行的实现,看着就头大.

总结

整个hashmap算是看了,至少看了有一半了,里面有大量的简写.

刚开始理解起来还比较累,好在有IDE的帮助,变量都能实时的对应起来,后来熟悉了这种写法,就能理解是怎么回事了.

这个类库的代码绝对不是适合日常的业务代码.

单独的一个map中,类库里面还有大量的内部类,和各种抽象的实现,还有大量的final/static的东西,这些东西都是需要深入思考的.

而且这个hashmap还有不少子类,子类怎么用怎么操作,也很值得回味.因为这个hashmap为子类提供了一些东西,让它能够做改.

总的来说,hashmap里面值得学习的点还是非常多的.

但是设计上的东西真的不好表述.也不知道该怎么学啊.哎