记一次HashMap面试
从网上已经身边同事朋友的面试情况来看，面试
HashMap几乎是必问的，网上也很多类似的文章，但是真面起来，发现还是有很多点可以深抠的。本篇就结合一次面试经历说一下之前没有注意的点吧。
HashMap的底层结构
这个相信不用我多说，大家都知道HashMap的底层是Node数组结构Node<K,V>[] table。
扩容也不用我多说了，在size达到阈值（默认0.75的负载因子*容量）时触发扩容。
数组的capacity大小是2的x幂也无需多言，但这里多问一句为什么是2的x幂而不是其他数呢？我们知道，当一个key被放进到数组时需要明确自己被放在哪个位置。最简单的当然就是对key进行hash之后h%n确定。而如果数组的长度n是2的x幂，h%n这个操作与h&(n-1)是等价的，会更快。同时在扩容时，每个key需要重新确定自己在数组中的index，这时如果数组每个位置的元素都变了一次，显然开销会比较大。但是如果n是2的x幂，那么在扩容变成2n后需要重新确认index时，对某个table[index]这个元素的新位置只有两种可能：1. 在原地不动（如果h&n的高位为0），2. index+n（h&n的高位为1）。这样每个元素移动的概率只有50%，显然会节约很多拷贝操作。
HashMap中链表转红黑树
这个也是高频问点，大家也基本都清楚，JDK1.8之后，如果某位置的链表长度大于某个阈值之后，就会转为红黑树，防止链表深度过大，从而查询时复杂度达到o(n)最坏情况。但是细问起来，如果没有认真看过putVal方法中每一行代码，真的有的地方可能会忽略。比如：
- 链表长度达到多少之后开始转链表？你可能脱口而出8。但真的超过这个阈值8之后就会转树吗？我们跟进代码后会发现：还有另一个条件，即数组的长度如果小于
MIN_TREEIFY_CAPACITY默认64这个值，会触发一次扩容而并不会执行转树操作，所以链表的长度是可以超过8的。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}- 在转成红黑树时，每个
key应该放在左子树还是右子树？这个由什么确定？因为HashMap的key并不要求是Comparable，而TreeMap很显然key是要满足Comparable的，那么此时新来一个TreeNode，左右确定以什么为依据呢？
面试时在次数被面试官坑了一把，其实我们仔细想想，我们并不需要严格的确定某个TreeNode应该挂在它父节点的左边还是右边，挂在哪边都可以啊，只要我插入时按某个标准，查找时也按同样的标准，两者保持一致就可以了，对吧？跟到源代码，对于没有实现Comparable的key，比较一下hashCode就可以了。源码中的比较一句就是两个key的hashCode，使用的是System.identityHashCode(object)这个native方法。
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}后记
还有大家都耳熟能详的东西我就不赘述了，面后也思考了一下，基础还是很重要，还是有很多指的深入思考的地方，一定要打牢基础，可能准备了很多框架原理实践什么的，如果基础的没答好，这些应用层的东西准备的再好，可能也没机会跟面试官聊了，当然在面试中如何去引导面试官这一点也很重要，俗话说的好，把对方拉倒跟我一个低智商区，然后用我丰富的经验打败他，这一点很重要，以后要多注意。