我的博客java篇-HashMap
概括
HashMap 散列表，通过数组加链表的形式构成，在jdk1.8以后，当链表长度大于8的时候，会转化成红黑树的形式存储。
允许null值，同时非有序，非同步(即线程不安全)
put 方法原理
- 根据
key的hasCode，通过哈希函数算出存储位置index值。 - 如果改位置没有元素，则直接存储
- 如果已经有了元素，就判断该元素的
key值和key的hashCode是否一致，一致就直接覆盖value - 如果不一致，就产生了
hash冲突，就在链表上插入新的结点存储，如果链表长度大于8的话，就转化成红黑树进行存储 - 插入后，如果数量大于阈值则进行扩容
get 方法原理
- 根据
key做Hash映射，得到对应的index - 遍历链表或者红黑树，查找
key值和key的hashCode都相等的节点，返回value
HashMap 的容量为什么一定要是 2 的 n 次方
HashMap的默认初始长度是16，并且每次自动扩展或者手动初始化时，长度必须为2的幂
因为为了让元素能够均匀分配，HashMap需要将key映射到index
计算方法 index = key的hash值 & (Length - 1) 将key的hash值和数组的长度-1取逻辑与运算
当HashMap的容量为2的n次方的时候，length-1的值所有二进制为都为1，这样能让index的计算结果分布更加均匀
扰动函数（hash 函数）
在计算数组的index值的时候，并不是直接通过key的hashcode和lengh-1取逻辑与运算的，这里有很多文章都是错误的讲解，需要先将hashcode通过hash函数计算出hash值，在和数组的lengh-1取逻辑与运算
///jdk1.8源码
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
我们需要hash值是足够散列的，这样才能减少hash碰撞的概率
任意一个Objec类型的hashCode方法得到的hashCode值是一个int类型，有32位。
显然很少有HashMap的数组有40亿这么长。如果只是取低几位的hash值的话，那么那些低位相同，高位不同的hash值就碰撞了，如：
/// Hash碰撞示例：
H1: 00000000 00000000 00000000 00000101 & 1111 = 0101
H2: 00000000 11111111 00000000 00000101 & 1111 = 0101
为了解决这类问题，HashMap想了一种办法（扰动）：将hash值的高16位右移并与原hash值取异或运算^，混合高16位和低16位的值，得到一个更加散列的低16位的hash值。如：
00000000 00000000 00000000 00000101 // H1
00000000 00000000 00000000 00000000 // H1 >>> 16
00000000 00000000 00000000 00000101 // hash = H1 ^ (H1 >>> 16) = 5
00000000 11111111 00000000 00000101 // H2
00000000 00000000 00000000 11111111 // H2 >>> 16
00000000 00000000 00000000 11111010 // hash = H2 ^ (H2 >>> 16) = 250
这样将hashcode通过扰动函数生成hash值，就可以减少hash碰撞的概率了
负载因子
负载因子loadFactor表示哈希表空间的使用程度，当size到达数组的容量*负载因子的时候，会触发扩容
当负载因子越大，则HashMap的装载程度就越高。也就是能容纳更多的元素，元素多了，发生hash碰撞的几率就会加大，从而链表就会拉长，此时的查询效率就会降低。
当负载因子越小，则链表中的数据量就越稀疏，此时会对空间造成浪费，但是此时查询效率高。
扩容机制
条件： HashMap.Size >= Capacity * LoadFactor
步骤：
1.扩容
创建一个新的Entry空数组，长度是原数组的 2 倍。
2.ReHash
遍历原Entry数组，把所有的Entry重新Hash到新数组。为什么要重新Hash呢？因为长度扩大以后，index的计算规则也会改变，需要重新计算分布
HashMap 为什么是非线程安全的
当
a线程准备插入的时候，线程阻塞，b线程插入成功，a线程继续运行的话，会覆盖b线程的值ReHash在并发的情况下可能会形成链表环（java8之前）
头插法和尾插法
在java8之前是头插法，java8之后是尾插法
使用头插法，在高并发的场景下会出现链表成环的问题
使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了
为啥我们重写 equals 方法的时候需要重写 hashCode 方法呢
如何重写了equals方法，会导致原先不相同的两个对象，现在相同了，但是他们的hashcode还是不相同，违背了相同的对象返回相同的 hash 值，不同的对象返回不同的 hash 值的设计初衷
使用HashMap时，谨慎使用可变对象作为key键
如果key对象是可变的，那么key的哈希值就可能改变。在HashMap中可变对象作为Key会造成数据丢失。因为我们再进行hash & (length - 1)取模运算计算位置查找对应元素时，位置可能已经发生改变，导致数据丢失
最好选择不可变对象作为key。例如String，Integer等不可变类型作为key是非常明智的
HashMap 和 HashTable 的区别
- HashMap 的 key 和 value 都允许为 null，Hashtable 的 key 和 value 都不允许为 null
- HashMap 的初始化容量为 16，并且容器容量一定是 2 的 n 次方，扩容时，是以原容量 2 倍 的方式 进行扩容。Hashtable 初始化容量为 11 扩容时，是以原容量 2 倍 再加 1 的方式进行扩容。即
int newCapacity = (oldCapacity << 1) + 1 - 散列分布方式
-
HashMap是先将key键的hashCode经过扰动函数扰动后得到hash值，然后再利用hash & (length - 1)的方式代替取模，得到元素的存储位置 -
Hashtable则是除留余数法进行计算存储位置的（因为其默认容量也不是2的n次方。所以也无法用位运算替代模运算），int index = (hash & 0x7FFFFFFF) % tab.length
-
- 线程安全
-
HashMap不是线程安全，如果想线程安全，可以通过调用synchronizedMap(Map m)使其线程安全。但是使用时的运行效率会下降，所以建议使用ConcurrentHashMap容器以此达到线程安全。 -
Hashtable则是线程安全的，每个操作方法前都有synchronized修饰使其同步，但运行效率也不高，所以还是建议使用ConcurrentHashMap容器以此达到线程安全。
-
Hashtable是一个遗留容器，如果我们不需要线程同步，则建议使用HashMap，如果需要线程同步，则建议使用ConcurrentHashMap
