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)。
- 哈希表：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能非常高，在不考虑哈希冲突下，仅需一次定位就能完成，时间复杂度为O(1)。
2.2 哈希表的数据结构
哈希表
- 数据结构的物理储存结构只有两种：顺序储存结构和链式储存结构；
- 顺序储存：在内存中按照顺序分配内存空间，比如数组；
- 链式储存：在内存中无序存放，但是一个Node中存储着下一个Node内存地址，比如链表。
- 哈希表同时使用了这两种结构的特性（数组+链表）。
2.3 哈希冲突（散列码冲突）
- 当我们的关键字通过哈希函数计算后得到结果相同时，即发生了哈希冲突。
- 我们不能保证哈希冲突一定不会发生，越是优秀的哈希函数，越能够计算简单并且散列地址均匀。
- 面对哈希冲突，有多种解决方案：开放定址法，再散列法，链地址法，而Java中的HashMap则使用的是链地址法。
3.HashMap的实现原理
3.1 hashmap数据结构
要了解hashmap首先要弄清楚他的结构。在java编程语言中最基本的数据结构有两种，数组和链表。
数组：查询速度快，可以根据索引查询；但插入和删除比较困难；
链表：查询速度慢，需要遍历整个链表，但插入和删除操作比较容易。
hashmap是数组和链表组成的，数据结构中又叫“链表散列”。
如涉及版权问题，请私信联系处理。
3.2 hashmap特点
- 快速存储 ：比如当我们对hashmap进行get和put的时候速度非常快；
- 快速查找（时间复杂度o(1)）当我们通过key去get一个value的时候时间复杂度非常的低，效率非常高；
- 可伸缩：1数组扩容，边长。2，单线列表如果长度超过8的话会变成红黑树（JDK1.8）。
3.3 Hashmap扩容
扩容的触发条件：
- 数组扩容：数组存储比例达到75% – 0.75（阈值）时，数组长度变成2倍 0.75；
- 链表转换为红黑树：当单线链表达到一定长度后效率会非常低，那么在jdk1.8以后的话，加入了红黑树，链表长度>8时，就会变成一个红黑树。
4. 什么是红黑树？
- 红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
- 它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
红黑树
红黑树特点：
- 性质1. 节点是红色或黑色。
- 性质2. 根节点是黑色。
- 性质3 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
5. HashMap&Hashtable的区别？
相同点：
- 实现原理相同，功能相同，底层都是哈希表结构，查询速度快，在很多情况下可以互用。
不同点：
- JDK引入版本：Hashtable是早期提供的接口，HashMap是新版JDK1.2提供的接口。
- 父类不同：Hashtable继承Dictionary类，HashMap实现Map接口。
- 线程安全性：Hashtable线程安全，HashMap线程非安全。
- null值问题：Hashtable不允许null值，HashMap允许null值。
- 遍历方式不同：HashMap都使用了Iterator，而由于历史原因，Hashtable还使用了Enumeration的方式 。
现在Hashtable基本上已经被弃用，非线程安全使用HashMap，需线程安全使用ConcurrentHashMap。