1.Put方法原理
- 通过对key.hashCode()进行哈希计算[1]，即hash(key.hashCode())得到hash值
- 再通过hash & (table.length - 1) 得到key在bucket数组上映射的索引位置
- 该位置如果为空， 直接插入key-value键值对，如果不为空，则检测有没有相同的key，有相同的key，则把新的value插入，旧的value通过put方法返回；如果没有相同的key，则发生了哈希冲突，需要解决哈希冲突
- 将这个新的key-value键值对以链表节点的形式挂在当前数组位置的下方，通过“链表散列”的数据结构解决哈希冲突
- Jdk1.8，解决冲突的方式发生了改进，如果bucket数组长度没有达到64，那首先会进行扩容，扩容操作是每次都扩容到原来的两倍，如果达到64，链表长度达到8的时候，就会将链表转化为红黑树节点，以减少元素检索的时间，提高检索效率。
[1] 哈希计算得到hash值的过程：hashCode与hashCode>>>16进行异或操作。
哈希函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞
2.HashMap使用了哪些方法来解决哈希冲突？
- 使用链地址法（使用散列表）来链接拥有相同hash值的数据；
- 使用hash函数来降低哈希冲突的概率，使得数据分布更平均；
- 引入红黑树进一步降低遍历的时间复杂度O（logn），使得遍历更快；
3.Hashmap初始容量多大？
①默认情况下初始容量为16；
②如果使用构造函数指定一个数字为容量，那么会选择大于等于这个数字的第一个2的幂次的数字，比如指定3，构建的容量则为4，指定5就是8。得到这个数字的算法是通过无符号右移和按位或来提升计算效率的。
③如果想最大程度避免扩容带来的内存消耗，建议把默认容量大小的数字设置成expectedSize/0.75F + 1F。日常开发中，可以通过Map<String,String> map = Maps.newHashMapWithExpectedSize(10) 来创建HashMap。
第三种情况是因为：当HashMap内部维护的哈希表的容量达到75%时（默认情况下），会触发rehash（扩容），而rehash的过程是比较耗费时间的。所以初始化容量时用的数字要设置成expectedSize/0.75 + 1的话，可以有效的减少冲突也可以减小误差，当然在内存上会有小小的牺牲。
举例：比如我们想要装载的元素个数为7，使用构造函数构建HashMap会将其容量设置为8，但是8*75% = 6，也就是说当装了6个元素的时候，就会进行扩容操作，扩容操作非常费时间，是我们不愿意看到的，所以最有效的减少冲突的方式是将这个数字设置成expectedSize/0.75 + 1，即7/0.75 + 1 = 10,10经过jdk处理的结果是16,大大减少了扩容的几率，提升了效率。
4.HashMap的扩容操作是怎么实现的？
①.在jdk1.8中，resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize方法进行扩容；
②.每次扩展的时候，都是扩展2倍；
③.扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。
在putVal()中，我们看到在这个函数里面使用到了2次resize()方法，resize()方法表示的在进行第一次初始化时会对其进行扩容，或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发
这也是JDK1.8版本的一个优化的地方，在1.7中，扩容之后需要重新去计算其Hash值，根据Hash值对其进行分发，但在1.8版本中，则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0，重新进行hash分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上
5.为什么HashMap的长度为2的幂次方？
目的：
原因是为了减少Hash碰撞，尽量使Hash算法的结果均匀分布。
分析：
- 首先明确如何计算数组下标:index = hash & (length -1)
- 只有当HashMap的length为2的整数倍时，length-1的结果是全1，如HashMap的初始值是16，那么length-1就是1111，和length-1进行与运算，有16种(2的4次方)结果，所以h&(length-1)==h%length，这时候就运算结果的可能性数量而言，与运算 和 取模运算 相同，这是最理想的结果。
- 如果HashMap的length不是2的整数倍，如length=15，那么length-1就是14(1110)，那么最后一位不论为0还是为1,进行&运算的结果最后一位都是0，那么相当于最后一位就失效了，那么下标就不可能映射到以1结尾的数上，如0001（1）、0011（3）、0111（7）、1111（14），这样由于可以映射的范围减少，就增加了碰撞的概率，而且h&(length-1)！=h%length
给定数字后得出初始容量的算法：
①对一个二进制数依次向右移位，然后与原值取或。其目的对于一个数字的二进制，从第一个不为0的位开始，把后面的所有位都设置成1。
②就是做一下极限值的判断，然后把Step 1得到的数值+1。
无符号右移和按位或运算大大提升了效率。
计算初始化容量的算法的步骤代码：
int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; //说明：|= 代表 或等于
应用一下就很容易理解了：
1100 1100 1100 >>>1 = 0110 0110 0110 1100 1100 1100 | 0110 0110 0110 = 1110 1110 1110 1110 1110 1110 >>>2 = 0011 1011 1011 1110 1110 1110 | 0011 1011 1011 = 1111 1111 1111 1111 1111 1111 >>>4 = 1111 1111 1111 1111 1111 1111 | 1111 1111 1111 = 1111 1111 1111
但是还有一种特殊情况套用以上公式不行，这些数字就是2的幂自身。如果数字4 套用公式的话。得到的会是 8 ；为了解决这个问题，JDK的工程师把所有用户传进来的数在进行计算之前先-1，就是源码中的第一行：
参考：
https://www.jianshu.com/p/7cf2d6f1096b
https://thinkwon.blog.csdn.net/article/details/104588551
6.HashMap的扩容操作是怎么实现的？
①.在jdk1.8中，resize方法是在hashmap初始化时或者键值对个数大于阀值时（由装载因子决定，一般为hashmap容量的75%），就调用resize方法进行扩容；
②.每次扩展的时候，都是扩展2倍；
③.扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。
在putVal()中，我们看到在这个函数里面使用到了2次resize()方法，resize()方法表示的在进行第一次初始化时会对其进行扩容，或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发，这也是JDK1.8版本的一个优化的地方，在1.7中，扩容之后需要重新去计算其Hash值，根据Hash值对其进行分发，但在1.8版本中，则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0，重新进行hash分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上
7.Hashmap线程安全吗？多线程情况下用什么？
不安全，HashMap在多线程情况下，在put的时候，插入的元素超过了容量（由负载因子决定，一般为0.75）的范围就会触发扩容操作，就是rehash，这个会重新将原数组的内容重新hash到新的扩容数组中，在多线程的环境下，存在同时其他的元素也在进行put操作，如果hash值相同，可能出现同时在同一数组下用链表表示，造成闭环，导致在get时会出现死循环，所以HashMap是线程不安全的。多线程环境下一般使用ConcurrentHashMap。
8.ConcurrentHashMap实现原理是什么？
JDK1.7
首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。
在JDK1.7中，ConcurrentHashMap采用Segment + HashEntry的方式进行实现，结构如下：
一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。
1.该类包含两个静态内部类 HashEntry 和 Segment ；前者用来封装映射表的键值对，后者用来充当锁的角***r>2.Segment 是一种可重入的锁 ReentrantLock，每个 Segment 守护一个HashEntry 数组里得元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 锁。
JDK1.8
在JDK1.8中，放弃了Segment臃肿的设计
取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现，synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。
下面我来简单总结一下ConcurrentHashMap的核心要点：
1．底层结构是散列表(数组+链表)+红黑树，这一点和HashMap是一样的。
2．Hashtable是将所有的方法进行同步，效率低下。而ConcurrentHashMap作为一个高并发的容器，它是通过部分锁定+CAS算法来进行实现线程安全的。CAS算法也可以认为是乐观锁的一种~
3．在高并发环境下，统计数据(计算size…等等)其实是无意义的，因为在下一时刻size值就变化了。
4．get方法是非阻塞，无锁的。重写Node类，通过volatile修饰next来实现每次获取都是最新设置的值
5．ConcurrentHashMap的key和Value都不能为null
9.ConcurrentHashMap和HashMap区别在哪里？
1.ConcurrentHashMap对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁进行保护，相对于HashTable的synchronized锁的粒度更精细了一些，并发性能更好，而HashMap没有锁机制，不是线程安全的。（JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。）
2.HashMap的键值对允许有null，但是ConCurrentHashMap都不允许。
10.HashMap 与 HashTable 有什么区别？
1.线程安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过 synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
2.效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
3.对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛NullPointerException。
4.初始容量大小和每次扩充容量大小的不同： ①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小，后面会介绍到为什么是2的幂次方。
5.底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。
6.推荐使用：在 Hashtable 的类注释可以看到，Hashtable 是保留类不建议使用，推荐在单线程环境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代。
京公网安备 11010502036488号