hashmap是java开发和Android开发中使用度非常高的数据结构，平时业务开发中更多的是使用，对其了解甚小，正好这段时间不忙 对其一些原理性和细节有了浅显的研究，下面做一下记录，方便后续的查询：
- java中顺序存储和散列存储
- java中的数据类型分为基本类型和复合类型，对象属性通常也是由这两种类型组成，基本类型此处不再详述，更多的是描述复合类型。
- 复合类型以存储类型可以分类为顺序存储类型和散列存储类型，数组存储类型以数组，数组列表，数组栈，数组队列等，散列结构则是以链表，HashMap为主。
- 顺序存储以数组为例：数组的引用变量存储在栈内存中，对应的item下标及其value存储在堆内存的一块连续内存中。
- 散列又被称为哈希，哈希算法通过一定的算法将给定长度的输入计算成为固定长度的输出，通常来说就是将任意长度的消息压缩成为固定长度消息的消息摘要。Object对hash算法有着默认实现，后续子类可以重写hash算法。
- 散列存储结构和数据存储结构不同，散列是以key-value方式存储，以key的哈希值为索引进行add，remove，get操作等，散列数据结构多以链表的方式进行存储。
- 散列（哈希）冲突：哈希表通常以key的哈希值计算映射地址，任意hash函数最终都有可能计算出相同的地址，这就被称为哈希冲突。
- 解决hash冲突的方法：开放地址法（继续寻找下一个没有使用的地址，针对数组来说顺序查找），再hash函数法（再次进行hash函数），链表法，相同hash值的对象通过链表链起来（hashmap使用这个）
- 顺序存储方便查询和修改，链表方便增删 ，原因是顺序每一次增删都得移动当前所有的元素item，而散列则修改其key即可，查询则相反。
- java中HashMap的物理存储
- HashMap的底层也是HashTable的实现，物理存储是以数组+链表的模式实现。
- HashMap add数据，先以key的hash值计算出对应的数组下标（具体参考下面的hash算法整理），校验当前数组下标是否有值，若没有直接插入，若有则校验key值，key存在修改value，若不存在找到最后一个item链到表尾。
- 结合上面数组方便查询，散列方便增删的优势，尽可能的散列平均（最优是单个key对应单个下标）减少散列冲突即链表越短越好。
- hashmap在1.8中除了数组加链表方式，在数组长度大于64且链表长度大于8的时候会将链表转为红黑树，在数组长度小于6的时候从红黑树再转为链表。
- HashMap的hash算法
- 节点寻址算法如下：
tab[i = (n - 1) & hash]
此算法为映射数组下标的算法，即key的hash值和map的数组长度取按位于操作，按位于操作最大取决于两者最小的数即取决于数组长度，此也解决了hash码过大超出数组下标的问题。
- 单纯的key的hash值和数组长度取按位于极容易出现相同的数组下标即哈希冲突严重会将数据都链接到同一个下标上，为了优化这个问题引入了扰动函数，即：
static final int hash(Object key) {
int h;
return (key == null) ? 0 :
(h = key.hashCode()) ^ (h >>> 16);
}
- 如上：若key为null，则key的hash值为0若key不为null则扰动函数如下：
* 计算key的hash值
* 将其hash值无符号右移16位后高位补0后和hash值进行异或操作得到最终的hash值，扰动函数的核心是无符号右移后将高16位移到低16位再和hash值的原低16位异或操作实现了原高16位和低16位的融合尽可能减少hash冲突。
- hashmap的构造方法解析：
- hashmap的构造方法主要有两个参数：初始大小和装载因子，初始大小可以指定hashmap的初始数组长度，装载因子决定了hashmap什么时候扩容，即扩容=初始大小*装载因子,当hashmap的数组长度大于前面的值的时候hashmap进行扩容。
- 默认构造参数为16，装载因子为0.75,扩容值为12
- 可以通过构造方法修改上面两个值，不过需要注意的是 初始大小设置无论什么数，hashmap创建的时候都会按照2的次数幂进行创建即大于设定值的2的最近次数幂创建。
- 为了优化hashmap性能建议创建hashmap的时候设置map的初始长度，此初始长度的依赖于：
* 2的次数幂
* 尽可能减少扩容
* 比如map长度为19，则若装载因子不变还是0.75则考虑扩容因素，使其不扩容则长度设置为26,26不是2的次数幂 则离其最近是32,所以最优化设置其长度为32. 若直接设置其长度为19 hashmap会创建为32，因为离19最近的2的次数幂也是32. - 为什么hashmap的长度是2的次数幂？
- hashmap2次幂和非2次幂对比图.png
- 如对比图所示，2次幂可以让元素更均匀的分配到数组中去，提升了元素的查询效率，通过hash值查询效率高于hash查询不到再通过key查询。
- 结合hashmap的hash算法是（length-1）&hash，2次幂减一可以保证最后一位是1非2次幂减一则二进制后最后一位是0，而按位与运算是都为一则为一，最后一位为1则能保证hash值的最后一位0和1区分，若最后一位为0则不能区分hash值的最后一位，最后一位0和1对应的都是0，这样整个数组就有一半的位置不可用，非2次幂则提升了哈希冲突。
- 为了优化hashmap性能建议创建hashmap的时候设置map的初始长度，此初始长度的依赖于：
- hashmap的扩容：
- hashmap的扩容在java 1.7和1.8 存在不同，java1.7 当数量超过初始大小*转载因子就会成倍数（2倍）扩容，在java 1.8 则是数量小于64的时候优先倍数扩容，在数量达到64链表长度大于8的时候先转为红黑树，在putval的时候若数组长度小于6的时候又有红黑树转为链表。
-
hashmap 在1.7中2倍容量扩容，然后元素可能重新计算hash也可能不重新计算按照头插法插入新的数组，在1.8中结合hashmap 数组成倍数扩容，item属性要么数组下标位置不变要么数组下标=原位置+数组原长度。即：
hashmap的1.8扩容
- hashmap 1.7和1.8的区别：
- 存储方式不同
- 扩容后计算数组下标的方式不同
- 扩容策略不同
- 数组不能扩容，为何hashmap可以扩容
- 数组不能扩容是不会自动扩容，可以人为复制数组的方式扩容数组
- hashmap也是利用了数组复制扩容的方式实现扩容
参考文章：
hashmap 元素存储原理解析
hashmap 底层存储原理
java 数组的扩容方式
hashmap中的hash算法总结
知乎：hashmap中的hash算法原理
hashmap 红黑树和链表转换
解析hashmap红黑树和链表转换时机
解析为何hashmap要指定长度
hashmap扩容的是元素还是数组
知乎：hashmap扩容的扩容机制
hashmap扩容的扩容机制及其元素迁移
