原创

HashMap- resize()

【概述】

HashMap是介于数组和链表之间的数据结构,其中存储元素式键值对。键值对的对象首先存储在数组里面,数组的下标式通过key的hash值来确定,如果出现Hash碰撞,那么就会在该数组下标的元素后面添加链表的元素。如果链表的长度大于8,那么就会用红黑树来存储。

1. HashMap的数据存储方式(数组->链表->红黑树)

代码解析

从整体上讲这段代码分为两个部分,第一部分,给capacity赋值,并新建table。第二部分,给新建的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;
        //扩容的时候会用到,因为只有在有初始值的时候oldcap才能大于0
        if (oldCap > 0) {
        //oldCap达到了最大值,那么就等于最大值
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshHold也等于最大值
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //如果oldCap移位后小于最大值,就给阈值也左移一位
            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"})
        //创建新的table
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        
        
        //如果不是初始化就做数据搬迁
        if (oldTab != null) {
        //对table遍历
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //如果数组里面没有值,j
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    //table的里的值为空,就给赋值
                    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
                        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;
                        }
                    }
                }
            }
        }
        return newTab;
    }

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 设计模式——单例模式(Singleton Pattern)

    有些场景,我们只有一个对象,那么这个时候我们就要用到单例模式。单例模式是在被用到的时候才会被创建,不 用的时候不会,比较节省系统资源

    来啦老弟
  • 面向对象基础——Java多态

    我们准备实现一个王者荣耀的英雄,这里面有多个英雄,其中operator类里的operate方法可以启动某个英雄,通过多态可以实现libai或者hanxin启动。...

    来啦老弟
  • 装饰者模式

    当对一个事物进行抽象的时候,会出现一个父类,很多子类的情况。而且新添加子类时是不容易的,也就是说不易扩展。

    来啦老弟
  • HashMap的尾部遍历问题 (Tail Traversing)

    JDK1.7的HashMap在实现resize()时,新table[]的列表采用LIFO方式,即队头插入。 这样做的目的是:避免尾部遍历。

    一个会写诗的程序员
  • HashMap源码解析(JDK1.8)

    1 package java.util; 2 3 import sun.misc.SharedSecrets; 4 5 imp...

    武培轩
  • Java的ConcurrentHashMap

    ConcurrentHashMap是Java中的一个线程安全且高效的HashMap实现。

    用户3467126
  • Windows Community Toolkit 3.0 - CameraPreview

    Windows Community Toolkit 3.0 于 2018 年 6 月 2 日 Release,同时正式更名为 Windows Community...

    Shao Meng
  • 使用Optional来减少null检查

    平常我们使用null检查在项目中简直太常见了,从数据库中查询到的数据可能不存在返回null,service中处理中发现不存在返回一个null,在互相调用的时候每...

    Dylan Liu
  • [代码优化]null校验的优美处理

    我们写java代码的时候,使用对象前,都会下意识先判断对象非null,这是防止NPE的无奈之举,毕竟入门写代码时都写过npe的代码。这么做真的好吗,每层方法中都...

    逝兮诚
  • HashMap 如何解决冲突?扩容机制?

    HashMap默认的容量是DEFAULT_INITIAL_CAPACITY,16。

    暮雨

扫码关注云+社区

领取腾讯云代金券

玩转腾讯云 有奖征文活动