java容器HashMap原理

时间:2021-10-16 10:25:06

1、为什么需要HashMap

前面我们说了ArrayList和LinkedList,它们对容器内的对象都能实现增、删、改、查、遍历等操作,

并且对应不同的情况,我们可以选择不同的List,用以提高效率。从功能上来说,这个容器已经设计得很好了,

为什么我们还要HashMap呢?接下来,让我们细细地分析:

在程序中,我们最常用的动作就是存数据和取数据,存数据就是把数据存起来(包括插入数据和增加数据),

取数据就是找到我们存进去的数据(查找数据),下面从这两个方面来分析一下ArrayList和LinkedList的问题。

  • ArrayList在增加数据和按下标获取数据效率高。
  • LinkedList在插入数据和删除数据方面效率比较高。

提出问题:能不能有一种容器能在它存数据的时候很快,查找数据的时候也很快呢?

新的需求:事物之间都是有关联的。ArrayList是靠下标来关联数据的,这种关联太单一了,

无法完美的适应OO编程环境,面向对象编程就是要把世间万物都用对象包装起来,

我们把这些对象都只与数字(0、1、2)关联起来,也太单调了,也太没有颜色了。

世间是多彩的,基于这种情况,我们就提出:

能不能使其他的事物也与我们的对象关联起来呢?(比如说,我们用汽车牌号码关联汽车,用身份证号码关联人)

当然同时满足上面提出的条件(能不能有一种容器能在它存数据的时候很快,查找数据的时候也很快呢?),

那就非常完美了。

程序袁的回答:是的,我们能过设计出这种容器,他将马上风靡全球。

2、HashMap实现原理

先看看下面这两张图

java容器HashMap原理java容器HashMap原理

表1这是HashMap的两种存储模式表二

下面解释这两种表存储对象的原理

首先理解两个概念:

  • hashcode(散列码):现在只需要知道hashcode是返回一个整数。

后面会单独用一章具体解析hashcoed和equal的问题,以及怎么写hashcode和equal的。

  • equal(相等):现在只需要知道equal在两个逻辑上面相等的对象的时候返回true,

例如:new student(1,"aa");和new student(1,"aa")是两个相等的对象,如果用object里面的equal来判断

这两个对象结果是不相等的。

存储数据的分析:

现在有以下几个对象:

a=newnew student(1,"aa"); b=new
student(4,"aa");

c=new
student(2,"aa");d=new student(1,"aa")

现在假设a对象的hashcode是5,b的hashcode是17,假设 c的hashcode是10,,

因为一些规则的原因(在hashcode这一章会重点解析),d的hashcode必须是5;接下来我们就对

这些数据进行存储。先对表一进行存储:int index=hashcode()%12--------这个12是值这个表的大小。

先存a,那么a对象放在5这个位置,接下来存b,此时经过int
index=hashcode()%12,

也会存储到5这个位置,但是此时此刻,5这个位置已经有数据了,,接下来判断这个a对象

跟b对象是否相等,现在是不想等,那我们就把这个b对象放到右边这个非常小的格子里面的第一个格子,

接下来存储c对象,把c放在10这个地方,再接下来存储d,经过计算吗,d会存储到5这个位置,

但是此时此刻,5这个位置已经有数据了,接下来判断这个a对象跟b对象是否相等,现在是相等,

那我们就把d这个对象替换掉原来a的对象。

存储结果如下图:

java容器HashMap原理java容器HashMap原理

注意5这个位置的元素的替换

接下来对表二的存储方式进行分析:公式也是一样的int index=hashcode()%12,先存a,那么a对象放在5这个位置,

接下来存b,此时经过int index=hashcode()%12,也会存储到5这个位置,但是此时此刻,

5这个位置已经有数据了,接下来判断这个a对象跟b对象是否相等,现在是不想等,

那我们就把这个b对象放在5这个位置接在a的对象后面,接下来存储c对象,把c放在10这个地方,

再接下来存储d,经过计算吗,d会存储到5这个位置,但是此时此刻,5这个位置已经有数据了,

接下来是遍历5这一条链路的数据,看看是否有相等的对象,现在找到a这个对象是相等的,

那我们就把d这个对象替换掉原来a的对象。存储结果如下图。

java容器HashMap原理java容器HashMap原理

注意5这个位置a和d的替换

查找数据的分析:

以上是存储对象时的分析,接下来是查找对象的分析,(以下分析是针对表一进行分析的)现在我要查找三个对象,

x=newnew
student(1,"aa"), y=newnew student(3,"aa"),z=new
student(4,"aa"),

由相等的对象必须有相同的hashcode这个条件的限制(先不管为什么有这个霸道的条件,后面会解析),

我们可知x的hashcode的为5,z的hashcode为17,y的hashcode我们就随便取一个,假设为10,

(为什么不同的对象会有相同的hashcode?这样行吗?合理吗?后面会解析)。接下来我们就来查找对象了。

先查找x,经过int
index=hashcode()%12计算,是第5格,此时有数据,接下来判断这两个对象是否相等,

此时相等,那么我们就找到了这个对象。接下来查找y,经过int
index=hashcode()%12计算是第10个,

此时有数据,接下来判断这两个对象是否相等,此时不相等,然后就到右边那个

非常小的格子里面一个一个的判断是否相等,我们遍历一遍后,发现没有相等的,此时我们得出结论,没有这个数据,

再接下来找z,经过int
index=hashcode()%12计算是第10个,此时有数据,接下来判断这两个对象是否相等,此时不相等,

然后就到右边那个非常小的格子里面一个一个的判断是否相等,在遍历的时候,

我们发现第一个就是相等的,那我们就找到了这个数据。

3、总结HashMap的主要特点

    • 如果我们不知道下标,相比ArrayList和LinkedList,hashMap有具有非常快的查找能力
    • hashMap不仅能够形成键值对,这个是一个非常好的关系