JAVA的那些数据结构实现总结,实现,扩容说明

简介:

能沉淀下来的东西,往往都很基础,整理了下JAVA中遇到的数据结构

 

 

目录大纲:

 

 

 

 

 

到目前接触到的

有几个说明:

 

可扩容数组

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

 

 

可扩容的数组链表

数组链表的扩容实现:

以HashMap为例子, 当链表深度过长,或生产个新的数组链表进行copy

注意:

扩容过程中容易出现死链,下面是死链的个演示

扩容前
[ 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;
            }
        }
    }
复制代码

 

 

 

 

 

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.

 

 

 

红黑树:

红黑树的实现,TreeMap举例,加入自己的注释的理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
//对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树变种,红黑树详情可以看我上一篇

 

而且JDK8的hashMap链表后,链表的深度超过8也是转换成红黑树的存储,个人是认为转换成红黑树后,hashMap的扩容条件是有问题了,应该加入是否有红黑树的判断

 

相关文章
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
92 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
2月前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
50 1
|
2月前
|
存储 Java
告别混乱!用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中,随着项目复杂度增加,数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案,帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,有效提升了代码质量和维护性。
94 2
|
2月前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
72 2
|
8天前
|
存储 缓存 安全
Java 集合江湖:底层数据结构的大揭秘!
小米是一位热爱技术分享的程序员,本文详细解析了Java面试中常见的List、Set、Map的区别。不仅介绍了它们的基本特性和实现类,还深入探讨了各自的使用场景和面试技巧,帮助读者更好地理解和应对相关问题。
29 5
|
1月前
|
Java 索引 容器
Java ArrayList扩容的原理
Java 的 `ArrayList` 是基于数组实现的动态集合。初始时,`ArrayList` 底层创建一个空数组 `elementData`,并设置 `size` 为 0。当首次添加元素时,会调用 `grow` 方法将数组扩容至默认容量 10。之后每次添加元素时,如果当前数组已满,则会再次调用 `grow` 方法进行扩容。扩容规则为:首次扩容至 10,后续扩容至原数组长度的 1.5 倍或根据实际需求扩容。例如,当需要一次性添加 100 个元素时,会直接扩容至 110 而不是 15。
Java ArrayList扩容的原理
|
1月前
|
缓存 算法 Java
本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制
在现代软件开发中,性能优化至关重要。本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制。通过调整垃圾回收器参数、优化堆大小与布局、使用对象池和缓存技术,开发者可显著提升应用性能和稳定性。
48 6
|
1月前
|
存储 Java 索引
Java中的数据结构:ArrayList和LinkedList的比较
【10月更文挑战第28天】在Java编程世界中,数据结构是构建复杂程序的基石。本文将深入探讨两种常用的数据结构:ArrayList和LinkedList,通过直观的比喻和实例分析,揭示它们各自的优势与局限,帮助你在面对不同的编程挑战时做出明智的选择。
|
2月前
|
存储 算法 Java
Java 中常用的数据结构
【10月更文挑战第20天】这些数据结构在 Java 编程中都有着广泛的应用,掌握它们的特点和用法对于提高编程能力和解决实际问题非常重要。
33 6
|
2月前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
32 1
下一篇
DataWorks