1. HashMap集合介绍
-
hashMap基于hash表(是根据关键码值(key value)而直接进行访问的数据结构)的Map接口实现，是以key:value存储形式存在，即主要用来存储键值对。hashMap的实现是不同步，这意味着它的线程是不安全的。它的key，value都可以为null，此外，hashMap中的映射不是有序 - jdk1.8之前
hashMap是由数组+链表组成，数组是hashMap的主体,链表则主要是解决哈希冲突（两个对象调用的hashCode方法计算的哈希值一致导致计算数组的索引值相同）而存在的（“拉链法”解决冲突）。jdk1.8之后是由数组+链表+红黑树组成，在解决哈希冲突时有了较大的改变，当链表长度大于阈值（默认8）并且当前的数组长度大于64时，此时此索引上的链表结构转化为红黑树结构，及此索引位置上的所有数据改为使用红黑树存储
补充：将链表转换成红黑树前会判断，即便阈值大于8，但是数组的长度小于64，此时并不会将链表转化为红黑树，而是选择数组扩容
这样做的目的是因为数组比较小，尽量避开红黑树结构，这种情况下变成红黑树结构，反而会降低效率，因为红黑树需要进行左旋，右旋，变色这些操作保持平衡。同时数组长度小于64是，搜索速率相对是比较快的。所以综合所述为了提高性能和减少搜索时间，底层阈值大于8并且数组长度大于64是，链表才转化为红黑树，具体可以去参看treeifyBin()方法
- hashMap特点
- 存储无序
- 键和值位置都可为null，但键位置只能存放一个null
- 键位置是唯一的，是底层的数据结构控制的
- jdk1.8之前数据结构为数组+链表，jdk1.8之后为数组+链表+红黑树
- 阈值大于8并且数组长度大于64，才将链表转换成红黑树，变为红黑树的目的是提高查询速率
2. HashMap底层数据结构
2.1 数据结构
数据结构是[计算机]存储、组织[数据]的方式。数据结构是指相互之间存在一种或多种特定关系的[数据元素]的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储[效率]。数据结构往往同高效的检索[算法]和[索引]技术有关
人话可以理解为：数据结构就是用来存储数据的一种方式
2.2 存储数据过程
HashMap<String, Integer> map = new HashMap<>();
map.put("柳岩", 18);
map.put("杨幂", 28);
map.put("刘德华", 40);
map.put("柳岩", 20);
输出结果：{杨幂=28, 柳岩=20, 刘德华=40}
分析过程：
当创建HashMap集合对象的时候，在jdk1.8之前，构造函数中创建一个长度为16的 entry[ ] table用来存储键值对数据的。在jdk1.8之后不是在构造函数底层创建一个数组，是在第一次调用put方法是创建的数组node[ ] table用来存储键值对数据
假设向哈希表中存储 <柳岩,18> 数据，根据柳岩调用 String 类中重写之后的 hashCode() 方法计算出值，然后结合数组长度采用某种算法计算出向 Node 数组中存储数据的空间的索引值。如果计算出的索引空间没有数据，则直接将<柳岩,18>存储到数组中。（举例：计算出的索引是 3 ）
向哈希表中存储数据 <刘德华,40>，假设算出的 hashCode() 方法结合数组长度计算出的索引值也是3，那么此时数组空间不是 null，此时底层会比较柳岩和刘德华的 hash 值是否一致，如果不一致，则在空间上划出一个结点来存储键值对数据对 <刘德华,40>，这种方式称为拉链法
-
假设向哈希表中存储数据 <柳岩,20>，那么首先根据柳岩调用 hashCode() 方法结合数组长度计算出索引是 3，此时比较后存储的数据柳岩和已经存在的数据的 hash 值是否相等，如果 hash 值相等，此时发生哈希碰撞。那么底层会调用柳岩所属类 String 中的 equals() 方法比较两个key的内容是否相等？
相等：将后添加的数据的 value 覆盖之前的 value
不相等：继续向下和其他的数据的 key 进行比较，如果都不相等，则划出一个结点存储数据，如果结点长度即链表长度大于阈值 8 并且数组长度大于 64 则将链表变为红黑树
在不断的添加数据的过程中，会涉及到扩容问题，当超出阈值（且要存放的位置非空）时，扩容。默认的扩容方式：扩容为原来容量的 2 倍，并将原有的数据复制过来
综上描述，当位于一个表中的元素较多，即 hash 值相等但是内容不相等的元素较多时，通过 key 值依次查找的效率较低。而 jdk1.8 中，哈希表存储采用数组+链表+红黑树实现，当链表长度（阈值）超过8且当前数组的长度大于64时，将链表转换为红黑树，这样大大减少了查找时间
简单的来说，哈希表是由数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的。如下图所示：
jdk1.8 中引入红黑树的进一步原因：
jdk1.8以前 HashMap 的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当HashMap中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有n个元素，遍历的时间复杂度就是O(n)，完全失去了它的优势
针对这种情况，jdk1.8中引入了红黑树（查找时间复杂度为O(logn)）来优化这个问题。当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树
关于时间复杂度O(n),O(logn)简介,参考:https://www.jianshu.com/p/f31744e423eb总结：
-
- size 表示 HashMap 中键值对的实时数量，注意这个不等于数组的长度
- threshold（临界值）= capacity（容量）* loadFactor（负载因子）。这个值是当前已占用数组长度的最大值。size超过这个值就重新 resize（扩容），扩容后的 HashMap 容量是之前容量的两倍
