仓酷云
标题:
了解下JAVA的Commons Collections进修条记(三)
[打印本页]
作者:
萌萌妈妈
时间:
2015-1-18 11:08
标题:
了解下JAVA的Commons Collections进修条记(三)
主要缺点就是:速度比较慢,没有C和C++快
这个Map类是基于红黑树构建的,每一个树节点有两个域,一个寄存节点的Key,一个寄存节点的Value,相称因而两棵红黑树,一棵是关于key的红黑树,一棵是关于Value的红黑树。
关于红黑树的具体先容,参考《C#与数据布局--树论--红黑树(RedBlackTree)》这篇文章。
publicfinalclassDoubleOrderedMapextendsAbstractMap
{
privateNode[]rootNode=newNode[]{null,null};//根节点
publicSetentrySetByValue()
{//按Value猎取Entry汇合
if(setOfEntries[VALUE]==null){
setOfEntries[VALUE]=newAbstractSet(){
publicIteratoriterator(){
returnnewDoubleOrderedMapIterator(VALUE){
protectedObjectdoGetNext(){
returnlastReturnedNode;
}
};
}
publicbooleancontains(Objecto){
if(!(oinstanceofMap.Entry)){
returnfalse;
}
Map.Entryentry=(Map.Entry)o;
Object key =entry.getKey();
Node node =lookup((Comparable)entry.getValue(),
VALUE);
return(node!=null)&&node.getData(KEY).equals(key);
}
publicbooleanremove(Objecto){
if(!(oinstanceofMap.Entry)){
returnfalse;
}
Map.Entryentry=(Map.Entry)o;
Object key =entry.getKey();
Node node =lookup((Comparable)entry.getValue(),
VALUE);
if((node!=null)&&node.getData(KEY).equals(key)){
doRedBlackDelete(node);
returntrue;
}
returnfalse;
}
publicintsize(){
returnDoubleOrderedMap.this.size();
}
publicvoidclear(){
DoubleOrderedMap.this.clear();
}
};
}
returnsetOfEntries[VALUE];
}
privateObjectdoRemove(finalComparableo,finalintindex)
{
Node node=lookup(o,index);//在红黑树中查找节点
Objectrval=null;
if(node!=null)
{
rval=node.getData(oppositeIndex(index));
doRedBlackDelete(node);//在红黑树中删除指定节点
}
returnrval;
}
privateObjectdoGet(finalComparableo,finalintindex)
{
checkNonNullComparable(o,index);//反省参数非空
Nodenode=lookup(o,index);//按Key或Value查找指定节点
return((node==null)?null:node.getData(oppositeIndex(index)));
}
privateNodelookup(finalComparabledata,finalintindex)
{
Noderval=null;
Nodenode=rootNode[index];//根节点
while(node!=null)
{
intcmp=compare(data,node.getData(index));//与以后节点对照
if(cmp==0)
{//找到了
rval=node;
break;
}else{//在左子树或右子树中寻觅
node=(cmp<0)
?node.getLeft(index)
:node.getRight(index);
}
}
returnrval;
}
privatestaticNodeleastNode(finalNodenode,finalintindex)
{//前往指定节点的最右子节点
Noderval=node;
if(rval!=null){
while(rval.getLeft(index)!=null){
rval=rval.getLeft(index);
}
}
returnrval;
}
privateNodenextGreater(finalNodenode,finalintindex)
{//前往下一个年夜于指定节点的节点
Noderval=null;
if(node==null){
rval=null;
}elseif(node.getRight(index)!=null)
{//右子树不为空,前往右子树最左子节点
rval=leastNode(node.getRight(index),index);
}
else
{//不休向上,只需仍旧是右子节点
Nodeparent=node.getParent(index);
Nodechild =node;
while((parent!=null)&&(child==parent.getRight(index))){
child =parent;
parent=parent.getParent(index);
}
rval=parent;
}
returnrval;
}
privatevoidrotateLeft(finalNodenode,finalintindex)
{//左旋操纵
NoderightChild=node.getRight(index);
node.setRight(rightChild.getLeft(index),index);
if(rightChild.getLeft(index)!=null){
rightChild.getLeft(index).setParent(node,index);
}
rightChild.setParent(node.getParent(index),index);
if(node.getParent(index)==null)
{//设置为根节点
rootNode[index]=rightChild;
}elseif(node.getParent(index).getLeft(index)==node){
node.getParent(index).setLeft(rightChild,index);
}else{
node.getParent(index).setRight(rightChild,index);
}
rightChild.setLeft(node,index);
node.setParent(rightChild,index);
}
privatevoidrotateRight(finalNodenode,finalintindex)
{//右旋操纵
NodeleftChild=node.getLeft(index);
node.setLeft(leftChild.getRight(index),index);
if(leftChild.getRight(index)!=null){
leftChild.getRight(index).setParent(node,index);
}
leftChild.setParent(node.getParent(index),index);
if(node.getParent(index)==null)
{//设置为根节点
rootNode[index]=leftChild;
}elseif(node.getParent(index).getRight(index)==node){
node.getParent(index).setRight(leftChild,index);
}else{
node.getParent(index).setLeft(leftChild,index);
}
leftChild.setRight(node,index);
node.setParent(leftChild,index);
}
privatevoiddoRedBlackInsert(finalNodeinsertedNode,finalintindex)
{//举行红黑树节点拔出后的调剂
NodecurrentNode=insertedNode;//新拔出节点置为以后节点
makeRed(currentNode,index);//标志新节点为白色
while((currentNode!=null)&&(currentNode!=rootNode[index])&&(isRed(currentNode.getParent(index),index)))
{//确保以后节点父节点为白色才持续处置
if(isLeftChild(getParent(currentNode,index),index))
{//父节点是祖父节点的左孩子
Nodey=getRightChild(getGrandParent(currentNode,index),index);//叔节点是祖父节点的右孩子
if(isRed(y,index))
{//红叔()
makeBlack(getParent(currentNode,index),index);//标志父节点为玄色
makeBlack(y,index);//标志叔节点为玄色
makeRed(getGrandParent(currentNode,index),index);//标志祖父节点为白色
currentNode=getGrandParent(currentNode,index);//置祖父节点为以后节点
}
else
{//黑叔(对应和)
if(isRightChild(currentNode,index))
{//以后节点是父节点的右孩子()
currentNode=getParent(currentNode,index);//置父节点为以后节点
rotateLeft(currentNode,index);//左旋
}
makeBlack(getParent(currentNode,index),index);//以后节点的父节点置为玄色
makeRed(getGrandParent(currentNode,index),index);//祖父节点置为白色
if(getGrandParent(currentNode,index)!=null)
{//对祖父节点举行右旋
rotateRight(getGrandParent(currentNode,index),index);
}
}
}else
{//父节点是祖父节点的右孩子
Nodey=getLeftChild(getGrandParent(currentNode,index),index);//叔节点是祖父节点的左孩子
if(isRed(y,index))
{//红叔()
makeBlack(getParent(currentNode,index),index);//标志父节点为玄色
makeBlack(y,index);//标志叔节点为玄色
makeRed(getGrandParent(currentNode,index),index);//标志祖父节点为白色
currentNode=getGrandParent(currentNode,index);//置祖父节点为以后节点
}
else
{//黑叔(对应和)
if(isLeftChild(currentNode,index))
{//以后节点是父节点的左孩子()
currentNode=getParent(currentNode,index);//置父节点为以后节点
rotateRight(currentNode,index);//右旋
}
makeBlack(getParent(currentNode,index),index);//以后节点的父节点置为玄色
makeRed(getGrandParent(currentNode,index),index);//祖父节点置为白色
if(getGrandParent(currentNode,index)!=null)
{//对祖父节点举行左旋
rotateLeft(getGrandParent(currentNode,index),index);
}
}
}
}
makeBlack(rootNode[index],index);//标志根节点为玄色
}
privatevoiddoRedBlackDelete(finalNodedeletedNode)
{//在红黑树中删除指定节点
for(intindex=FIRST_INDEX;index<NUMBER_OF_INDICES;index++){
//ifdeletednodehasbothleftandchildren,swapwith
//thenextgreaternode
if((deletedNode.getLeft(index)!=null)
&&(deletedNode.getRight(index)!=null)){
swapPosition(nextGreater(deletedNode,index),deletedNode,
index);
}
Nodereplacement=((deletedNode.getLeft(index)!=null)
?deletedNode.getLeft(index)
:deletedNode.getRight(index));
if(replacement!=null){
replacement.setParent(deletedNode.getParent(index),index);
if(deletedNode.getParent(index)==null){
rootNode[index]=replacement;
}elseif(deletedNode
==deletedNode.getParent(index).getLeft(index)){
deletedNode.getParent(index).setLeft(replacement,index);
}else{
deletedNode.getParent(index).setRight(replacement,index);
}
deletedNode.setLeft(null,index);
deletedNode.setRight(null,index);
deletedNode.setParent(null,index);
if(isBlack(deletedNode,index)){
doRedBlackDeleteFixup(replacement,index);
}
}else{
//replacementisnull
if(deletedNode.getParent(index)==null){
//emptytree
rootNode[index]=null;
}else{
//deletednodehadnochildren
if(isBlack(deletedNode,index)){
doRedBlackDeleteFixup(deletedNode,index);
}
if(deletedNode.getParent(index)!=null){
if(deletedNode
==deletedNode.getParent(index)
.getLeft(index)){
deletedNode.getParent(index).setLeft(null,index);
}else{
deletedNode.getParent(index).setRight(null,
index);
}
deletedNode.setParent(null,index);
}
}
}
}
shrink();
}
privatevoiddoRedBlackDeleteFixup(finalNodereplacementNode,
finalintindex){
<p>
首先java功能强大的背后是其复杂性,就拿web来说,当今流行的框架有很多,什么struts,spring,jQuery等等,而这无疑增加了java的复杂性。
作者:
蒙在股里
时间:
2015-1-20 14:57
接着就是EJB了,EJB就是Enterprise JavaBean, 看名字好象它是Javabean,可是它和Javabean还是有区别的。它是一个体系结构,你可以搭建更安全、更稳定的企业应用。它的大量代码已由中间件(也就是我们常听到的 Weblogic,Websphere这些J2EE服务器)完成了,所以我们要做的程序代码量很少,大部分工作都在设计和配置中间件上。
作者:
小女巫
时间:
2015-1-27 18:53
Java自面世后就非常流行,发展迅速,对C++语言形成了有力冲击。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于个人PC、数据中心、游戏控制台
作者:
乐观
时间:
2015-2-5 08:51
Java 编程语言的风格十分接近C、C++语言。
作者:
若相依
时间:
2015-2-11 08:13
另外编写和运行Java程序需要JDK(包括JRE),在sun的官方网站上有下载,thinking in java第三版用的JDK版本是1.4,现在流行的版本1.5(sun称作J2SE 5.0,汗),不过听说Bruce的TIJ第四版国外已经出来了,是专门为J2SE 5.0而写的。
作者:
爱飞
时间:
2015-3-2 01:03
那么我书也看了,程序也做了,别人问我的问题我都能解决了,是不是就成为高手了呢?当然没那么简单,这只是万里长征走完了第一步。不信?那你出去接一个项目,你知道怎么下手吗,你知道怎么设计吗,你知道怎么组织人员进行开发吗?你现在脑子里除了一些散乱的代码之外,可能再没有别的东西了吧!
作者:
仓酷云
时间:
2015-3-11 01:20
另外编写和运行Java程序需要JDK(包括JRE),在sun的官方网站上有下载,thinking in java第三版用的JDK版本是1.4,现在流行的版本1.5(sun称作J2SE 5.0,汗),不过听说Bruce的TIJ第四版国外已经出来了,是专门为J2SE 5.0而写的。
作者:
不帅
时间:
2015-3-17 17:41
还好,SUN提供了Javabean可以把你的JSP中的 Java代码封装起来,便于调用也便于重用。
作者:
透明
时间:
2015-3-24 15:41
Java 不同于一般的编译执行计算机语言和解释执行计算机语言。它首先将源代码编译成二进制字节码(bytecode),然后依赖各种不同平台上的虚拟机来解释执行字节码。从而实现了“一次编译、到处执行”的跨平台特性。
欢迎光临 仓酷云 (http://ckuyun.com/)
Powered by Discuz! X3.2