HashMap
Q0：HashMap是如何定位下标的？
A：先获取Key，然后对Key进行hash，获取一个hash值，然后用hash值对HashMap的容量进行取余（实际上不是真的取余，而是使用按位与操作，原因参考Q6），最后得到下标。
Q1：HashMap由什么组成？
A：数组+单链表，jdk1.8以后又加了红黑树，当链表节点个数超过8个（m默认值）以后，开始使用红黑树，使用红黑树一个综合取优的选择，相对于其他数据结构，红黑树的查询和插入效率都比较高。而当红黑树的节点个数小于6个（默认值）以后，又开始使用链表。这两个阈值为什么不相同呢？主要是为了防止出现节点个数频繁在一个相同的数值来回切换，举个极端例子，现在单链表的节点个数是9，开始变成红黑树，然后红黑树节点个数又变成8，就又得变成单链表，然后节点个数又变成9，就又得变成红黑树，这样的情况消耗严重浪费，因此干脆错开两个阈值的大小，使得变成红黑树后“不那么容易”就需要变回单链表，同样，使得变成单链表后，“不那么容易”就需要变回红黑树。
Q2：Java的HashMap为什么不用取余的方式存储数据？
A：实际上HashMap的indexFor方法用的是跟HashMap的容量-1做按位与操作，而不是%求余。（这里有个硬性要求，容量必须是2的指数倍，原因参考Q6）
Q3：HashMap往链表里插入节点的方式？
A：jdk1.7以前是头插法，jdk1.8以后是尾插法，因为引入红黑树之后，就需要判断单链表的节点个数（超过8个后要转换成红黑树），所以干脆使用尾插法，正好遍历单链表，读取节点个数。也正是因为尾插法，使得HashMap在插入节点时，可以判断是否有重复节点。
Q4：HashMap默认容量和负载因子的大小是多少？
A：jdk1.7以前默认容量是16，负载因子是0.75。
Q5：HashMap初始化时，如果指定容量大小为10，那么实际大小是多少？
A：16，因为HashMap的初始化函数中规定容量大小要是2的指数倍，即2，4，8，16，所以当指定容量为10时，实际容量为16。
Q6：容量大小为什么要取2的指数倍？
A：两个原因：1，提升计算效率：因为2的指数倍的二进制都是只有一个1，而2的指数倍-1的二进制就都是左全0右全1。那么跟（2^n - 1）做按位与运算的话，得到的值就一定在【0,（2^n - 1）】区间内，这样的数就刚合适可以用来作为哈希表的容量大小，因为往哈希表里插入数据，就是要对其容量大小取余，从而得到下标。所以用2^n做为容量大小的话，就可以用按位与操作替代取余操作，提升计算效率。2.便于动态扩容后的重新计算哈希位置时能均匀分布元素：因为动态扩容仍然是按照2的指数倍，所以按位与操作的值的变化就是二进制高位+1，比如16扩容到32，二进制变化就是从0000 1111（即15）到0001 1111（即31），那么这种变化就会使得需要扩容的元素的哈希值重新按位与操作之后所得的下标值要么不变，要么+16（即挪动扩容后容量的一半的位置），这 样就能使得原本在同一个链表上的元素均匀（相隔扩容后的容量的一半）分布到新的哈希表中。（注意：原因2（也可以理解成优点2），在jdk1.8之后才被发现并使用）
Q7：HashMap满足扩容条件的大小（即扩容阈值）怎么计算？
A：扩容阈值=min(容量负载因子,MAXIMUM_CAPACITY+1)，MAXIMUM_CAPACITY非常大，所以一般都是取（容量负载因子）
Q8：HashMap是否支持元素为null？
A：支持。
Q9：HashMap的 hash(Obeject k)方法中为什么在调用 k.hashCode()方法获得hash值后，为什么不直接对这个hash进行取余，而是还要将hash值进行右移和异或运算？
A：如果HashMap容量比较小而hash值比较大的时候，哈希冲突就容易变多。基于HashMap的indexFor底层设计，假设容量为16，那么就要对二进制0000 1111（即15）进行按位与操作，那么hash值的二进制的高28位无论是多少，都没意义，因为都会被0&，变成0。所以哈希冲突容易变多。那么hash(Obeject k)方法中在调用 k.hashCode()方法获得hash值后，进行的一步运算：h=(h20)(h12);有什么用呢？首先，h20和h12是将h的二进制中高位右移变成低位。其次异或运算是利用了特性：同0异1原则，尽可能的使得h20和h12在将来做取余（按位与操作方式）时都参与到运算中去。综上，简单来说，通过h=(h20)(h12);运算，可以使k.hashCode()方法获得的hash值的二进制中高位尽可能多地参与按位与操作，从而减少哈希冲突。
Q10：哈希值相同，对象一定相同吗？对象相同，哈希值一定相同吗？
A：不一定。一定。
Q11：HashMap的扩容与插入元素的顺序关系？
A：jdk1.7以前是先扩容再插入，jdk1.8以后是先插入再扩容。
Q12：HashMap扩容的原因？
A：提升HashMap的get、put等方法的效率，因为如果不扩容，链表就会越来越长，导致插入和查询效率都会变低。
Q13：jdk1.8引入红黑树后，如果单链表节点个数超过8个，是否一定会树化？
A：不一定，它会先去判断是否需要扩容（即判断当前节点个数是否大于扩容的阈值），如果满足扩容条件，直接扩容，不会树化，因为扩容不仅能增加容量，还能缩短单链表的节点数，一举两得。
反向阈值：当红黑树只有6个节点，那么就改成链表。为什么是6？防止在同一个位置频繁的插入删除
|