编程知识 cdmana.com

算法和数据结构:面试高频:一文搞定HashMap的实现原理

1. 为什么需要理解HashMap?

2. 什么是哈希表?

2.1 哈希表性能

2.2 哈希表的数据结构

2.3 哈希冲突

3. hashmap的实现原理

3.1 hashmap数据结构

3.2 hashmap特点

3.3 Hashmap扩容

4. 什么是红黑树?

5. HashMap&Hashtable的区别?


1. 为什么需要理解HashMap的实现原理?

  • HashMap是Java语言中使用频率很高的一种数据结构。
  • HashMap是一种经典&集大成的数据结构,同时用到了数组+链表+哈希表+红黑树多种数据结构;

 

2. 什么是哈希表?

要真正理解HashMap的数据结构,必须先了解哈希表的基本概念。

2.1 哈希表性能

先谈性能,主流数据结构的性能对比:

  • 数组:采用一段连续的储存单元来储存数据。对于指定下标的查找,时间复杂度为O(1),通过给定值进行查找,我们需要遍历数组,所以时间复杂度为O(n),对于一般的插入删除操作,因为数组元素要进行移动,所以时间复杂度也为O(n)。
  • 线性链表:对于链表的新增,删除等操作,因为链表的特殊性,仅需处理节点引用,所以时间复杂度为O(1),而要进行查找操作需要遍历链表,复杂度为O(n)。
  • 二叉树:对于一科相对平衡的有序二叉树,对其进行插入,查找,删除等操作平均复杂度为O(logn)。</

版权声明
本文为[架构师训练营]所创,转载请带上原文链接,感谢
https://cbk419323.blog.csdn.net/article/details/109249677

Scroll to Top