生动形象的用大白话说一下什么是HashMap

1.HashMap的社会关系

生动形象的用大白话说一下什么是HashMap_第1张图片

HashMap的爸爸是AbstractMap,他的老师Cloneable教会了他如何复制,老师Serializable教会了他如何序列化,老师Map也是他爸爸的老师,教会了他们爷俩如何好好做一个Map。 

2.HashMap的自我介绍

再说下HashMap自己,我们先把他当成是一个key/value存储的容器吧,就像是下面这个寄存柜,一个人可以保存一样物品,多了会替换前面的。

门牌号就是Hash,你的身份证就是Key,里面的书包就是Value。

生动形象的用大白话说一下什么是HashMap_第2张图片

3.HashMap的作用

1.你把身份证和书包(Key-Value)给管理员(JVM),然后你就可以溜了。

2.管理员苦逼的先用Hash算法算你的身份证号,得到了一个柜门号,再把你的书包丢进去。

3.你玩完回来拿书包,把身份证号给管理员,管理员去算柜门号,然后打开柜门把书包给你。

时间复杂度只需要O(1),因为直接打开了目标柜门。

4.理想与现实

理想

生动形象的用大白话说一下什么是HashMap_第3张图片

现实

生动形象的用大白话说一下什么是HashMap_第4张图片

       事实上这个柜子不是给你个人服务的,而是给一大群人服务的。而且会有一些人刚好用Hash算法算出来的柜号子和你相同.....,这就出现了冲突,总不能把你的书包扔出去吧,也不能不让人家放吧......该怎么办呢?

5.如何解决冲突?(Hash冲突的解决)

       事实上关于解决Hash冲突的方法有很多,比如看看隔壁柜子是不是空的、看看隔壁第N个柜子是不是空的、一直翻柜子直到翻到空柜子等等。但目前来说,运用最多的还是链地址法(书包链)解决冲突,因为它可以最有效的利用数组(柜子)空间,并且可以将数组的查询优势和链表的增删改优势结合起来。

       也就是说,现在的储物柜,不再放书包啦,里面放一个卡片,卡片上记录了第一个书包的位置。而书包呢,彼此之间用绳子连起来,那么不管堆在那里,通过绳子总不会丢。OK,找到A书包,那么这一条绳上的蚂蚱,都是1号柜子的。

生动形象的用大白话说一下什么是HashMap_第5张图片

我:管理员给我书包,我的身份证号是123456。

管理员:好,我先Hash一下,哦哦,你的柜子号是8号。(打开8号柜子)我看看链头书包在哪,原来在第一个窗户下面。(顺着绳子一个一个看),123444不是,123455也不是,123456是,来给你书包。

不考虑书包拿出来的问题,这样就找到你存的书包了。

不过拿出来也没啥,先抓住你书包后面书包的绳子,然后让你书包前面书包的绳子帮绑到你后面的书包上就OK了。(删除链表节点,没人不会吧)

6.回头看一下放书包的流程(HashMap插入流程)

12:00 管理员把你的书包放到8号柜子里

12:30 管理员把张三的书包放到9号柜子里

(java 1.7版本)

13:00 管理员发现李四的书包也应该放到8号,于是他把李四的书包扔到了厕所门口,把你的书包用绳子绑到了李四书包后面。把8号柜子里板子上的字写成厕所门口。

......

15:30 王五的书包也要放到8号,管理员先把之前李四的书包绑到王五的书包后面,然后把王五的            书包放到了厕所门口窗台上。把8号柜子里板子上的字改成厕所门口窗户上。

(java 1.8版本)

13:00 管理员发现李四的书包也应该放到8号,于是他把李四的书包扔到了厕所门口,把你的书包挂到厕所墙上,李四书包绑在你书包后面。把8号柜子里板子上的字写成厕所墙上。

......

15:30 王五的书包也要放到8号,管理员先把王五的书包绑到李四的书包后面,然后把王五的            书包放到了厕所门口窗台上。

.....

16:00 你来拿书包

7.柜子的扩容以及多管理员下的问题(HashMap扩容和多线程问题)

OK,讨论回柜子(HashMap)

(1)HashMap是一种散列表,采用(数组 + 链表 + 红黑树)的存储结构;

(2)HashMap的默认初始容量为16(1<<4),默认装载因子为0.75f,容量总是2的n次方;

(3)HashMap扩容时每次容量变为原来的两倍;

(4)当桶的数量小于64时不会进行树化,只会扩容;

(5)当桶的数量大于64且单个桶中元素的数量大于8时,进行树化;

(6)当单个桶中元素数量小于6时,进行反树化;

(7)HashMap是非线程安全的容器;

(8)HashMap查找添加元素的时间复杂度都为O(1);

java 1.7版本的柜子如何扩容的?

1.无要求(无参数),一开始是空柜子,16格子,柜子的使用率超过0.75,拿来一个两倍大的柜子,重新计算hash值,再把之前柜子里的内容都迁移过去,头插法迁移,所以书包链的前后顺序会颠倒。

2.有要求(有参数),根据你的要求配置柜子大小,柜子的使用率。第一次使用初始化容量为你的要求最近的2的幂。

扩容条件:当前数据存储的数量(即size())大小必须大于等于阈值;当前加入的数据发生了hash冲突。柜子大于等于使用率了,下一个要放到新的空间里了。

java 1.8版本的柜子如何扩容的?

1.无要求(无参数),一开始是空柜子,0格子,使用一次立即变16格。柜子的使用率超过0.75,拿来一个两倍大的柜子,重新计算hash值,把之前柜子里的内容都迁移过去,尾插法迁移。

2.有要求(有参数),根据你的要求配置柜子大小,柜子的使用率。第一次使用初始化容量为你的要求最近的2的幂。(细小区别是,先把最近的2的幂给阈值,再把阈值给容量,再把阈值等于容量*加载因子)

扩容条件:当前数据存储的数量(即size())大小必须大于等于阈值;柜子大于等于使用率了。

多个管理员(多线程下的问题)

java 1.7死循环

甲乙两个管理员要做扩容

甲管理员先拿来了一个大柜子,然后先标记12345要放到新柜子里,然后再标记下一个是12346。这时候突然他拉肚子,就去厕所了。

乙管理员哪里知道甲已经做这么多了,乙就都给搬好了。因为是头插法,现在是12346后面是12345。

甲回来了,嘴里念叨着12345,他也不知道乙都搬完了,他就回来把头指针指向12345。他就查记录,12345,下一个是12346。OK,再做一步标记,然后开始搬。现在是12346,下一个是12345,好眼熟啊....,于是就把12346头插到12345前面了。然后再往后...12345头插到12346前面。

死循环了....

java 1.8死循环

这个是数组转红黑树时出现的问题,先不说了,你知道就好。

数据丢失

甲管理员要把书包放到8号空箱子,他要放还没放的时候突然拉肚子,回来的时候乙已经把另一个书包也是8号放好了。但是甲不知道,他还以为8号是空箱子,直接把里面的"垃圾"丢掉,把自己的放进去。(理解为覆盖吧)...

8.关于HashCode和Equals

Java里有个原则  相同对象——相同Hash

一旦违背了这个原则,就违背了一个人只能保存一样物品这个规矩,一个人用身份证号可以占用多个箱子,但是查询却只能查询到最先查到的。而且不允许重复的Set也会出现重复,Set失效。

所以这个原则不能被违背。

分两种情况讨论:

不同对象插入HashMap ——>小概率Hash相同  >equals判等,正常是不等,去链后面或去树后面但如果重写,使其相等,不同的对象间就会覆盖,对象丢失。

                                      ——>大概率Hash不同  放进不同的Hash桶里。

相同对象插入HashMap ——>Hash一定相同,不同就违反原则  >equals判等,正常是相等,覆盖或不变,这时equals重写了使其两者不相等 ,一个链上就会出现重复的值。Set失效,而且查询只能拿到最前面的。

所以,重写Equals一定要重写HashCode,一定要满足相同对象——相同Hash原则。而且先判断HashCode后判断Equals。否则效率太低,一个是直接判断数值,一个是可能要对比对象。最主要的是HashCode做的事和Equals不同,他承担了维护哈希表的任务。

9.挂书包的艺术(HashMap红黑树)

我真编不下去了,难不成让我说管理员吧挂书包用绳子搞了个树出来?

关于红黑树,看这个清晰理解红黑树的演变---红黑的含义_chen_zhang_yu的博客-CSDN博客

1.柜子容量大于64,单个桶中元素的数量大于8时,才会进行树化。

2.当单个桶中元素数量小于6时,进行反树化;

写在最后的话:拥抱孤独才能使人进步。

你可能感兴趣的