文档章节

一,撸基础篇系列,JAVA的那些数据结构应用

爱吃大肉包
 爱吃大肉包
发布于 2017/02/23 18:09
字数 1134
阅读 46
收藏 1

 

到目前接触到的

有几个说明:

 

可扩容数组

ArrayList 扩容数组的实现, 满了后扩容,扩容在1.5倍,通过copy过来,无扩容因子

      int newCapacity = oldCapacity + (oldCapacity >> 1);
     // minCapacity is usually close to size, so this is a win:
     elementData = Arrays.copyOf(elementData, newCapacity);

 

 

 

stack栈的实现 ,基于数组继承自Vector(故线程安全):

获取peek():get(len-1)

出栈 pop(): 从数组最大坐标开始取出,peek(len-1) , 然后remove

入栈 push(o) : add(o)

 

 

 

队列

阻塞队列的实现:

基于数组和单向链表

获取:peek(),

实现:重入锁保证线程安全,peek(),从顶部获取

 

阻塞入队:put(o),

实现: 重入锁保证线程安全,通过Condition阻塞,无超时,支持Interrupt

 

带超时阻塞入队: offer(o,timeout, tmeUnit), 

实现: 重入锁保证线程安全,通过Condition阻塞,condition方法,awaitNanos(纳秒),支持Interrupt

 

其它注意点

当前数组的大小: AtomicInteger计算,用CAS保证同步,记得ReentrantLock必须是全局变量,局部的话,每次锁的对象是this.

 

非阻塞并发队列

单向 ConcurrentLinkedQueue

ConcurrentLinkedQueue的size有个小坑, 为了offer时的速度,并没有存储个当前队列的大小。 故调用concurrentLinkedQueue.size()时就坑了,只能去遍历整个列

 

数组链表

数组链表的扩容实现:

以HashMap为例子:

 

扩容过程

扩容前
[ 1 ] [ 2 ] [ 3 ] [ 空]
  5     10

第一个线程扩容后,数组链表如下

[ 1 ] [ 10 ] [3] [] [] [] []
          2

第二个线程又把从头把2指向10,然后2和10形成了个死循环

 

扩容代码

//对HashMap死链理解的注解 . 2017.02.17 by 何锦彬 JDK,1.7.51

void transfer(Entry[] newTable, boolean rehash) {
         //获取新table的容量
        int newCapacity = newTable.length;
        //迭代以前的数组
        for (Entry<K,V> e : table) {
            //如果数组上有元素
            while(null != e) {
                // 赋值next
                Entry<K,V> next = e.next;
                //获取e在新的table里的位置
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                //把e指向当前的新数组里的第一个元素,这里会并发了,如果在这断点等待下个线程过来,就会死循环,尝试下
                e.next = newTable[i];
                //替代新数组的位置
                newTable[i] = e;
                e = next;
            }
        }
    }

 

 

红黑树:

红黑树的实现,TreeMap举例,

//对treeMap的红黑树理解注解. 2017.02.16 by 何锦彬  JDK,1.7.51<br>  <br>/** From CLR */
    private void fixAfterInsertion(Entry<K, V> x) {
 
         
         
        //新加入红黑树的默认节点就是红色
        x.color = RED;
        /**
         * 1. 如为根节点直接跳出
         */
        while (x != null && x != root && x.parent.color == RED) {
            
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                 
                //如果X的父节点(P)是其父节点的父节点(G)的左节点 
                //即 下面这种情况
                /**
                 *                         G
                 *               P(RED)              U
                 */              
                //获取其叔(U)节点
                Entry<K, V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    // 这种情况,对应下面 图:情况一
                    /**
                     *                         G
                     *               P(RED)              U(RED)
                     *          X
                     */
                    //如果叔节点是红色的(父节点有判断是红色). 即是双红色,比较好办,通过改变颜色就行. 把P和U都设置成黑色然后,X加到P节点。 G节点当作新加入节点继续迭代
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    //处理红父,黑叔的情况
                    if (x == rightOf(parentOf(x))) {
                        // 这种情况,对应下面 图:情况二
                        /**
                         *                           G
                         *            P(RED)                        U(BLACK)
                         *                     X
                         */
                        //如果X是右边节点
                        x = parentOf(x);
                        // 进行左旋
                        rotateLeft(x);
                    }
                    //左旋后,是这种情况了,对应下面 图:情况三
                    /**
                     *                           G
                     *            P(RED)                        U(BLACK)
                     *      X
                     */
                     
                    // 到这,X只能是左节点了,而且P是红色,U是黑色的情况
                    //把P改成黑色,G改成红色,以G为节点进行右旋
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));
                }
            } else {
                //父节点在右边的
                /**
                 *                         G
                 *                 U               P(RED)
                 */              
                //获取U
                Entry<K, V> y = leftOf(parentOf(parentOf(x)));
                 
                if (colorOf(y) == RED) {
                    //红父红叔的情况
                    /**
                     *                          G
                     *             U(RED)               P(RED)
                     */    
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    //把G当作新插入的节点继续进行迭代
                    x = parentOf(parentOf(x));
                } else {
                    //红父黑叔,并且是右父的情况
                    /**
                     *                          G
                     *             U(RED)               P(RED)
                     */    
                    if (x == leftOf(parentOf(x))) {
                    //如果插入的X是左节点
                     /**
                        *                            G
                        *            U(BLACK)                        P(RED)
                        *                                       X              
                        */
                        x = parentOf(x);
                        //以P为节点进行右旋
                        rotateRight(x);
                    }
                    //右旋后
                    /**
                     *                            G
                     *            U(BLACK)                        P(RED)
                     *                                                        X
                     */
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    //以G为节点进行左旋
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        //红黑树的根节点始终是黑色
        root.color = BLACK;
    }

 

其实就是一颗2-3-4树变种

见我另一篇博客 JAVA中的数据结构 - 真正的去理解红黑树

 

环链表+SET,如redis的HashedWheelTimer

 

 

 

 

 

© 著作权归作者所有

爱吃大肉包

爱吃大肉包

粉丝 64
博文 40
码字总数 37046
作品 0
广州
程序员
私信 提问
泥沙砖瓦浆木匠/java-core-learning-example

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

泥沙砖瓦浆木匠
04/02
0
0
《成神之路-基础篇》JVM——JVM内存结构(已完结)

Java内存模型,Java内存管理,Java堆和栈,垃圾回收 本文是《成神之路系列文章》的第一篇,主要是关于JVM的一些介绍。 持续更新中 参考文章: Java虚拟机的内存组成以及堆内存介绍 Java堆和栈...

2018/05/05
0
0
Java 10大优点—Part4—Java内存模型

在忙着参加在爱沙尼亚进行的 TEDx talk 演讲活动以及在比利时举办的一届非常忙碌的Devoxx 会议的间隙,我将继续推进 Java’s Rocking 的系列博文。 对还没有接触过这个系列博文的读者,不妨先...

foxlee
2013/12/09
422
1
JVM 性能优化, Part 4: C4 垃圾回收

ImportNew注:本文是JVM性能优化 系列-第4篇。前3篇文章请参考文章结尾处的JVM优化系列文章。作为Eva Andreasson的JVM性能优化系列的第4篇,本文将对C4垃圾回收器进行介绍。使用C4垃圾回收器...

梁杰_Jack
2014/10/30
46
0
干货系列1:Java互联网网站开发工程师 的技术提高与晋升路线(技术专精)

前几天写了自己对于Java软件开发工程师职业发展规划方面的一些感悟,陆续收到一些反馈,希望我能再就Java工程师不同的开发(职责)方向谈谈职业发展问题。(上一篇:Java软件开发工程师的自我...

半饱即好
2018/06/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

UAVStack功能上新:新增JVM监控分析工具

UAVStack推出的JVM监控分析工具提供基于页面的展现方式,以图形化的方式展示采集到的监控数据;同时提供JVM基本参数获取、内存dump、线程分析、内存分配采样和热点方法分析等功能。 引言 作为...

宜信技术学院
6分钟前
1
0
MySQL的5种时间类型的比较

日期时间类型 占用空间 日期格式 最小值 最大值 零值表示 DATETIME 8 bytes YYYY-MM-DD HH:MM:SS 1000-01-01 00:00:00 9999-12-31 23:59:59 0000-00-00 00:00:00 TIMESTAMP 4 bytes YYYY-MM......

物种起源-达尔文
13分钟前
3
0
云服务OpenAPI的7大挑战,架构师如何应对?

阿里妹导读:API 是模块或者子系统之间交互的接口定义。好的系统架构离不开好的 API 设计,而一个设计不够完善的 API 则注定会导致系统的后续发展和维护非常困难。比较好的API设计样板可以参...

阿里云官方博客
17分钟前
1
0
Rancher + VMware PKS实现全球数百站点的边缘K8S集群管理

Sovereign Systems是一家成立于2007年的技术咨询公司,帮助客户将传统数据中心技术和应用程序转换为更高效的、基于云的技术平台,以更好地应对业务挑战。曾连续3年提名CRN,并且在2012年到2...

RancherLabs
21分钟前
2
0
6、根据坐标,判断该坐标是否在地图区域范围内

最近在写配送区域相关的代码,具体需求如下: 根据腾讯地图划分配送区域,总站下边设多个配送分站,然后将订单中的收货地址将其分配给不同的配送分站。 1、地图区域划分(腾讯地图) 1.1、H...

有一个小阿飞
23分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部