哈希表（HashMap）

（面试题）谈谈你理解的HashMap？
HashMap本质上是一个用Key，Value结构做存储的，内部是使用哈希表这种数据结构。
哈希表是非常适合用来做搜索的数据结构，因为它可以实现插入/删除/查找时间复杂度是O(1)。
哈希表最重要内部是由数组（利用数组的随机访问是O(1)的特性）实现+单链表或者其他数据结构（这些数据结构主要是为了解决Hash冲突）

例：10万个数可以均匀分布于1万个数组元素中，相当于在10个数中查找想要访问元素。时间复杂度可以看为O(1)。

HashMap是可以以引用类型来进行存储，如果需要通过引用类型来进行存储，我们需要对Key复写HashCode的方法。得到Hash值怎么保证Hash值转化为数组下标是不越界呢？
java中使用的是：
第一：数组的长度一定是幂次方比如：1,2,4,8,16…
第二：利用Hash值%（数组长度-1）
结合起来可以保证我们的下标是不会越界的。

最后：找到元素为值Index：再在Hash值对应的链表中查找即可。因为很高效所以一般认为时间复杂度（O(1)）

为什么1.7时候使用的是头插法，1.8变成尾插？？

因为HashMap本来是线程不安全的，但是总是有人将HashMap在多线程环境下使用，如果在多线程环境下使用头插很可能形成循环链表，在查询就死循环了，CPU100%，这台机器就什么都不能干了。如果改成尾插的话虽然是错的但是不会出现卡死的现象。也只能算是降低损失。再次提醒多线程下不要使用HashMap。使用ConcurrentHashMap,虽然HashTable是线程安全的，但效率很低（只有一把锁，一个线程跑其他就不能跑了）

为什么HashMap不是线程安全的？

考虑两方面：1.有没有写2.有没有写同一个对象（共享资源）

看成链表一样，会有多个线程对数据进行修改，在插入的过程包括扩容中是使数据出现错误。

为什么在HashMap中的链表会退化成红黑树

1.hash算法是公开的
如果有人恶意攻击：肯定可以构建一组数据，这组数据的hash值是一样的（冲突了），是无法通过调节负载因子来控制冲突率了

解决方法：
1.运算hash的过程中加入其它不公开的信息：私钥参与hash运算
2.某个下标冲突率过高代表小集合数据也太多了，不适合用链表再用其他的数据结构解决。
搜索树vs哈希表
java选择红黑树解决。
什么情况下认为过多了，阈值8个，key的个数足够多的情况。
根据泊松分布计算，如果一个index的冲突个数=8的概率是0.00000006
如果真的是8，1.认为要不是恶意情况 2，认为数据本身不是均匀分布的。

java中所有集合基本都是延迟初始化的
Node[ ] table=null
用到的时候再初始化（put数的时候）

HashMap是允许key为null，其他都不允许Hashtable/ConcurrentHashMap

就插入的过程讲解：

1.哈希函数（key）=> 哈希值

并不要求Key是整形数字
HashMap的key是引用类型，所以，实际上调用的是HashCode()
如果自定义类作为key，必须覆写hashCode()方法
保证认为对象相等，则hashCode()得到的哈希值一定是一样的

2.如何从哈希值的到一个有效的下标（不越界的下标）

int index = hash%array.length(建立在array.length是素数的基础上效果最好)
java 前提array.length一定是2的次方，16/32/64/128
前提：下标一定是32 位（很多时候没有这么大）
hashCode()是32位的
<1>高16位 -异或上-低16位====>尽可能的使每一位都参与到下标的获取，并且尽可能的符合均匀分布。
<2>h:上一步的结果 . L：数组的长度(一定是2的次方)
. . .int index = h & (L-1)
. . . 位用算：
根据下标找到数组位置进行插入，引出问题
冲突：
1.什么是冲突
不同的key，通过运算得到的hash值是相同的
2.冲突可能消除吗？
数组的长度 << 数据的个数，所有数据放在有限个数组元素中
根据鸽笼原理，必然是存在一个笼子里有多个鸽子
3.冲突不能消除的情况，并且不想要冲突，怎么尽可能避免冲突？
<1>hash的函数设计：理想情况下，key是符合均匀分布的
经过hash函数，得到的hash值也尽可能的均匀分布。
<2>负载因子=key的个数/数组的长度
冲突率的函数曲线

4.真冲突了怎么解决？
闭散列：此处不留爷，自有留爷处
开散列/哈希桶：利用一个其他的数据结构存储所有冲突的key，之所以选择链表是：一般情况下冲突的个数不会太多，链表就够用了。
单链表每有一个数据就保留一个数据，顺序表是需要预留空间。
HashMap是采用这种方式。