数据结构 -- 数组+链表 HashMap

时间:2023-02-16 00:16:33

主要讲HashMap, 好像还有一个叫HashTable来着。一个一个讲吧。

HashMap,首先我的思路就转到了Hash这种字眼上。HashCode,是一个常见的东西,可是这东西究竟要怎么用那?

HashMap图解--转载

HashMap的数据结构

先讲讲HashCode是个什么?先说是干嘛的把,目的就是为了找内存中的某段内存比较方便。我们都知道内存那么大的地方,存着那么多东西假设我们要找一个指定的对象啥的,一个一个找,这个也行得通哈,但是呢,太慢,又或者是有别的方法可以找的更快。hashCode 出现就是解决这个问题的。。一些学术的词我也不是特别懂。接下来谈谈到底是什么个办法,用上了hashcode,能加快查找速度。。

就举个例子吧,上学谈论某人的时候,,“哎?你知道娅娅梨吗?就5班的那个英语课代表,知道吗?”,和“哎?你知道娅娅梨吗?”这俩的区别,我想第一句话最能体现出hashcode的含义了。想想为什么要这么谈论?娅娅梨这个人可能学校都好几个都是同名,先不管,但是一提5班的话,,那么旁听者的脑子就立马锁定一个范围了,脑子里只在5班所有同学里找娅娅梨是谁!这样的话,立马就能锁定目标。但是如果只说第二句,效果是啥??全校2000多名学生,我哪知道你说的是谁?脑子都糊了,半天才想起来谁是娅娅梨!

以上的例子是hashcode思路的基本描述,上述的5班,这个含义实则就是HashCode的地位。那么回归一下,hashcode的真实含义和用途。。个人感觉是分类用的。。hashcode 实则是内存指针位置经过一系列算法得到的一个值,,假设内存中有10个内存点,,地址位置分别是 2, 3, 4, 5, 6, 7, 8, 9, 10; 那就将这几个元素用取模的方式计算得到一个所谓的hash值。当然,真实情况下要算的复杂的多哈:   就以4位模吧。  那么   2/4 = 0 余 2, hashcode是2,  3/4 = 0 余 3, hashcode是3, ,依次计算下来,大家的hashcode值分别为:  2,3,0,1,2,7,0,1,2

对比下来

数据结构 -- 数组+链表 HashMap

好了,这么算下来,你会发现,以上的元素似乎因为hashcode 值,被分为了4类:

数据结构 -- 数组+链表 HashMap

那如果这样的话,我们假设要找 3 在哪里,是不是不同从这9个数里面一个一个找,反而是算哈希值,找找它到底值那个班级的,这样直接在指定的班级找,这不就更快了,,这里3被分配到了3班,,里面只有俩学生,就是3 和 7。撑死查看俩,是不是快多了。这就是hashCode主要功能。

那么接下来步入正题,HashMap原理。HashMap,就是为快而快的数据结构。。这里不得不说到最基本的线性表结构,数组和链表。。数组呢,查找啥的挺快,但是一到插入删除,就麻烦了,涉及到一波调换位置,全体前移或者后移。所以插入删除有些吃力,尤其是插入删除到前面的。。 那链表呢,,可以说是很好的解决了插入删除要全体动元素这个问题,但是随之而来的就是查找吃力,不是像数组那样一个i[n]就能很快的得知地址在哪里。。他得顺藤摸瓜慢慢捋。。有些吃力。所谓鱼与熊掌不可兼得。。但是他俩要是组合一下呢?各取所优?于是hashMap就是取各自的优点。。数组不是查找的快吗?那我就让你充当班级的角色,,链表不是添加删除无压力吗?我就让你的每个单元充当学生。。每当一个学生入校的时候,我就根据这个学生的特质,算出来它应属于哪个班级,得出来一个班级号,就是hash,,然后我就把它加到hash指定的班里面,假设hash是3,那就分到三班。。然后学生到三班报道,总得有个座位吧,,然而这些座位相当于链表的结构,,用链表的那一套给他得出来位置就行了,其实就是加个指针。


如图:以16取模,分的位置。

数据结构 -- 数组+链表 HashMap

这样看来 HashMap实则也不是辣么神秘啦,反而还是挺有趣呢,数组和单向链表的结合体。

那咱们用的时候不是有key value 这一说吗?先上一个毁三观的图,告诉我不是只有我一个刚刚接触的时候是这么以为的:

数据结构 -- 数组+链表 HashMap

曾经的我知道map不是数组,脑海中的图像俨然是数组的样子。。够毁三观吧。。。请勿模仿。不过以后绝不会这么想啦。


其实key value 呢,是存在链表节点中的,,并且这个key,就是作为算hash值的关键人物。value呢就是咱们加入的数据没啥好说的。。在HashMap中,有不少地方根据key算出了hash值,然后根据这个值,来确定这个元素是属于 数组结构中哪个单元格格里面的,找到哪个格格里,,再对这个格格存的链表头顺藤摸瓜进行查找,添加,更改等工作,大概就是这么个思路。想上源码分析呢,但是目前比较紧没时间了。。看看链接中的帖子。写的非常好。哪里有分析。先撤。以后补。