HashMap是怎么解决哈希冲突的？
在解决这个问题之前，我们首先需要知道什么是哈希冲突，而在了解哈希冲突之前我们还要知道什么是哈希才行；什么是哈希？
Hash，一般翻译为“散列”，也有直接音译为“哈希”的，这就是把任意长度的输入通过散列算法，变换成
固定长度的输出，该输出就是散列值（哈希值）；这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要(Message Digest , MD5算法就是一种消息摘要函数)的函数。
所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。
什么是哈希冲突？
当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做碰撞（哈希碰
撞）。
HashMap的数据结构
在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做链地址法的方式可以解决哈希冲突。
这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的 bucket下，但相比
于hashCode返回的int（32bit）类型，我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16）要远小于int类型的范围，所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率，并且最坏情况下还会将HashMap变成一个单链表，所以我们还需要对hashCode作一定的优化。
上面提到的问题，主要是因为如果使用hashCode取余，那么相当于参与运算的只有hashCode的低位（原因是因为取余的大小是1<<4（16），那么其实在1<<5（32）以上的位置，他们对1<<4取余都等于0，也就是不会影响余数），高位是没有起到任何作用的，所以我们的思路就是让 hashCode取值出的高位也参与运算，进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动，在JDK 1.8中的hash()函数如下：
这比在JDK 1.7中，更为简洁，相比在1.7中的4次位运算，5次异或运算（9次扰动），在1.8中，只进行了1次位运算和1次异或运算（2次扰动）；
JDK1.8新增红黑树
通过上面的链地址法（使用散列表）和扰(img)动函数我们成功让我们的数据分布更平均，哈希碰撞减
少，但是当我们的HashMap中存在大量数据时，加入我们某个 bucket下对应的链表有n个元素，那么遍历时间复杂度就为O(n)，为了针对这个问题，JDK1.8在HashMap中新增了红黑树的数据结构，进一步使得遍历复杂度降低至O(logn)；
简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的：
- 使用链地址法（使用散列表）来链接拥有相同hash值的数据；
- 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；
- 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；
能否使用任何类作为 Map 的 key？
可以使用任何类作为 Map 的 key，然而在使用之前，需要考虑以下几点： 如果类重写了 equals() 方法，也应该重写 hashCode() 方法。类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。
如果一个类没有使用 equals()，不应该在 hashCode() 中使用它。
用户自定义 Key 类的最佳实践是使之为不可变的，这样 hashCode() 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变，这样就会解决与可变相关的问题了。这也就是为什么上面推荐使用String，Integer作为键。如果键是可变的，那么使用的时候就可能出现由于键内部的属性改变，导致hashcode返回的值改变，那么就会查询不到原有的数据了。
为什么HashMap中String、Integer这样的包装类适合作为K？
String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少
Hash碰撞的几率。
- 都是final类型，即不可变性，保证key的不可更改性，不会存在获取 hash值不同的情况
- 内部已重写了equals()、hashCode()等方法，遵守了HashMap内部的规范（不清楚可以去上面看看
putValue的过程），不容易出现Hash值计算错误的情况
如果使用Object作为HashMap的Key，应该怎么办呢？
必须重写hashCode()和equals()方法！！！
- 重写hashCode()是因为需要计算存储数据的存储位置，需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能，这样虽然能更快但可能会导致更多的Hash碰撞；
- 重写equals()方法，需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x，x.equals(null)必须返回false的这几个特性，目的是为了保证key在哈希表中的唯一性，具体如何设计一个良好的equals方法可以直接搜索 “如何设计一个完美的equals方法”，可以查找到许多答案。
HashMap为什么不直接使用hashCode()处理后的哈希 值直接作为table的下标而是需要进行二次Hash？
答：hashCode()方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 - 1)，约有40亿个映射空间，而HashMap的容量范围是在16（初始化默认值）~2 ^ 30，HashMap通常情况下是取不到 大值的，并且设备上也难以提供这么多的存储空间，从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置；
那怎么解决呢？
- HashMap自己实现了自己的hash()方法，通过两次扰动使得它自己的哈希值高低位自行进行异或运算，降低哈希碰撞概率也使得数据分布更平均；
- 在保证数组长度为2的幂次方的时候，使用hash()运算之后的值与运算（&）（数组长度 - 1）来获取数组下标的方式进行存储，这样一来是比取余操作更加有效率，二来也是因为只有当数组长度为2的幂次方时，h&(length-1)才等价于h%length，三来解决了“哈希值与数组大小范围不匹配"的问题
HashMap 的长度为什么是2的幂次方
这道题的答案其实就是上面那道题的答案
为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。
这个算法应该如何设计呢？
我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。”
并且采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。
并且扩容时hash&oldCap==0的元素留在原来位置，否则新位置=旧位置+oldCap
那为什么是两次扰动呢？
这样就是加大哈希值低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性与均匀性， 对于减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的。
HashMap 的长度不使用2的幂次方可以吗？
可以，首先使用2的幂次方带来的第一个问题就是数据的分布可能不那么均匀了。
因为对于偶数的数字进行与运算的时候，就可能导致大部分的偶数数据全都扎堆在偶数索引处，导致数据分布不均匀。而如果想要追求更高的Hash分布的均匀，那么推荐使用质数作为容量，并且如果容量为质数，那么甚至都不需要进行二次hash也可以获取很好的hash分布性。
所以选择使用2的幂次方主要是为了追求性能。
而如果要求追求hash分布性的，那么是可以不使用2的幂次方的。
例如.net中的实现就是扩容的时候先翻倍，然后查找比当前容量大的最接近的质数作为新容量，因此.net更加追求分布性，而Java则追求性能。
HashMap 与 HashTable 有什么区别？
- 线程安全： HashMap 是非线程安全的，HashTable 是线程安全的；
HashTable 内部的方法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使用
ConcurrentHashMap 吧！）； - 效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被
淘汰，不要在代码中使用它； - 对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一
个或多个键所对应的值为 null。但是在HashTable 中 put 进的键值只要有一个 null，直接抛NullPointerException。 - 初始容量大小和每次扩充容量大小的不同 ：
①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。
②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小，后面会介绍到为什么是2 的幂次方（其实上面的回答就已经给出答案了）。 - 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈
值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。 - 推荐使用：在 Hashtable 的类注释可以看到，Hashtable 是保留类不建议使用，推荐在单线程环境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代。
如何决定使用 HashMap 还是TreeMap？
对于在Map中插入、删除和定位元素这类操作，HashMap是 好的选择。
然而，假如你需要对一个有序的key集合进行遍历，TreeMap是更好的选择。基于你的collection的大小，也许向HashMap中添加元素会更快，但将map换为TreeMap允许你进行有序key的遍历，具体使用情况看场景。
HashMap 和 ConcurrentHashMap （并发HashMap）的区别
- ConcurrentHashMap对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁进
行保护，相对于HashTable的synchronized 锁的粒度更精细了一些，并发性能更好，而HashMap
没有锁机制，不是线程安全的。（JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用
CAS算法。） - HashMap的键值对允许有null，但是ConCurrentHashMap都不允许。
ConcurrentHashMap 和 Hashtable 的区别？
ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。
- 底层数据结构：
JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，
JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。
Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的； - 实现线程安全的方式（重要）:
① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据（一把锁锁一个Segment），多线程访问容器（不同Segment）里不同数据段的数据，就不会存在锁竞争，提高并发访问率。（默认分配16个Segment，也就是把数组分为了16段，最优情况下比Hashtable效率提高16倍！！！。） ，而如果想要读取Segment中的数据，那么就得先获取到这把锁，所以他最多支持16个线程的并发。
到了 JDK1.8 的时候已经摒弃了Segment的概念，不再继续使用分段锁的方式，而是直接用 Node 数组+链表+红黑树 的数据结构来实现，并发控制使用synchronized 和 CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化），它使用了更加细粒度的锁，他锁的不再是一个分段了，而是哈希桶中的一个最小单位，然后再写入键值对的时候，可以锁住哈希桶中的链表的头节点，锁住了链表的头节点，那么后面的节点也无法访问了，就保证了线程安全。或者是锁住树的根节点，是一样的。 整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；
②Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。
两者对比图如下：
JDK1.7的ConcurrentHashMap：
JDK1.8的ConcurrentHashMap（TreeBi(img)n: 红黑二叉树节点 Node: 链表节点）：
JDK1.7中的ConcurrentHashMap的规则
基本结构
在JDK1.7中ConcurrentHashMap的底层结构为Segment数组+数组+链表。
其中只需要对Segment数组进行加锁，那么Segment中的数组的元素就不允许并发访问了，但是如果访问的是不同的Segment数组中的数据，那么就允许并发访问。
下面说一下这个版本中的ConcurrentHashMap的构造函数，他有三个参数，分别是capacity：容量
factor：数组扩容因子，指的不是Segment数组，而是Segment数组中的数组
clevel：并发度，代表了Segment数组的长度
刚才说过Segment中的元素是一个数组和链表，而这个数组的长度的初始值为
capacity/clevel，也就是如果你的capacity为64，clevel为16，那么初始的数组长度就为4，并且当元素个数达到3个，还会触发扩容。而如果capacity的值小于clevel，那么默认数组大小为2。
Segment[0]与原型模式
JDK1.7中的ConcurrentHashMap中在创建的时候只有Segment[0]这个下标有数组，这里设定数组大小为2，那么之后再有数据插入的时候，在其他Segment数组处会以Segment[0]此时的数组状态进行创建。
例如如果要插入到Segment[1] ，此时如果Segment[0]长度为2，那么创建Segment[1]时候的数组大小也是2，如果要插入到Segment[2]，此时的Segment[1]的数组大小为4，那么创建的数组大小也为4。这使用了设计模式中的原型模式。
Hash规则
JDK1.7中的ConcurrentHashMap的hash规则与hashmap不相同。
当输入的数据得到原始hash之后，会经过二次hash，二次hash的二进制数中，取出高n位组成的十进制数作为数据要插入到的Segment下表。取出低m位作为Segment数组中的数组的下标。其中n满足2 ^ n=clevel，2 ^ m=Segment数组中的数组大小
例如二次hash后得到的32位为 1100 0000 … 0001。设定此时clevel为16，Segment的数组中的数组大小为2，那么就有n=4，m=1。
所以此时定位到Segment的位置为12，并且定位到Segment数组中的数组下标为1。
JDK1.8中的ConcurrentHashMap
底层结构
不再使用重量级的Segment数组，而是使用数组+链表+红黑树的结构。
相比于JDK1.7中的饿汉式创建数组，JDK1.8中使用的是懒汉式，也就是必须调用了PUT方法之后才会创建ConcurrentHashMap。
他的初始容量也是16，他的扩容规则和JDK1.8中的HashMap一样，也是只要元素个数达到阈值就直接扩容，并且重新Hash。
构造函数
JDK1.8中的ConcurrentHashMap的构造函数参数为capacity和factor，但是这里是capacity表示的是ConcurrentHashMap要放入16个元素，很明显如果要放入16个元素，是需要进行扩容的，因此如果你设定capacity为16，那么创建的ConcurrentHashMap数组大小为32。如果你设定的是12，那么由于默认是0.75，因此还是超过了，所以创建的还是32。
而这里的factor扩容因子，也只是对于构造函数的时候有用，而之后的扩容因子大小依旧为0.75。例如一开始你设置capacity为7，然后factor为0.5，因此此时不会触发扩容，而就算再放入一个元素也不会扩容，你可能以为16*0.5=8应该要发生扩容了，但是这个factor代表的只是与你第一次构建数组的时候的扩容因子大小。因此如果你一开始设定的capacity为8，然后factor设定为0.5，那么此时创建的数组大小就是32。
扩容过程
这里设定数组大小为16，扩容因子为0.75，数组中已经有了11个元素了，此时再次插入一个元素的时候就会触发数组扩容。对于ConcurrentHashMap，扩容的方式为从数组尾巴开始，将链表中的数据经过rehash放入到新的数组中去。然后每一个被处理完毕的链表，都会被设定为forwardingNode。直到所有的数组位置都被复制，那么此时旧数组就会被新数组给代替了。
那么，其中扩容的细节是什么呢？
以为ConcurrentHashMap代表的是多线程下的HashMap呀，如果在扩容的过程中有其他线程来get或者put数据怎么办呢？总不能支持多线程的ConcurrentHashMap让我阻塞吧？
get
首先我们来说说get方法。
情况1：某条链表中的数据已经完整复制到新数组中
我们现在假设数组中的部分数据已经被拷贝完毕了，也就是数组链表被设定为forwardingNode。那么此时分为两种情况，第一种是如果访问的是还没有被拷贝的数组位置，那么就直接访问旧数组里面的数据即可，第二种情况就是访问到了已经拷贝完毕的数据，那么此时链表被设定为forwardingNode，那么这个线程就要去新数组中查找数据了。所以此时对于get方法，是不会阻塞的，可以并发运行。
情况2：查询时数据只复制了一半，还有一半还在链表中
这种情况就是get方法查询到的是一条比较长的链表，此时链表还没有被设定为forwardingNode，那么查询就会在旧的链表中进行查询。
但是由于会发生rehash，所以会导致迁移节点后，新数组中的1节点和旧数组中的1节点不是同一个对象，下图中1数组中的节点的next就不再是2而是null了。因此如果说使用的还是原来的对象，那么就完全可以去新数组中查找呀，以为那样子新数组中的节点1的next代表的还是2，但是此时其实已经是null了，所以进行扩容的时候其实进行的是创建了新的节点，而不是直接把原有的数据复制过去。当然ConcurrentHashMap也做了优化，就是在链表的最后几个元素，比如这里的3，4元素，他们如果rehash之后还是在对方的下面，那么就是直接复制过去了，不需要重新的创建。
put
put的并发情况分为三种。
情况1：
put的时候发生的是还没有开始发生扩容迁移时候的链表位置，那么此时就是正常情况，直接put即可，并且允许并发执行。
情况2：
put的位置是发生迁移的链表位置，由于我们知道扩容的时候会需要加锁，所以此时链表头加锁了，是无法访问的，所以也无法进行put操作，必须阻塞直到完成扩容。
情况3：
put发生的位置是节点类型为forwardingNode的时候，此时并不是将这个数据put到新数组中。因为ConcurrentHashMap既然是多线程的，那么其实他的扩容并不是完全由一个线程去执行的，而是一个线程去扩容16个数组大小，例如原本的数组大小为32，那么原有的线程可能扩容的是0-15这个位置的数组，然后此时这个put线程发现他put的时候要阻塞，所以他也没有闲着，而是去帮忙这个线程去做扩容，他可能扩容的久是16-31这个位置的数组。
ConcurrentHashMap可以使用ReentrantLock作为锁吗？
理论上是可以的，但是不推荐。
在JDK1.6之后，synchronized关键字已经被升级了。
他引入了偏向锁，轻量级锁，重量级锁，而这些在ReentrantLock中是没有的。
并且随着JDK版本的升级，synchronized也在进一步优化，而ReentrantLock本身也是使用Java代码来实现的，因此优化的空间比较少。因此选择优先选择synchronized，次之选择ReentrantLock。
