[数据结构与算法]HashMap有关面试题笔记

1，jdk1.7 采用头插法；jdk1.8采用尾插法（jdk1.8需要判断链表的长度，循环到最后一个元素，索性就把新元素插到了尾部了；为什么判断链表长度？因为要转红黑树）

2，关于元素的插入位置index，index = hashcode & (length-1)

首先，&运算速度快；length一定是2的幂次方，与运算过后，一定是个0-length之间的一个数；index计算过程中，还有一些右移，异或运算啥的，都是为了让高位能参与运算。

3，put(key,value)方法，如果覆盖原先值的话，put方法的返回值为，被覆盖额值。

4，jdk1.7是先扩容再添加；jdk1.8是先添加再扩容。

5，jdk1.8源码中的resize()方法的作用是初始化hashmap和扩容；链表长度大于8，转红黑树，小于6，红黑树转链表；为什么不是小于8转链表？防止频繁转换，节省开销，提高效率。

6，特别注意：链表长度大于8时，链表不一定转换红黑树！看好是不一定，源码中显示，如果数组的元素个数小于64，优先进行扩容；64是默认值，可以看源码确认一下。

7，经常被问的一个问题，hashmap里能不能存key为null 的值，答案是可以的，只不过只能存一个。标准答案：HashMap 允许插入键为 null 的键值对。但是因为无法调用 null 的 hashCode() 方法,也就无法确定该键值对的桶下标,只能通过强制指定一个桶下标来存放。HashMap 使用第 0 个桶存放键为 null 的键值对

8，总结：链表上的数据哈希值不一定相同（大多数情况下不相同），key值肯定不相同，当有新元素时，如果用hashcode得出的index相同，循环比较key的值，如果有相同的key值，则覆盖原来的值；如果没有相同的key值，就在链表尾部添加该元素，链表长度加1。