HashMap 存在的意义是什么?

JAVA herman 730浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog,发送下载链接帮助你免费下载!
本博客日IP超过1800,PV 2600 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog,之前的微信号好友位已满,备注:返现
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

我一直在思考一个问题:HashMap 存在的意义是什么?也就是说 Java 为什么要设计 HashMap?我问了很多面试者以及很多 CSDN 的博客专家都没有找到想要的答案!于是我自己查了很多资料想找 HashMap 为什么需要这样设计?最终都没有结果!

没有结果你还写这篇文章干啥?虽然没有结果,但是我又重新看了一遍 HashMap 的源码,得出了一些结论。我想这可能就是 HashMap 设计的初衷,分享给大家!不正确的地方希望大家指出,我们共同进步!

HashMap 存在的意义是什么?

前面我讲过 ArrayList 和 LinkedList,还有 Vector。但是它们都又一些缺点,要么插入删除速度慢、要么就是遍历速度慢。那么有没有一种插入、删除、遍历都比较不错的集合类呢?

于是 HashMap 就出现了。HashMap 可以存储一组键值对的集合,并实现快速的查找。

  • 为了实现快速查找,HashMap 选择了数组而不是链表。以利用数组的索引实现 O(1) 复杂度的查找效率。
  • 为了利用索引查找,HashMap 引入 Hash 算法, 将 key 映射成数组下标: key -> Index。
  • 引入 Hash 算法又导致了 Hash 冲突。
  • 为了解决 Hash 冲突,HashMap 采用链地址法,在冲突位置转为使用链表存储。
  • 链表存储过多的节点又导致了在链表上节点的查找性能的恶化。
  • 为了优化查找性能,HashMap 在链表长度超过 8 之后转而将链表转变成红黑树,以将 O(n) 复杂度的查找效率提升至 O(log n)。

现在我们是不是可以得出一种结论。

HashMap 存在的意义就是实现一种快速的查找并且插入、删除性能都不错的一种 K/V(key/value)数据结构。

关于编程,我希望大家每天都有一些思考,这样能成长的更快!

最后我留一个小问题,HashMap 删除元素,数组会移动吗?

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加QQ1群:135430763(2000人群已满),QQ2群:454796847(已满),QQ3群:187424846(已满)。QQ群进群密码:xttblog,想加微信群的朋友,之前的微信号好友已满,请加博主新的微信号:xttblog,备注:“xttblog”,添加博主微信拉你进群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作可添加助理微信进行沟通!

本文原文出处:业余草: » HashMap 存在的意义是什么?