面试必问之HashMap
问题1 hashmap原理？
问题1.1 hashmap底层数据结构是什么
哈希表结构（链表散列：数组+链表）实现，结合数组和链表的优点。当链表长度超过 8 时，链表转换为红黑树。
问题1.2 jdk1.8为啥要将链表转为红黑树呢？
链表的用的是线性检索，时间复杂度是O(n)，而红黑树的检索方式是二分查找，平均时间复杂度是O(logn)，当达到一定阈值后，二分查找是由于先行检索的
问题1.3 什么情况下会将链表转为红黑树
当来链表长度达到8时会转为红黑树，当桶中链表元素个数小于等于6时，树结构还原成链表。因为红黑树的平均查找长度是log(n)，长度为8的时候，平均查找长度为3，如果继续使用链表，平均查找长度为8/2=4，这才有转换为树的必要。链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
还有选择6和8，中间有个差值7可以有效防止链表和树频繁转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。
问题1.4 能说一下什么是红黑树吗？
红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树，则它的任一子树必为红黑树. 红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但 对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。 红黑树有5个原则：
- 每个节点是红色或者黑色的
- 根节点必须是黑色的
- 每个叶子节点都是黑色的空节点（NIL节点），即叶子节点不存储数据
- 红色节点的两个子节点必须都是黑色的（即路径中不能存在两个连续的红色节点）
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
定义了两个属性：节点的 黑深 以及 树的 黑高。 根据维基百科的定义， 节点的黑深指 从根节点到该节点的任意路径中黑色节点的数量。 树的黑高指 从根节点到叶子节点的任意路径上的黑色节点数量。 红黑树通过3种操作来维持自身的平衡（插入或删除节点后） —变色，左旋，右旋
问题1.5 还有其他集合的数据结构是红黑树吗？
treemap、hashset
问题1.6 红黑树能替换为二叉查找树吗？
不能，因为在特定条件下二叉树可能会退化为线性结构
问题2 hashmap在什么条件下扩容
- HashMap在什么条件下扩容?
- 为什么扩容是2的n次幂?
- 为什么要先高16位异或低16位再取模运算?
问题2.1 HashMap在什么条件下扩容?
如果bucket满了(超过load factor*current capacity)，就要resize。 load factor为0.75，为了最大程度避免哈希冲突 current capacity为当前数组大小。
问题2.2 为什么扩容是2的n次幂?
HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法 这个算法实际就是取模，hash%length。 但是，大家都知道这种运算不如位移运算快。 因此，源码中做了优化hash&(length-1)。 也就是说hash%length==hash&(length-1)
问题2.3 为什么要先高16位异或低16位再取模运算?
来看一下jdk1.8里的hash方法源码。1.7的比较复杂，就不看了。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}hashmap这么做，是为了降低hash冲突的几率。
问题3 讲一讲hashmap的get/put的过程
hashmap put过程： 对key的hashCode()做hash运算，计算index; 如果没碰撞直接放到bucket里； 如果碰撞了，以链表的形式存在buckets后； 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树(JDK1.8中的改动)； 如果节点已经存在就替换old value(保证key的唯一性) 如果bucket满了(超过load factor*current capacity)，就要resize。
hashmap get过程： 对key的hashCode()做hash运算，计算index; 如果在bucket里的第一个节点里直接命中，则直接返回； 如果有冲突，则通过key.equals(k)去查找对应的Entry; • 若为树，则在树中通过key.equals(k)查找，O(logn)； • 若为链表，则在链表中通过key.equals(k)查找，O(n)。
问题4 HashMap并发问题
问题4.1 HashMap 和 HashTable 有什么区别？
①、HashMap 是线程不安全的，HashTable 是线程安全的； ②、由于线程安全，所以 HashTable 的效率比不上 HashMap； ③、HashMap最多只允许一条记录的键为null，允许多条记录的值为null，而 HashTable 不允许； ④、HashMap 默认初始化数组的大小为16，HashTable 为 11，前者扩容时，扩大两倍，后者扩大两倍+1； ⑤、HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode
问题4.2 HashMap在并发过程中可能遇到什么问题
- 多线程put的时候可能导致元素丢失
- put非null元素后get出来的却是null
- 多线程put后可能导致get死循环
问题4.3 怎么得到线程安全的HashMap
一般情况下可以使用下面三种集合来替换hashMap，性能最好是ConcurrentHashMap
- HashTable (直接new)
- SynchronizedMap （Collections.synchronizedMap(new HashMap)）
- ConcurrentHashMap （直接new）
以上的三个都能在并发情况下正常工作，性能不同主要是体现在锁粒度方面 这三个都使用了synchrnized 关键字。 其中HashTable、SynchronizedMap 是直接锁住当前对象，不管是get、put都需要排队。 而ConcurrentHashMap JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基于 Segment，包含多个 HashEntry。 JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry<k,v>）。锁粒度降低了。 </k,v>