欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

HashMap源码学习

程序员文章站 2022-04-19 19:19:53
常用方法 方法 描述: 最常用的方法之一,用来向hash桶中 添加 键值对 .但是这个方法并不会去执行实际操作.而是委托 方法进行处理 代码: 这里调用了 方法获取了 key 的 hash ,后面单独说这个 hash 的意义 方法 描述: 实际执行 操作的方法. 代码: 方法 描述: 用于添加键值对 ......

常用方法

put方法

描述:

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

代码:

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

这里调用了hash方法获取了keyhash,后面单独说这个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方法,返回nodekey

代码:

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

valueiterator

描述:

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

代码:

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