为什么HashMap的加载因子是0.75呢？

加载因子指的是，实际个数/容量，实际个数指的是key-value对，容量指的是桶的数量

答：
从实际上考虑：加载因子过高，例如为1，虽然减少了空间开销，提高了空间利用率，但同时也增加了查询时间成本；

加载因子过低，例如0.5，虽然可以减少查询时间成本，但是空间利用率很低，同时提高了rehash操作的次数。

在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少rehash操作次数，所以，一般在使用HashMap时建议根据预估值设置初始容量，减少扩容操作。

选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折衷选择，

从统计学上考虑：

因为在加载因子为0.75的条件下，链表的长度与概率符合泊松分布，而当长度为8时，概率已经是0.00000006，基本上已经是不可能事件了，所以选择这个参数作为加载因子

HashMap的扩容过程（虽然阈值是通过数组大小×负载因子得到的，但是实际上是添加的节点数大于阈值，就回扩容）？

答：

1. JDK7中的扩容机制（先插入，后扩容，两次hash）

JDK7的扩容机制相对简单，有以下特性：

• 空参数的构造函数：以默认容量、默认负载因子、默认阈值初始化数组。内部数组是空数组。
• 有参构造函数：根据参数确定容量、负载因子、阈值等。
• 第一次put时会初始化数组，其容量变为不小于指定容量的2的幂数。然后根据负载因子确定阈值。
• 如果不是第一次扩容，则新容量=久容量×2 新阈值＝新容量×负载因子

2. JDK8的扩容机制（先扩容，在插入，一次hash）

JDK8的扩容做了许多调整。

HashMap的容量变化通常存在以下几种情况：

1. 空参数的构造函数：实例化的HashMap默认内部数组是null，即没有实例化。第一次调用put方法时，则会开始第一次初始化扩容，长度为16。
2. 有参构造函数：用于指定容量。会根据指定的正整数找到不小于指定容量的2的幂数，将这个数设置赋值给阈值（threshold）。第一次调用put方法时，会将阈值赋值给容量，然后让阈值 ＝容量负载因子*。（因此并不是我们手动指定了容量就一定不会触发扩容，超过阈值后一样会扩容！！）
3. 如果不是第一次扩容，则容量变为原来的2倍，阈值也变为原来的2倍。（容量和阈值都变为原来的2倍时，负载因子还是不变）

此外还有几个细节需要注意：

• 首次put时，先会触发扩容（算是初始化），然后存入数据，然后判断是否需要扩容；
• 不是首次put，则不再初始化，直接存入数据，然后判断是否需要扩容；

JDK7的元素迁移

JDK7中，HashMap的内部数据保存的都是链表。因此逻辑相对简单：在准备好新的数组后，map会遍历数组的每个“桶”，然后遍历桶中的每个Entity，重新计算其hash值（也有可能不计算），找到新数组中的对应位置，以头插法插入新的链表。

这里有几个注意点：

是否要重新计算hash值的条件这里不深入讨论，读者可自行查阅源码。
因为是头插法，因此新旧链表的元素位置会发生转置现象。
元素迁移的过程中在多线程情境下有可能会触发死循环（无限进行链表反转）。

JDK8的元素迁移
JDK8则因为巧妙的设计，性能有了大大的提升：由于数组的容量是以2的幂次方扩容的，那么一个Entity在扩容时，新的位置要么在原位置，要么在原长度+原位置的位置。原因如下图：

移位图

例子

JDK8的HashMap还有以下细节：

JDK8在迁移元素时是正序的，不会出现链表转置的发生。
如果某个桶内的元素超过8个，则会将链表转化成红黑树，加快数据查询效率。

为什么HashMap1.7用头插法，而1.8用尾插法？

答：因为在多线程的情况下，扩容的时候可能会导致链表成环，因为头插法的话再重新Hash后插入的时候，顺序是跟原来相反的具体例子看参考链接

JDK1.8对hash算法进行了哪些优化？

1、hash算法：JDK1.7中通过key.hashcode()得到关键字的hash值，JDK1.8将hash值的高16位与低16位进行异或运算，使得hash值的低16位同时保留高16位和低16位的特征，对于两个hash值低16位相等，高16位不等的情况，减少hash冲突。

2、寻址算法：JDK1.7位hash值对数组长度进行取模运算，JDK1.8变为hash&(n-1)，n为数组长度。当数组长度是2的幂次时，hash值对数组长度取模和hash&(n-1)的效果是一样的，但是与运算的性能更高。

为什么HashMap的数组长度要取2的整数幂？

答：首先我们要知道key散列到相应的数组下标的hash规则，就是index=key&（N-1），其实本来是index%N，换成这样首先是因为位运算更快，因为比如16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。也就是取值是0-15，这也就相当于%的效果了。

为什么采用hashcode的高16位和低16位异或能降低hash碰撞？hash函数能不能直接用key的hashcode？

答：因为 key.hashCode() 函数调用的是key键值类型自带的哈希函数，返回int型散列值。int值范围为-2147483648~2147483647，前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。你想，如果HashMap数组的初始大小才16，用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。比如说0 到10000的散列空间，如果是1 1001 2001 3001 ...... 这样在整个散列空间上是非常均匀的，但是一旦的取余了100了之后呢，全部冲突。
但这时候问题就来了，这样就算我的散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。更要命的是如果散列本身做得不好，分布上成等差数列的漏洞，如果正好让最后几个低位呈现规律性重复，就无比蛋疼。
右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

Java中HashMap、LinkedHashMap和TreeMap区别使用场景？

答：
1. HashMap：不是按照插入顺序，也不是按照大小顺序。单纯用来统计
2.LinkedHashMap：它内部有一个链表，保持Key插入的顺序。迭代的时候，也是按照插入顺序迭代，而且迭代比HashMap快。
3. TreeMap：顺序是Key的自然顺序（如整数从小到大），也可以指定比较函数。但不是插入的顺序。

HashMap的默认容量（1.7与1.8）全都是16吗？为什么是16？初始容量300的HashMap，加301个元素（map扩容几次）？

答：为什么是16呢我个人觉得这个是经验得来的，因为我们这个容量的大小，如果太小的话，那么会导致冲突的几率快，并且会经常扩容，但是如果太大的话，又会导致空间浪费，所以我们的容量设置主要是要在这两个方面去均衡，所以一般如果我们明确知道我们的Map数量最集中的取间是在哪，我们初始化的时候就设置容量会比较好。

红黑树为什么比链表查找快？

答：

1. 因为链表是线性表吗，每次查询都得遍历整个链表直到查询到想要的数据。是o（n）
2. 红黑树呢，是一种特殊的二叉查找树，二叉查找树，比如有完全二叉树，他的查询次数就是他的高度，但是这种维护成本太高了，所以就有了红黑树，红黑树的要求就没完全二叉树那么高了，但是他有一个特性，就是从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点，从每个叶子到根的所有路径上不能有两个连续的红色结点，那么这就可以知道红黑树的最长查询距离不会超过最短查询距离的两倍，那么就可以知道红黑树的查询时间复杂度为2log（n），这就大大提升了效率