HashMap
HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体。 只是在JDK1.8中，链表长度大于8的时候，链表会转成红黑树！ 为什么用数组+链表？ 数组是用来确定桶的位置，利用元素的key的hash值对数组长度取模得到. 链表是用来解决hash冲突问题，当出现hash值一样的情形，就在数组上的对应位置形成一条链表。
常见面试题及解析
HashMap在什么条件下扩容?
如果bucket满了(超过load factor*current capacity)，就要resize。 load factor为0.75，为了最大程度避免哈希冲突 current capacity为当前数组大小。
为什么扩容是2的次幂?
HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法；
这个算法实际就是取模，hash%length。 但是，大家都知道这种运算不如位移运算快。
因此，源码中做了优化hash&(length-1)。 也就是说hash%length==hash&(length-1)
因为2的n次方实际就是1后面n个0，2的n次方-1，实际就是n个1。 例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞。 而长度为5的时候，3&(5-1)=0 2&(5-1)=0，都在0上，出现碰撞了。 所以，保证容积是2的n次方，是为了保证在做(length-1)的时候，每一位都能&1 ，也就是和1111……1111111进行与运算。
HashMap在并发编程环境下有什么问题啊?
(1)多线程扩容，引起的死循环问题
(2)多线程put的时候可能导致元素丢失
(3)put非null元素后get出来的却是null
你一般用什么作为HashMap的key?
此题可以组成如下连环炮来问
- 健可以为Null值么?
- 你一般用什么作为HashMap的key?
- 我用可变类当HashMap的key有什么问题?
- 如果让你实现一个自定义的class作为HashMap的key该如何实现？
键可以为Null值么?
必须可以，key为null的时候，hash算法最后的值以0来计算，也就是放在数组的第一个位置。
你一般用什么作为HashMap的key?
一般用Integer、String这种不可变类当HashMap当key，而且String最为常用。
- (1)因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就使得字符串很适合作为Map中的键，字符串的处理速度要快过其它的键对象。这就是HashMap中的键往往都使用字符串。
- (2)因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的覆写了hashCode()以及equals()方法。
我用可变类当HashMap的key有什么问题?
hashcode可能发生改变，导致put进去的值，无法get出，如下所示
HashMap<List<String>, Object> changeMap = new HashMap<>();
List<String> list = new ArrayList<>();
list.add("hello");
Object objectValue = new Object();
changeMap.put(list, objectValue);
System.out.println(changeMap.get(list));
list.add("hello world");//hashcode发生了改变
System.out.println(changeMap.get(list));
输出值如下
java.lang.Object@74a14482
null
为什么HashMap不用LinkedList,而选用数组?
因为用数组效率最高！ 在HashMap中，定位桶的位置是利用元素的key的哈希值对数组长度取模得到。此时，我们已得到桶的位置。显然数组的查找效率比LinkedList大。
那ArrayList，底层也是数组，查找也快啊，为啥不用ArrayList?
因为采用基本数组结构，扩容机制可以自己定义，HashMap中数组扩容刚好是2的次幂，在做取模运算的效率高。 而ArrayList的扩容机制是1.5倍扩容。
