`
noble510520
  • 浏览: 57990 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

jdk源码分析ArrayDeque

    博客分类:
  • java
阅读更多

ArrayDeque

数组循环队列,这个数据结构设计的挺有意思的。
据说此类很可能在用作堆栈时快于 Stack,在用作队列时快于 LinkedList。

一、容量

1.1默认容量是8=2^3

1.2指定初始化容容量

    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }
    private void allocateElements(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0) // Too many elements, must back off initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        elements = new Object[initialCapacity];
    }
此方法是给数组分配初始容量,初始容量并不是numElements,而是大于指定长度的最小的2的幂正数
所以ArrayDeque的容量一定是2的幂整数
计算的方法是用或运算

1.3或运算的特点:

得到的结果大于等于任意一个操作数
结果有趋向每个位都为1的趋势
所以这样运算下来,运算得到的结果的二进制一定是每个位都是1,再加一个,就刚好是2的整数幂了

1.4扩展容量

当头尾指针相遇,则数组存满了
clipboard
此时要扩展容量,会调用
    private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;//bit count faster
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);//copy the right of head(include head)
        System.arraycopy(elements, 0, a, r, p);//copy the left of the tail(exclude tail)
        elements = a;
        head = 0;
        tail = n;
    }

1.5细说doubleCapacity

注意看:
1.求两本容量,n<<1,使用位运算要快于四则运算,因为这更贴近运算器电路的设计
2.复制原来的数组到目标数组要注意顺序!
可以看到,复制分两次复制进行,第一次复制head指针右边的元素(包括head指针指向的那个),第二次复制left指针左边的元素(不包括tail指针指向的那个)
扩展为原来两本的容量,结果还是2的幂整数
为什么容量一定要是2的幂整数呢?待会说

二、头尾指针

clipboard
一开始,头尾指针都在下标为0的地方,如果向队头插入数据,头指针向左移,向队尾插入数据,尾指针向右移
tail指针所在的位置,不存储数据,代表下一次addLast存储的地方

三、add

队列提供增加到队首和队尾的两种方法,注意看怎么处理指针临界状态和指针循环

3.1addLast

    public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }
移动tail指针,用了与运算
与运算的特点:
结果一定小于等于任意一个操作符的值
与正数进行与运算结果一定为证
当tail+1了之后,超过数组长度,用与运算可以起到循环指针的效果,相当于(tail+1%elements.length)
因为elements.length一定是2的整数幂,当-1了之后每一位一定是1,当tile+1超过数组长度的时候,刚好是2的整数幂,则是10***00这种形式,所以与运算了之后,一定等于0

3.2addFirst

    public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }
当head-1<0的时候,用与运算可以得到绝对值,并且循环指针
因为当head超过数组,head-1刚好是-1,则二进制每个都是1,与运算了之后,一定是111***111的正数,刚好是数组的最后一个位置

四、指针相遇

当tail == head的时候,首尾指针重合,此时队列已满,需要扩展队列,调用doubleCapacity

五、利用空间局部性

在方法中需要多次调用的全局变量,最好创建一个局部变量来访问
因为全局变量是在静态存储区中的,局部变量是放在栈中的,和方法的指令中同一个区域,所以访问会更快,提高程序性能
就像下面这样
    public boolean removeFirstOccurrence(Object o) {
        if (o == null)
            return false;
        int mask = elements.length - 1;
        int i = head;
        Object x;
        while ( (x = elements[i]) != null) {
            if (o.equals(x)) {
                delete(i);
                return true;
            }
            i = (i + 1) & mask;
        }
        return false;
    }
创建了一个mask,来存放elements.length-1

6.优化删除策略

    private boolean delete(int i) {
        checkInvariants();
        final Object[] elements = this.elements;
        final int mask = elements.length - 1;
        final int h = head;
        final int t = tail;
        final int front = (i - h) & mask;
        final int back  = (t - i) & mask;

        // Invariant: head <= i < tail mod circularity if (front >= ((t - h) & mask))
            throw new ConcurrentModificationException();

        // Optimize for least element motion
        //最优化删除策略
        if (front < back) {//如果要删除的元素在前半段
            if (h <= i) {//如果head在要删除元素的前面
                System.arraycopy(elements, h, elements, h + 1, front);//将要删除元素的前继元素往后移动一格
            } else { // Wrap around
                System.arraycopy(elements, 0, elements, 1, i);//把i前面的元素往后挪一格
                elements[0] = elements[mask];
                System.arraycopy(elements, h, elements, h + 1, mask - h);//head-数组末端(不包括数组末端) 都往后移一格
            }
            elements[h] = null;//帮助垃圾收集
            head = (h + 1) & mask;//头指针回退一格
            return false;
        } else {
            if (i < t) { // Copy the null tail as well
                System.arraycopy(elements, i + 1, elements, i, back);
                tail = t - 1;
            } else { // Wrap around
                System.arraycopy(elements, i + 1, elements, i, mask - i);
                elements[mask] = elements[0];
                System.arraycopy(elements, 1, elements, 0, t);
                tail = (t - 1) & mask;
            }
            return true;
        }
    }
这段源码我觉得很值得一看,他用了最优删除策略,都适用与数组实现的数据结构
当删除的时候,先计算删除点是在队列的上半段还是下半段
如果是上半段,则上半段移动一格
这样子可以达到最少的元素移动!
对于这种循环队列,需要注意删除元素的位置,有两种特殊位置

6.1第一种特殊位置

clipboard1
此时删除节点在队列的上半段,但是上半段是断开的
这个时候要移动上半段的话,要分两次移动
第一次移动删除元素前面的,第二次移动头指针到数组末端

6.2第二种特殊位置

clipboard



查看原文:http://blog.zswlib.com/2016/10/27/jdk%e6%ba%90%e7%a0%81%e5%88%86%e6%9e%90arraydeque/

0
1
分享到:
评论

相关推荐

    win7修复本地系统工具

    win7修复本地系统工具

    《自动化专业英语》04-Automatic-Detection-Block(自动检测模块).ppt

    《自动化专业英语》04-Automatic-Detection-Block(自动检测模块).ppt

    《计算机专业英语》chapter12-Intelligent-Transportation.ppt

    《计算机专业英语》chapter12-Intelligent-Transportation.ppt

    西门子S7-1200博图平台下3轴伺服螺丝机程序解析与应用

    内容概要:本文详细介绍了基于西门子S7-1200博图平台的3轴伺服螺丝机程序。该程序使用SCL语言编写,结合KTP700组态和TIA V14及以上版本,实现了对X、Y、Z三个轴的精密控制。文章首先概述了程序的整体架构,强调了其在自动化控制领域的高参考价值。接着深入探讨了关键代码片段,如轴初始化、运动控制以及主程序的设计思路。此外,还展示了如何通过KTP700组态实现人机交互,并分享了一些实用的操作技巧和技术细节,如状态机设计、HMI交互、异常处理等。 适用人群:从事自动化控制系统开发的技术人员,尤其是对西门子PLC编程感兴趣的工程师。 使用场景及目标:适用于希望深入了解西门子S7-1200博图平台及其SCL语言编程特点的学习者;旨在帮助读者掌握3轴伺服系统的具体实现方法,提高实际项目中的编程能力。 其他说明:文中提供的代码示例和设计理念不仅有助于理解和学习,还能直接应用于类似的实际工程项目中。

    MATLAB仿真:非线性滤波器在水下长基线定位(LBL)系统的应用与比较

    内容概要:本文详细探讨了五种非线性滤波器(卡尔曼滤波(KF)、扩展卡尔曼滤波(EKF)、无迹卡尔曼滤波(UKF)、粒子滤波(PF)和变维卡尔曼滤波(VDKF))在水下长基线定位(LBL)系统中的应用。通过对每种滤波器的具体实现进行MATLAB代码展示,分析了它们在不同条件下的优缺点。例如,KF适用于线性系统但在非线性环境中失效;EKF通过雅可比矩阵线性化处理非线性问题,但在剧烈机动时表现不佳;UKF利用sigma点处理非线性,精度较高但计算量大;PF采用蒙特卡罗方法,鲁棒性强但计算耗时;VDKF能够动态调整状态维度,适合信标数量变化的场景。 适合人群:从事水下机器人(AUV)导航研究的技术人员、研究生以及对非线性滤波感兴趣的科研工作者。 使用场景及目标:①理解各种非线性滤波器的工作原理及其在水下定位中的具体应用;②评估不同滤波器在特定条件下的性能,以便为实际项目选择合适的滤波器;③掌握MATLAB实现非线性滤波器的方法和技术。 其他说明:文中提供了详细的MATLAB代码片段,帮助读者更好地理解和实现这些滤波器。此外,还讨论了数值稳定性问题和一些实用技巧,如Cholesky分解失败的处理方法。

    VMware-workstation-full-14.1.3-9474260

    VMware-workstation-full-14.1.3-9474260

    DeepSeek系列-提示词工程和落地场景.pdf

    DeepSeek系列-提示词工程和落地场景.pdf

    javaSE阶段面试题

    javaSE阶段面试题

    《综合布线施工技术》第5章-综合布线工程测试.ppt

    《综合布线施工技术》第5章-综合布线工程测试.ppt

    安川机器人NX100使用说明书.pdf

    安川机器人NX100使用说明书.pdf

    S7-1200 PLC改造M7120平面磨床电气控制系统:IO分配、梯形图设计及组态画面实现

    内容概要:本文详细介绍了将M7120型平面磨床的传统继电器控制系统升级为基于西门子S7-1200 PLC的自动化控制系统的过程。主要内容涵盖IO分配、梯形图设计和组态画面实现。通过合理的IO分配,确保了系统的可靠性和可维护性;梯形图设计实现了主控制逻辑、砂轮升降控制和报警逻辑等功能;组态画面则提供了友好的人机交互界面,便于操作和监控。此次改造显著提高了设备的自动化水平、运行效率和可靠性,降低了维护成本。 适合人群:从事工业自动化领域的工程师和技术人员,尤其是熟悉PLC编程和控制系统设计的专业人士。 使用场景及目标:适用于需要进行老旧设备升级改造的企业,旨在提高生产设备的自动化水平和可靠性,降低故障率和维护成本。具体应用场景包括但不限于金属加工行业中的平面磨床等设备的控制系统改造。 其他说明:文中还分享了一些实际调试中的经验和技巧,如急停逻辑的设计、信号抖动的处理方法等,有助于读者在类似项目中借鉴和应用。

    chromedriver-linux64-136.0.7103.48.zip

    chromedriver-linux64-136.0.7103.48.zip

    IMG_20250421_180507.jpg

    IMG_20250421_180507.jpg

    《网络营销策划实务》项目一-网络营销策划认知.ppt

    《网络营销策划实务》项目一-网络营销策划认知.ppt

    Lianantech_Security-Vulnerabil_1744433229.zip

    Lianantech_Security-Vulnerabil_1744433229

    MybatisCodeHelperNew2019.1-2023.1-3.4.1.zip

    MybatisCodeHelperNew2019.1-2023.1-3.4.1

    《Approaching(Almost)any machine learning problem》中文版第13章(最后一章)

    【深度学习部署】基于Docker的BERT模型训练与API服务部署:实现代码复用与模型共享

    火车票订票系统设计与实现(代码+数据库+LW)

    摘  要 传统办法管理信息首先需要花费的时间比较多,其次数据出错率比较高,而且对错误的数据进行更改也比较困难,最后,检索数据费事费力。因此,在计算机上安装火车票订票系统软件来发挥其高效地信息处理的作用,可以规范信息管理流程,让管理工作可以系统化和程序化,同时,火车票订票系统的有效运用可以帮助管理人员准确快速地处理信息。 火车票订票系统在对开发工具的选择上也很慎重,为了便于开发实现,选择的开发工具为Eclipse,选择的数据库工具为Mysql。以此搭建开发环境实现火车票订票系统的功能。其中管理员管理用户,新闻公告。 火车票订票系统是一款运用软件开发技术设计实现的应用系统,在信息处理上可以达到快速的目的,不管是针对数据添加,数据维护和统计,以及数据查询等处理要求,火车票订票系统都可以轻松应对。 关键词:火车票订票系统;SpringBoot框架,系统分析,数据库设计

    【ABB机器人】-00标准保养简介.pdf

    【ABB机器人】-00标准保养简介.pdf

    最新校园跑腿小程序源码 多校版本 多模块 适合跑腿 外卖 表白 二手 快递等校园服务.zip

    最新校园跑腿小程序源码 多校版本,多模块,适合跑腿,外卖,表白,二手,快递等校园服务 此版本为独立版本,不需要微擎 直接放入就可以 需要自己准备好后台的服务器,已认证的小程序,备案的域名!

Global site tag (gtag.js) - Google Analytics