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)。</