我眼中的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举例,加入自己的注释的理解:
//对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的扩容条件是有问题了,应该加入是否有红黑树的判断
最新文章
- 【转】NSArray排序方法
- C#网页自动登录和提交POST信息的多种方法(转)
- Android之使用SharedPreferences保存用户偏好参数
- MSSQL查询连接数
- 一起来看看css中的单位
- Chapter 10 模版方法模式
- Python数据分析numpy库
- 使用VMware安装Ubuntu虚拟机,创建后开启显示黑屏的解决方法
- Entity Framework入门教程(8)---预先加载、延迟加载、显示加载
- Excel 恢复默认行高、列宽
- 用jieba库统计文本词频及云词图的生成
- libnids校验和引起回放包不能正常捕捉
- Python中_,__,__xx__的区别
- 简单代码生成csv文件(excel)
- FTP主动模式与被动模式,及java FTPClient模式设置
- 作为phper既然了解共享内存函数shmop的使用方法,那么就必须要了解一下信号量是什么,以及信号量使用的代码案例
- WPF DataGrid多表头/列头,多行头,合并单元格,一列占据多行
- Flink窗口介绍及应用
- 【转载】centos7.3 防火墙配置
- Juno 版 Keystone 主配置文件 keystone.conf 详解