HashMap源码学习

常用方法

put方法

描述:

最常用的方法之一,用来向hash桶中添加 键值对.但是这个方法并不会去执行实际操作.而是委托putval方法进行处理

代码:

public v put(k key, v value) {
    // 这次个调用分别指定了hash,key,value,替换现有值,非创建模式
    return putval(hash(key), key, value, false, true);
}

这里调用了hash方法获取了key的hash,后面单独说这个hash的意义

putval方法

描述:

实际执行put操作的方法.

代码:

final v putval(int hash, k key, v value, boolean onlyifabsent,
               boolean evict) {
    // tab - 当前hash桶的引用
    // p - key所代表的节点(此节点不一定是目标节点,而仅仅是hash与桶长度的计算值相同而已)(它不为空时可能是链表或红黑树)
    // n - 当前桶的容量
    // i - key在桶中的下标(同p,不代表目标节点)
    node<k,v>[] tab; node<k,v> p; int n, i;
    // 初始化局部变量tab并判断是否为空,初始化局部变量n并判断是否为0
    // ps: 源码中大量的使用了这种书写方法,不知道放在某写大厂里会怎么样(斜眼笑)
    if ((tab = table) == null || (n = tab.length) == 0)
        // 当tab为空或n为0时,表明hash桶尚未初始化,调用resize()方法,进行初始化并再次初始化局部变量tab与n
        n = (tab = resize()).length;
    
    // 初始化p与i
    // 这里使用了(n - 1) & hash的方式计算key在桶中的下标.这个在后面单独说明
    // 当p是否为空
    if ((p = tab[i = (n - 1) & hash]) == null)
        // p为空,调用newnode方法初始化节点并赋值到tab对应下标
        tab[i] = newnode(hash, key, value, null);
    else {
        // p不为空,发生碰撞.进行后续处理
        
        // e - 目标节点
        // k - 目标节点的key
        node<k,v> e; k k;
        
        // 判断key是否相同.(这里除了比较key以外,还比较了hash)
        // 注意,这里同时初始化了局部变量k,但是在第二组条件不满足的情况下,没有使用价值,可以被忽略
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // key相同,将e(目标节点)设置为p
            e = p;
        // 判断节点是否是红黑树
        else if (p instanceof treenode)
            // 确定时,直接委派处理
            e = ((treenode<k,v>)p).puttreeval(this, tab, hash, key, value);
        else {
            // 走到这里,代表当前节点为普通链表,进行遍历查找
            // 变量bincount只作为是否达到tree化的阈值判断条件.
            for (int bincount = 0; ; ++bincount) {
                
                // 获取链表的下一个元素,并赋值到e(此时e是一个中间变量,不确定是否是目标节点)
                // 第一次for循环时,p代表hash桶中的节点(同时也是链表的头部节点),之后一直等于p.next
                if ((e = p.next) == null) {
                    // 链表遍历到末尾
                    
                    // 向链表中追加新的节点
                    p.next = newnode(hash, key, value, null);
                    
                    // 判断当前链表长度是否达到tree阈值
                    if (bincount >= treeify_threshold - 1) // -1 for 1st
                        // 调用treeifybin方法直接处理
                        treeifybin(tab, hash);
                    // 中断循环
                    // 注意,此时局部变量e=null
                    break;
                }
                
                // 能走到此处,说明链表未结束,比较e的k是否相同(hash与==)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // key相同
                    break;
                
                // e既不为null也不是目标节点,赋值到p,准备进行下次循环
                p = e;
            }
        }
        
        // 判断e是否存在
        if (e != null) { // existing mapping for key
            // e不等于null说明操作为"替换"
            
            // 缓存老值
            v oldvalue = e.value;
            // 判断是否必须替换或老值为null
            if (!onlyifabsent || oldvalue == null)
                // 必须替换或老值为空,更新节点e的value
                e.value = value;
            // 调用回调
            afternodeaccess(e);
            // 返回老值
            // 注意,这里直接返回了,而没有进行modcount更新与下面的后续操作
            return oldvalue;
        }
    }
    
    // 除了更新链表节点以外,都会走到这里(puttreeval的返回值是什么有待确认)
    // modcount+1
    ++modcount;
    // size+1(元素数量+1)
    // 判断是否超过阈值
    if (++size > threshold)
        // 重置大小
        resize();
    // 调用后置节点插入回调
    afternodeinsertion(evict);
    return null;
}

resize方法

描述:

用于添加键值对后的扩容与对槽重新分布的操作

代码:

final node<k,v>[] resize() {
    //----------------------------------- 新容量与阈值计算 -----------------------------------
    
    // 缓存桶引用
    node<k,v>[] oldtab = table;
    // 缓存老的桶的长度,桶为null时,使用0
    // 注意,这里用的是oldtab.length,而不是size
    int oldcap = (oldtab == null) ? 0 : oldtab.length;
    // 缓存阈值
    int oldthr = threshold;
    // 新桶容量与阈值
    int newcap, newthr = 0;
    
    // 老容量大于.这一般代表这个桶已经经过了resize的数次处理
    if (oldcap > 0) {
        
        // 老容量大于maximum_capacity = 1 << 30 = 1073741824
        // 容量计算方式为n<<1,当oldcap >= maximum_capacity时,再次执行位移.其可能的最大值就是integer.max_value
        if (oldcap >= maximum_capacity) {
            // 设置阈值为integer.max_value
            threshold = integer.max_value;
            // 直接return.放弃全部后续处理
            return oldtab;
        }
        // 使用oldcap << 1初始化newcap
        // 当oldcap小于maximum_capacity并且oldcap大于default_initial_capacity(16)时
        // 此时newcap可能已经大于maximum_capacity并且newthr=0或者newcap很小(小于16>>2)并且newthr=0
        else if ((newcap = oldcap << 1) < maximum_capacity &&
                 oldcap >= default_initial_capacity)
            //设置newthr为oldthr << 1(这里没有做正确性校验,待查)
            newthr = oldthr << 1; // double threshold
    }
    // 判断老阈值是否大于0
    // 走到这说明oldcap==0,并且使用了包含initialcapacity参数的构造器构造了这个map,且没有被添加过元素
    else if (oldthr > 0) // initial capacity was placed in threshold
        // 使用将新容量复制为老阈值(newcap此时为0)
        // 注意: 在使用了包含initialcapacity参数的构造方法时,其threshold已经被计算为2的n次幂
        newcap = oldthr;
    else {               // zero initial threshold signifies using defaults
        // 默认方法,当使用无参构造方法时,会出现oldthr与oldcap都等于0的情况
        // 使用默认初始化容量赋值到newcap
        newcap = default_initial_capacity;
        // 使用默认初始化容量与加载因子相乘赋值到newthr
        newthr = (int)(default_load_factor * default_initial_capacity);
    }
    
    // 统一处理newthr
    if (newthr == 0) {
        // 新容量与加载因子相乘
        float ft = (float)newcap * loadfactor;
        // 当newcap与ft均小于maximum_capacity时,newthr=ft.否则newthr=integer.max_value
        newthr = (newcap < maximum_capacity && ft < (float)maximum_capacity ?
                  (int)ft : integer.max_value);
    }
    
    //----------------------------------- 元素重排 -----------------------------------
    // 更新threshold
    threshold = newthr;
    @suppresswarnings({"rawtypes","unchecked"})
    // 更新桶对象(此时是空的)
    node<k,v>[] newtab = (node<k,v>[])new node[newcap];
    table = newtab;
    // 判断老桶是否为空
    if (oldtab != null) {
        // 老桶不为空.进行遍历
        for (int j = 0; j < oldcap; ++j) {
            // 桶元素
            node<k,v> e;
            // 进行桶元素获取
            // 判断桶元素是否存在(因为使用(n-1)&hash的方式进行计算,所以经常会出现这种情况)
            if ((e = oldtab[j]) != null) {
                // 删除引用
                oldtab[j] = null;
                // 判断桶元素是否有下一个元素
                if (e.next == null)
                    // 没有下一个元需.使用相同的算法计算在新桶中的下标并赋值
                    newtab[e.hash & (newcap - 1)] = e;
                // 桶元素存在next,判断是否为treenode
                else if (e instanceof treenode)
                    // 进行委派执行
                    ((treenode<k,v>)e).split(this, newtab, j, oldcap);
                else { // preserve order
                    // 对于链表结构,拆分到高位与低位两组
                    
                    // lohead与lotail非别代表低位头与低位尾
                    node<k,v> lohead = null, lotail = null;
                    // hihead与hitail非别代表高位头与高位尾
                    node<k,v> hihead = null, hitail = null;
                    // next
                    node<k,v> next;
                    // 已经存在遍历目标,直接使用do while
                    do {
                        // 拿到e的next.
                        next = e.next;
                        // 判断e的hash是否是高位
                        // 判断原理如下.
                        // 首先oldcap恒定为2的n次幂,二进制表达为1000...
                        // 下标计算方程为(n-1)&hash
                        // 带入n后,为...111&hash
                        // 当n=111时,hash为1101,结果为101
                        // 当n=1111时,hash为1101,结果为1101.表示为高位(注意hash的高位)
                        // 当n=1111时,hash为0101,结果为101.表示为低位(注意hash的高位)
                        // 这样就,可以直接求出新的下标.但是,这种方式需要对所有的元素进行重新计算,非常低效
                        // 所以jdk使用了一个特别的方法.就是直接比较最高位,当一个hash与数组长度(也就是n的n次幂)时,如1101&1000
                        // 当结果等于0时,代表这个hash是低位hash,其他就是高位hash
                        if ((e.hash & oldcap) == 0) {
                            // 低位
                            // 判断低位尾部是否存在
                            if (lotail == null)
                                // 不存在,代表头部也没有,进行初始化
                                lohead = e;
                            else
                                // 存在,追加到尾部的next
                                lotail.next = e;
                            // 更新尾部
                            lotail = e;
                        }
                        else {
                            // 高位
                            if (hitail == null)
                                // 不存在,代表头部也没有,进行初始化
                                hihead = e;
                            else
                                // 存在,追加到尾部的next
                                hitail.next = e;
                            // 更新尾部
                            hitail = e;
                        }
                    } while ((e = next) != null);
                    
                    // 进行收尾处理
                    // 判断低位是否为空
                    if (lotail != null) {
                        // 不为空
                        // 清除末尾元素的next.当lotail是链表倒数第二个元素且倒数第一个元素是高位元素时,需要清空lotail的next对高位元素的引用
                        lotail.next = null;
                        // 低位使用原下标进行保存
                        newtab[j] = lohead;
                    }
                    if (hitail != null) {
                        // 不为空
                        // 清除末尾元素的next.理由同上但判断方式相反
                        hitail.next = null;
                        // 低位使用原下标+原容量进行保存
                        newtab[j + oldcap] = hihead;
                    }
                }
            }
        }
    }
    // 返回newtab
    return newtab;
}

treeifybin方法

描述:

当某槽内的链表长度大于阈值后,此方法会被调用.将槽内对应位置的链表替换为红黑树.
注意:这个方法内只是将链表替换成了红黑树对象treenode.此时还是链状结构,没有组装成红黑树的结构.需要在最后带用链表头部对象的treenode.treeify方法完成树化

代码:

final void treeifybin(node<k,v>[] tab, int hash) {
    // n - 代表参数tab长度
    // index - tab中表示hash的下标
    // hash - 待处理的链表节点hash
    // e - 目标节点
    int n, index; node<k,v> e;
    // 判断tab是否为空或tab长度min_treeify_capacity=64
    // 也就是说,在桶中单个链表长度可能已经达到要求(如putval中的bincount >= treeify_threshold - 1),但是桶容量未达标时,也不会进行tree化
    if (tab == null || (n = tab.length) < min_treeify_capacity)
        // 表是空的或表容量小于min_treeify_capacity
        // 重置大小
        resize();
    // 可以tree化,检查链表节点是否存在
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 链表节点存在
        
        // 树节点头与尾
        treenode<k,v> hd = null, tl = null;
        // 已经有第一个目标,直接do while
        do {
            // 构造一个treenode.(这里没有额外逻辑,仅仅是使用当前的e创建了treenode)
            // 注意,这里的tree继承自linkedhashmap.entry,内部包含了before与after的双向链表.但是treenode又自行实现了双向链表prev与next,并没有使用前者的数据结构
            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)
            // 调用treenode的treeify组装红黑树
            hd.treeify(tab);
    }
}

即使被调用,这个方法也不保证替换对应槽内的链表到红黑树.这还需要检查当前桶的容量是否达到阈值min_treeify_capacity

treenode.treeify方法

描述:

将链表结构的数据转换成红黑树结构的数据的实际执行者(此时链表中的所有对象已经是treenode类型的了)

代码:

final void treeify(node<k,v>[] tab) {
    // 根节点(黑色节点)
    treenode<k,v> root = null;
    // 进行迭代.(当前this作用域位于treenode实例)
    // x表示当前遍历中的节点
    for (treenode<k,v> x = this, next; x != null; x = next) {
        // 缓存next
        next = (treenode<k,v>)x.next;
        // 保证当前节点左右节点为null
        x.left = x.right = null;
        // 判断是否存在根节点
        if (root == null) {
            // 不存在
            // 跟节点没有父级.所以设置为null
            x.parent = null;
            // 红黑树中,根节点是黑色的
            x.red = false;
            // 保存到局部变量
            root = x;
        }
        else {
            // 跟节点已确认
            
            // 缓存key
            k k = x.key;
            // 缓存hash
            int h = x.hash;
            // key类型
            class<?> kc = null;
            // -------------------- 对跟节点进行遍历,查找插入位置 --------------------
            // p是插入节点的父节点
            for (treenode<k,v> p = root;;) {
                // dir - 用来表达左右.
                // ph - 父节点hash
                int dir, ph;
                // 父节点key
                k pk = p.key;
                
                // -------------------- 判断插入到左还是右节点 --------------------
                // 初始化父节点hash
                // 判断父节点hash是否大于当前节点hash
                if ((ph = p.hash) > h)
                    // dir = -1 插入节点在父节点左侧
                    dir = -1;
                // 判断父节点hash是否小于当前节点hash
                else if (ph < h)
                    // dir = 1 插入节点在父节点右侧
                    dir = 1;
                // 父节点hash等于当前节点hash,进行额外的处理
                // 这里使用了基于class的一些处理办法,最终保证了dir的正确值(不为0) todo 待补充 
                else if ((kc == null &&
                          (kc = comparableclassfor(k)) == null) ||
                         (dir = comparecomparables(kc, k, pk)) == 0)
                    dir = tiebreakorder(k, pk);


                // -------------------- 获取左或右节点并进行操作 --------------------
                // 缓存插入节点的父节点
                treenode<k,v> xp = p;
                // 使用dir获取父节点对应的左或右节点,并且检查这个节点是否为null.不为null时,进入下一次循环
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    // 父节点左或右节点为null
                    
                    // 设置父级节点
                    x.parent = xp;
                    // 再次判断左右
                    if (dir <= 0)
                        // 将父节点的左子节点复制为当前节点
                        xp.left = x;
                    else
                        // 将父节点的右子节点复制为当前节点
                        xp.right = x;
                    // 进行平衡
                    root = balanceinsertion(root, x);
                    // 退出查找插入位置的循环,进行下一个元素的插入
                    break;
                }
            }
        }
    }
    
    // 因为在进行旋转操作时,可能会修改根节点到其他节点.导致桶中的直接节点为分支节点,所以需要进行修正
    moveroottofront(tab, root);
}

hash方法

描述:

hashmap自己使用的hash的计算方式.作为key比较,index的计算依据.它通过对象原hash与其高16位进行^运算,而得出一个新值做回hash.

代码:

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

这里之所以没有直接使用key的hash.是为了应对当key的hash分布非常差的时候,会间接导致
hash桶的分布非常差,从而影响性能.所以使用原hash异或(xor)原hash的高16位,作为实际使用的hash
这里之所以使用16:16,而不是8:8:8:8或其他值,是因为jdk开发者充分考虑了时间,效率,性能等各方面
的情况后的折中选择.
同时也是因为当前jdk大多数的hash已经有了较好的分布,所以也不需要进行过多的处理
计算过程如下
10000000000000000000000000000000
00000000000000001000000000000000
10000000000000001000000000000000

tablesizefor方法

描述:

一般用作threshold的初始化工作.他会返回一个大于输入值的最小的2的幂.已经是2的幂时会再次返回它.

代码:

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

直接上流程(暂时忽略cap - 1部分,最后说)
10000 16 n初始状态
11000 24 n|=n>>>1 等价于 n = 10000|01000 = 11000
11110 30 n|=n>>>2 等价于 n = 11000|00110 = 11110
11111 31 n|=n>>>4 等价于 n = 11110|00001 = 11111
11111 31 略
11111 31 略
100000 32 n+1
最后,通过+1,将...111变为100...,即2的n次幂

这里使用了一个很有意思的方式完成了工作,就是输入值的最高有效位.
通过不断的向低位复制最高有效位(1),将所有低位换为1,最终这个值等于(2^n)-1.同时
也是当前数字的最高位能表达的最大值
那么,再对这个值+1就可以使这个值变成2^n.也就是大于输入值的最小的2的幂

cap - 1的作用:
如果输入值已经是2的幂,那么这个方法应该直接返回他.直接进行-1,使用原逻辑即可

内部类

hashiterator

描述:

hashmap自己实现的迭代器.主要用来约束对父类成员的引用.同时实现了remove,nextnode,hasnext等必须方法.为了方便子类实现,在nextnode方法中直接返回了node类型对象.用来直接获取key与value

代码:

abstract class hashiterator {
    /**
    * 下一个节点 
    */
    node<k,v> next;        // next entry to return
    /**
    * 当前节点 
    */
    node<k,v> current;     // current entry
    /**
    * 修改计数
    */
    int expectedmodcount;  // for fast-fail
    /**
    * 当前下标(对于父级成员变量table来说,它指向桶中的一个槽(slot))
    */
    int index;             // current slot

    /**
    * 构造方法 
    */
    hashiterator() {
        // 缓存修改计数
        expectedmodcount = modcount;
        // 缓存桶 
        node<k,v>[] t = table;
        // 进行置空(这一步是必须的吗????) 
        current = next = null;
        // 索引置0(为啥?????) 
        index = 0;
        // 检查桶是否已经初始化 
        if (t != null && size > 0) { // advance to first entry
            // 提前获取并保存next
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasnext() {
        return next != null;
    }

    final node<k,v> nextnode() {
        // 指向当前桶
        node<k,v>[] t;
        // 缓存next.准备替换next.同时e作为结果返回
        node<k,v> e = next;
        // fast-fail
        if (modcount != expectedmodcount)
            throw new concurrentmodificationexception();
        // next不应为空
        if (e == null)
            throw new nosuchelementexception();
        // -------------------- 寻找next --------------------
        // 设置current为e,next为e.next
        // 判断next是否为null
        // 如果为空,获取当前桶
        // 判断桶是否为空(能走到这里,说明之前已经在桶中获取了节点,那桶怎么回事空的呢?????)
        if ((next = (current = e).next) == null && (t = table) != null) {
            // 上面的next获取失败,这里使用切换槽位的方式寻找下一个next
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }

    public final void remove() {
        node<k,v> p = current;
        if (p == null)
            throw new illegalstateexception();
        // fast-fail
        if (modcount != expectedmodcount)
            throw new concurrentmodificationexception();
        // 删除当前迭代其中的current
        current = null;
        // 获取key
        k key = p.key;
        // 调用父级删除方法
        // 这里设置了movable为false,删除后不移动节点.这个值只对treenode生效,去要考证设置成false的作用
        // 貌似是在迭代器中被设置了false
        removenode(hash(key), key, null, false, false);
        // 更新计数
        expectedmodcount = modcount;
    }
}

keyiterator

描述:

hashiterator的实现.包装了其中的nextnode方法,返回node的key

代码:

final class keyiterator extends hashiterator
    implements iterator<k> {
    public final k next() { return nextnode().key; }
}

valueiterator

描述:

hashiterator的实现.包装了其中的nextnode方法,返回node的value

代码:

final class valueiterator extends hashiterator
    implements iterator<v> {
    public final v next() { return nextnode().value; }
}

entryiterator

描述:

hashiterator的实现.包装了其中的nextnode方法,直接返回了node

代码:

final class entryiterator extends hashiterator
    implements iterator<map.entry<k,v>> {
    public final map.entry<k,v> next() { return nextnode(); }
}

keyset

描述:

继承了abstractset,并通过内部类的特性,使实现方法通过直接调用父类hashmap的引用完成完成

代码:

final class keyset extends abstractset<k> {
    /**
    * 返回hashmap的成员变量size
    * @return 
    */
    public final int size()                 { return size; }
    /**
    * 因为是同名方法,所以只能使用类名.this.methodname()的方式调用了
    */
    public final void clear()               { hashmap.this.clear(); }
    /**
    * 返回一个内部类key迭代器
    * @return 
    */
    public final iterator<k> iterator()     { return new keyiterator(); }
    /**
    * 调用父类方法
    * @param o
    * @return 
    */
    public final boolean contains(object o) { return containskey(o); }
    /**
    * 调用父类方法.标记不需要匹配值,删除后重建
    * @param key
    * @return 
    */
    public final boolean remove(object key) {
        return removenode(hash(key), key, null, false, true) != null;
    }
    /**
    * 返回一个内部类keyspl迭代器
    * @return 
    */
    public final spliterator<k> spliterator() {
        return new keyspliterator<>(hashmap.this, 0, -1, 0, 0);
    }
    /**
    * 实现foreach
    * 这里有个需要注意的地方
    * 对于fail-fast,这个方法会在所有元素迭代完成之后进行,才进行判断
    * @param action
    */
    public final void foreach(consumer<? super k> action) {
        node<k,v>[] tab;
        if (action == null)
            throw new nullpointerexception();
        if (size > 0 && (tab = table) != null) {
            int mc = modcount;
            for (int i = 0; i < tab.length; ++i) {
                for (node<k,v> e = tab[i]; e != null; e = e.next)
                    action.accept(e.key);
            }
            if (modcount != mc)
                throw new concurrentmodificationexception();
        }
    }
}