HashMap 存在的意义是什么?

我一直在思考一个问题: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 删除元素,数组会移动吗?

HashMap 存在的意义是什么?

: » HashMap 存在的意义是什么?

原创文章,作者:奋斗,如若转载,请注明出处:https://blog.ytso.com/251926.html

(0)
上一篇 2022年5月3日
下一篇 2022年5月3日

相关推荐

发表回复

登录后才能评论