当前位置: 首页 > >

数据结构小白学是怎么通过Java的HashMap学会红黑树的

发布时间:

数据结构小白是怎么通过Java的HashMap学会红黑树的(一)
啥是红黑树,为啥要用它?

从jdk1.7到jdk1.8中间,在HashMap中加了一个红黑树,为啥呢,有什么好处呢,这就要把jdk1.7和jdk1.8的HashMap的结构拿来对比一番。


1.jdk1.7中的HashMap数据结构

在jdk1.7中,HashMap是使用一个Entry来存储数据的,但是这个Entry是数组加链表结构,啥?数组还能和链表一起玩?请看图:

细心的你发现了,这个数组的长度只有8(这是我自己定的8,jdk不一定是8,举个例子而已),为啥数组只有8个空,就能存好多东西呢?


细心的你又发现了,诶?插入第四个值的时候,好像不对劲。它插在了第二个数的后面,可以看出是用链表存的,这是啥操作。而且为啥他就插在第二个数后面,而不是第一个呢,这个先放一放,我们先了解一个东西。


Java中会有一个哈希计算,比如第一个对象的哈希值为2300,用2300除以8余数为4,那么这个对象就会存在Entry[4]这个位置上,HashMap会创建一个个节点来存这些对象。第二个数也一样,除以8余数为2,放在Entry[2]的位置。这下知道Java的HashMap是怎么把对象放到一个Entry里了吧。


可Entry只有8个空,怎么能做到放很多很多的对象?


这时候就用到了链表,比如插入的第四个对象,他的哈希值2322除以8,余数为2,但是Entry[2]已经有了,咋办呢,这时候,在Entry[2]这个节点的后面,使用链表,放上这个新加入的对象,你可能会疑惑,咋就能给它整连在一起了,木事,上图:


Node{
Node Parent;
Node Son;
Object object;
Node(Object object){//这个一般是泛型做到传啥是啥,不多说,懂得都懂
this.object = object;//上一条注释不负责,不懂的可以去看看Java泛型
}
}

这下懂了吧
存第四个对象只要两行代码就搞定:


node.Son = new node(Object);//创建个新节点,赋给Entry[2]的儿子
node.Son.Parent = node;//爸爸认了儿子,儿子当然得*职

不知道你有木有考虑一下下,这种做法好吗。没考虑的现在考虑考虑


。。。。。。(其实我挺讨厌这种句号放一起的感觉)


聪明的你,肯定发现了一个问题,啊?没发现?木事,我来告诉你


如果一堆对象,他们的哈希值除以8,余数全是2呢
那岂不是Entry[2]后面托着好多子子孙孙。如果想找子孙后代中的某一个节点时,也会感觉很慢,很累,要一个一个往下遍历才能找到,小小的年纪承受了不该承受的重量


这时候,jdk1.8来啦,它带着红黑树走来啦!


2.jdk1.8中的HashMap数据结构

刚刚说了,jdk1.7的HashMap由数组+链表组成,jdk1.8的HashMap由数组+链表+红黑树组成。


其实很简单,jdk1.8的HashMap数组那部分和jdk1.7的存储方法一样,先数组,后链表,不同的地方是,这里的链表用了红黑树。


这时候就可以吹一波红黑树的厉害之处了,红黑树能大大降低普通链表查找的速度。当然因为其插入数据的速度还是不如链表,所以Java会设定一个数值,超过这个数值量的数据,才会启用红黑树,不然还是用普通链表。


懂点数据结构的都知道哈,树的查找速度可比一条直链快得多,为啥呢,我们先来看两张图,然后再来说一说红黑树

-----------------图1 第一颗树----------------------------------图2 第二棵树-------------


提问:这两棵树谁先能找到H?
(这是两课二叉查找树,红黑树基于二叉查找树,其特点是,左节点比爸爸节点小,右节点比爸爸节点大)


答:肯定第二颗啊,只要查三次


这时候我们来复*下树的数据结构,看图


Node{
Node Parent;
Node Left;
Node Right;
Object object;
Node(Object object){
this.object = object;
}
}

查询代码如下:


public Node find(Node node, hashCode){//该方法传入
// 根节点和要查数据的哈希值即可开始遍历查找
if(hashCode == node.hashCode){
return node;
}
else if(hashCode < node.hashCode){
return find(node.Left);//当被查找的哈希值小于当前节点的哈希值
// 再调用自己,并传入左节点
// 我调我自己----递归
}else{
return find(node.Right);
}
}

这样一看,是不是还真是右边的树找的快呢,这是因为右边的树比较*衡,就是左边和右边的节点差不多多。
红黑树就是一颗,你插入值,它能根据某种规则,更改树各个节点的位置,来使得这棵树,更加*衡,这样找某些数的时候就递归的次数就会减少。、


红黑树到底是啥,我们下一篇文章见



友情链接: year2525网 工作范文网 QS-ISP 138资料网 528200 工作范文网 baothai 表格模版