文档章节

Java HashMap源码学习记录(一)

zhuqianli
 zhuqianli
发布于 2017/05/27 09:08
字数 1279
阅读 13
收藏 0
/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    //声明变量 tab:节点存放的数组 p:key对应的原来表里的节点
    Node<K,V>[] tab; Node<K,V> p; int n, i;

    //将全局变量table赋值给tab  tab的数组的长度赋值给n 如果表为空或者数组长度为空的话,执行resize方法
    //resize方法会在方法里对全局变量table进行赋值并返回
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    //n是当前数组的真实长度(2,4,8,16...) hash是key对应的hash值  
    //i=(n-1)&hash表示i的值必须小于等于(n-1) 
    //比如n=16,hash=101011101 则二进制(n-1)是1111, 1111&hash就是取hash后四位 1101  
    //如果对应的位置的节点(p)为空,直接新建节点,放入数组
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //如果p不为空
    else {
        Node<K,V> e; K k;
        //如果p的hash值与准备插入值的hash值一致,而且p的key和插入key一致  e=原来的节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //不一致的情况, 比如数组长度为16,说明准备插入key的hash值后四位和原来节点key的hash值后四位相等 
        //hash值还是不一样的
        //如果节点是树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //当对应的数组的索引一样,但key不一样时   (数组里的节点中的next,这种情况用,相当于一个链表)
        else {
            //递增binCount
            for (int binCount = 0; ; ++binCount) {
                //如果到达链表尾部了,在尾部插入节点 
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //当链表长度大于阈值 用树替换链表这个数据结构
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);                  
                    break;//这里返回时 e为空
                }
                //遍历的过程中发现了key一样的节点 直接结束循环
                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为true而且value不为空
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //空实现
            afterNodeAccess(e);
            //返回原来key对应的值
            return oldValue;
        }
    }
    //修改数 增加1  替换value不增加
    ++modCount;
    //map里size增加1 大于阈值调用resize方法
    if (++size > threshold)
        resize();
    //空实现
    afterNodeInsertion(evict);
    //增加了值,返回空
    return null;
}

 

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    //确定新的容量和阈值
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    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;
            //表索引为j的节点不为空 赋值给e
            if ((e = oldTab[j]) != null) {
                //将表索引为j 置为空
                oldTab[j] = null;
                //如果没有next 直接赋值
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode) //暂时不研究
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    //若存在next  则重新排序  
                    //假设:原来容量为16 现在扩容为32 
                    //则原来计算出来的索引是key的hash后四位 现在为后五位 所以要重新计算存储的位置
                    Node<K,V> loHead = null, loTail = null;//低位节点头和尾
                    Node<K,V> hiHead = null, hiTail = null;//高位节点头和尾
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //假设:原来容量为16 现在扩容为32 
                        // (e.hash & 10000)
                        //如果等于0 说明原来key的hash值 后数第五位是0 
                        if ((e.hash & oldCap) == 0) {
                            //下面就是连接节点的过程
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }//不等于0的话 后数第五位是1
                        else {
                            //下面就是连接节点的过程
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        //这里就是将低位节点头放到索引为0xxxx  x=1|0
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        //这里就是将高位节点头放到索引为1xxxx x=1|0
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
/**
 * Replaces all linked nodes in bin at index for given hash unless
 * table is too small, in which case resizes instead.
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        //将节点编程树节点(TreeNode) 设置成双向
        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);
        //将头结点放入数组中 不为空就调用TreeNode的树化方法
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}    

 

© 著作权归作者所有

zhuqianli
粉丝 5
博文 131
码字总数 57017
作品 0
杭州
程序员
私信 提问
泥沙砖瓦浆木匠/java-core-learning-example

感谢赞助的ta们 Java 核心系列教程,关于Java核心技术学习积累的例子,是初学者及核心技术巩固的最佳实践。 包括基础语法,OOP,字符串,集合,IO,反射,线程,网络等。 未完成模块:阿里J...

泥沙砖瓦浆木匠
04/02
0
0
一份关于 Java、Kotlin 与 Android 的学习笔记

JavaKotlinAndroidLearn 这是一份关于 Java 、Kotlin 、Android 的学习笔记,既包含对基础知识点的介绍,也包含对一些重要知识点的源码解析,笔记的大纲如下所示: Java 重拾Java(0)-基础知...

叶应是叶
2018/08/08
0
0
自己动手写AbstractMap

根据前辈的建议,最近在关注Java 的HashMap细节。 HashMap派生自AbstractMap,根据JDK的API描述,今天动手写了一个AbstractMap实现。 AbstractMap实现了Map<K, V>接口,Map<K,V>包含了一个内...

精神病的羽毛球
2014/03/31
0
0
京东4面(Java研发):事务隔离+乐观锁+HashMap+秒杀设计+微服务

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/t4i2b10X4c22nF6A/article/details/84347063 一面(基础面:约五十分钟) 自我介绍,主要讲讲做了什么和擅长什...

JAVA高级架构v
2018/11/22
0
0
一个三年Java工程师的面试总结

前言: 15年毕业到现在也近3年了,最近面试了阿里集团(菜鸟网络,蚂蚁金服)、网易、滴滴、点我达,最终收到点我达和网易offer,蚂蚁金服二面挂掉,菜鸟网络一个月了还在流程中...最终有幸去...

别打我会飞
2018/11/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

我为什么要写微信公众号

埋一颗种子,细心呵护,静待她枝繁叶茂,葱郁参天 V2论坛上有个帖子【做程序员最重要的还是一定要有自己的作品】,作者写道: 能有一个作品和你的名字联系在一起,应当成为在职业生涯前期着意...

运维咖啡吧
20分钟前
2
0
数据库

数据库架构 数据库架构可以分为存储文件系统和程序实例两大块,而程序实例根据不同的功能又可以分为如下小模块。 1550644570798 索引模块 常见的问题有: 为什么要使用索引 什么样的信息能成...

一只小青蛙
今天
5
0
PHP常用经典算法实现

<? //-------------------- // 基本数据结构算法 //-------------------- //二分查找(数组里查找某个元素) function bin_sch($array, $low, $high, $k){ if ( $low <= $high){ $mid = int......

半缘修道半缘君丶
昨天
5
0
GIL 已经被杀死了么?

本文原创并首发于公众号【Python猫】,未经授权,请勿转载。 原文地址:https://mp.weixin.qq.com/s/8KvQemz0SWq2hw-2aBPv2Q 花下猫语: Python 中最广为人诟病的一点,大概就是它的 GIL 了。...

豌豆花下猫
昨天
6
0
git commit message form

commit message一般包括3部分:Header、Body、Footer。 <type>(<scope>):<subject>blank line<body>blank line<footer> header是必需的,body、footer可以省略。 header中type、subject......

ninjaFrog
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部