一、概念
HashMap又叫哈希表、散列表，是一种以键值对方式存储数据的数据结构，它利用不重复、无序的键实现了快速查找。JDK1.8版本之前:HashMap的底层数据结构为数组+链表，JDK1.8版本之后:HashMap的底层数据结构为数组+链表+二叉树(红黑树)。数组+链表的含义指的是：每个数组的位置上的对象，是一个链表结构存储(换句话说，这样的方式就可以在数组的每个位置中存储多个对象)。
屏幕快照 2019-10-29 下午2.13.20.png
二、原理结构
屏幕快照 2019-10-29 下午2.16.50.png
三、重要特性
- HashMap在第一次put时，才进行初始化。put对象的过程: 求key对象的hash值，再通过哈希表数组的最大下标值&hash值（值永远<=下标值） 得出的结果，来作为哈希表数组的下标位置，这个位置就是对象存储的位置取值的原理与存储的原理一致，也是通过求hash值来确定哈希表的位置，如果此位置上有链表对象，那么需要遍历链表。
- 当容量到达75%的阀值后，进行扩容，扩容的算法是 oldCap<<1,表示*2，扩容了之后，那么需要把原哈希表中的数据，重新计算哈希值存储到新的哈希表中，重新扩容之后，原来的对象位置不保正有序。
- 对象的hashCode方法，是 Object类中定义的，就是用来给哈希表使用的,本身是一个本地方法，使用C/C++来实现，同一个对象多次调用hashCode方法，应该返回相同的int值（HashCode值)，但是重写了hashCode方法后可能返回不同的值。如果相同对象KEY的hashCode值不同，那么在Hash表中存储的对象就无法取出，又不会被垃圾收集器回收，此种情况称为内存泄露，内存泄露过多，就是会发生内存溢出；
- JDK 1.8版本之后: 改进的原因：如果数组中同一个位置的链表过长，那么会影响查询遍历的性能（因为链表不适合遍历)；转化成红黑树的条件，是 KEY 值的总数大于64时，在扩容时，当哈希表中数组同一个位置中的链表长度大于8时（阀值），那么会把链表转换成红黑树，来提高查询效率。在扩容时，当哈希表中数组同一个位置中的红黑树长度小于6时（阀值），那么会把红黑树转换成链表。在阀值6和8之间留个7的原因是为了防止链表和红黑树来回的转换，影响性能。
- 红黑树是在均衡二叉树上扩展, 其特点: 每个节点非红即黑。根节点总是黑色的。如果节点是红色的，则它的子节点必须是黑色的(反之不一定)。每个叶子节点都是黑色的空节点(NIL 节点)。从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点(即相同的黑色高度)。
- 缺点: 线程不安全。避免哈希表频繁散列（rehash），重新rehash会消耗性能。new HashMap(initialCapacity); 通过设置合理的初始容量。
优点: 取值快，优其在数据量越大表现越明显。HashMap 的结构通过会被用来设计缓存、框架底层的数据结构。
具体代码
https://github.com/JacksonMike/Java_ultimate/blob/master/HashMapDemo.java
四、常见面试题
- 为什么要用HashMap？
- HashMap的工作原理是什么?
- 有什么地方可以减少碰撞 ？
- HashMap中的hash函数是如何实现的 ？
- 拉链法导致链表过深问题为什么不用二叉查找树代替，而是选择使用红黑树，为什么不一直使用红黑树？
- 说说你对红黑树的理解？
- 解决hash碰撞还有那些办法？
- 如果HashMap的大小超过了负载因子定义的容量怎么办？
- 重新调整HashMap的大小存在什么问题吗？
