【面试大纲】Java集合-HashMap
声明：以下内容纯属个人理解，有不正确之处请积极指正！
HashMap
底层是什么结构？
HashMap底层是
数组+链表+红黑树，红黑树是在JDK1.8的时候引入的，引入红黑树的目的是为了优化过长的链表，也就是说1.7之前的结构都是数组+链表。
初始化参数有哪些？
默认初始容量 DEFAULT_INITIAL_CAPACITY = 16；
默认加载因子 DEFAULT_LOAD_FACTOR = 0.75；
阈值 threshold =0；
树化阈值 TREEIFY_THRESHOLD = 8；
取消树化阈值 UNTREEIFY_THRESHOLD = 6；
扩容机制是怎样的？
扩容主要取决于调用哪个构造函数！（下文容量就是指数组的长度）
- 使用
new HashMap()来创建实例，即没有指定数组的初始容量，此时数组还是null，那么当第一次执行put(K key, V value)方法添加元素时会初始化数组的容量为默认初始容量16，同时阈值 threshold = 16 * 0.75 = 12。当数组的第13个位置添加了元素（当前数组已经有13个位置是非空，不是指数组的下标），此时数组的元素个数 size 还是12（这里还没有+1），然后判断++size>threshold（13>12）成立，触发扩容，将数组的容量设置为原容量的2倍，阈值设置为原阈值的2倍，即此时 数组.length = 32，threshold = 24。 - 使用
new HashMap(int initialCapacity)来创建实例，则设置加载因子 loadFactor = 0.75，设置阈值 threshold 为大于 initialCapacity 并且是2的幂次方的数，比如 initialCapacity = 20，则 threshold = 25 = 32（源码中是通过移位和或运算实现的，具体实现在 tableSizeFor(int cap) 方法）；那么当第一次执行put(K key, V value)方法添加元素时会初始化数组的容量为 threshold 的值，所以当显示指定数组的容量时，底层并不会按照你指定的容量来初始化数组，而是将数组的容量初始化为大于指定值并且是2的幂次方的值。然后当数组的第 25 个位置添加了元素（当前数组已经有25个位置是非空，不是指数组的下标），此时数组的元素个数 size 还是24（这里还没有+1），然后判断++size>threshold（25>24）成立，触发扩容，将数组的容量设置为原容量的2倍，阈值设置为原阈值的2倍，即此时 数组.length = 64，threshold = 48。
上面就是 HashMap 常用的两种创建方式并且相应的扩容方式，对照源码可能会更容易理解。
是否线程安全？
非线程安全！
若要使用线程安全Map的可以考虑使用 Collections.synchronizedMap() 或 ConcurrentHashMap。
如何保证hash散列？或者说如何避免hash碰撞？
(1). 首先要找到元素存储在数组中的位置
找到数组的位置是通过一个简单的计算，即tab[i = (n - 1) & hash]，等价于根据hash函数计算出的 hash 值对数组的长度也就是 length 取余，但取余的计算效率没有位运算高，所以(n - 1) & hash也算是神来之笔，一个小的优化吧！
(2). 其次就是上面提到的hash函数，通过对 key 进行两次hash运算，增加hash复杂度。
- 第一次：先计算
h = key.hashCode(); - 第二次：计算
h ^ (h >>> 16)，这里右移16位的意义何在？因为 h 这里是int类型，int在java中占4个字节，每个字节是8位，也就是32位，前16位为高位，后16位为低位，计算余数时（紧跟第(1)步），由于 n 比较小，hash 只有低16位参与了计算，高位的计算可以认为是无效的。这样导致了计算结果只与低位信息有关，高位数据没发挥作用。为了处理这个缺陷，我们可以让 hash 的高16位数据与低16位数据进行异或运算，即 hash ^ (hash >>> 16)。通过这种方式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参与到计算中。
使用场景有哪些？
需要存储 键值对 key-value 类型数据时适用。
使用时要注意什么？
重写equals和hashCode方法！！！
当我们用HashMap存入自定义的类时，如果不重写这个自定义类的equals和hashCode方法，得到的结果会和我们预期的不一样。当然了，这里主要指的是HashMap的key部分！
对于HashMap，一般面试能说出这些应该也差不多了，如果是高级面试，对于红黑树以及HashMap的更详细实现要是能跟面试官侃侃而谈当然是最好不过了！
常用Map类的不同？
Map中常用的有 HashMap、LinkedHashMap、TreeMap。
-
HashMap
底层是数组+链表+红黑树结构； -
LinkedHashMap
它是继承自HashMap的，也就是说基本和HashMap类似，唯一的不同点就是它的底层是数组+双向链表+红黑树，引入双向链表的目的是保证你插入map的元素的顺序和你遍历出来的元素的顺序是一致的，这一点HashMap并没有保证！ -
TreeMap
它的底层是红黑树结构的；
遍历得到的元素是升序排列的。
上面小结的也只是我目前了解的一些，如果想要了解更多，可以参考下面的几篇博文，写的很棒，分析的也很透彻！
参考：
