1、HashMap的数据结构是什么？
答：在jdk1.7是采用了数组+链表；jdk1.8采用了数组+链表+红黑树，当链表长度大于等于的时候转化为红黑树，当红黑树的结点小于等于6的是时候就有红黑树转化为链表；
2、为什么要采用数组+链表作为存储结构？
首先要清楚一个基本的理论：数组查询效率高，只要给一个数组索引就可以立马找到对应的元素，但是插入、删除的效率低；链表插入、删除的效率高，但是查询的效率低。
因此HashMap的Node数组就可以通过一个索引值(index=(n-1)&hash)立即定位到确定到元素的槽位（solt）。但是可能有多个key的hashCode计算出来一样 即发生Hash碰撞，此时HashMap采用了拉链法，即以table数组这个槽位为链表头结点，把发生hash碰撞元素串在一根链表上。而且在jdk1.8进行了进一步优化，即如果链表的长度>=8时将会转化为红黑树，当红黑树上的结点<=6时又会转换为链表。这一点从源码中就可以看到：
TREEIFY_THRESHOLD是树化阈值为8，UNTREEIFY_THRESHOLD是非树化阈值为6
3、你知道 hash 的实现吗？为什么要这样实现(为什么要用异或运算符)？
jdk1.8的hash值是通过对key的hashCode的高16位和低16位进行异或得到的：hash=(h=key.hashCode())^(h>>>16) ;这样实现可以让高位的数字也可以参与到hash值的计算，从而使得哪怕一点变化都会引起hash函数有很大的不同，最终目的还是为了尽可能的实现hash函数的均匀分布。
4、说一下HashMap的put和get的工作原理？
HashMap 底层是 hash 数组和单向链表实现，数组中的每个元素都是链表，由 Node 内部类（实现 Map.Entry<K,V>接口）实现，HashMap 通过 put 和 get 方法存储和获取。
存储对象时，将 K/V 键值传给 put() 方法：
（1）调用 hash(K) 方法计算 K 的 hash 值，然后结合数组长度，计算得数组下标；
（2）调整数组大小（当容器中的元素个数大于 capacity * loadfactor 时，容器会进行扩容resize 为 2n）；
（3）i.如果 K 的 hash 值在 HashMap 中不存在，则执行插入，若存在，则发生碰撞；
ii.如果 K 的 hash 值在 HashMap 中存在，且它们两者 equals 返回 true，则更新键值对；
iii. 如果 K 的 hash 值在 HashMap 中存在，且它们两者 equals 返回 false，则插入链表的尾部（尾插法）或者红黑树中（树的添加方式）。
（JDK 1.7 之前使用头插法、JDK 1.8 使用尾插法）
（注意：当碰撞导致链表大于 TREEIFY_THRESHOLD = 8并且哈希表的容量大于64时，就把链表转换成红黑树，否则即使链表的长度大于8了，也不会立即将链表转化为红黑树，而是使用扩容来解决）
获取对象时：
（1）get()方法将键值对传入，首先还是计算key的hash值
（2）拿到hash值首先判断一下头结点是不是要找的元素，如果是直接返回value；如果不是就看看头结点是否有后继结点，如果没有就返回null
（3）如果头结点有后续结点那就判断如果头结点的类型如果是树就调用红黑树的获取值的方法getTreeNode()，否则还是当做链表处理，从头结点开始遍历，知道hash值相等并且equals返回true是就说明找到目标元素了。
hashCode 是定位的，存储位置；equals是定性的，比较两者是否相等。
5、HashMap扩容的原理？
HashMap的扩容过程总的来说分为两个过程：
- 根据老哈希表的大小计算出新哈希表的新容量以及新阈值，并创建一个新的Node空数组，长度是原数组的2倍
- 遍历原Entry数组，把所有的Entry重新Hash到新数组。 核心思路：遍历老的哈希表，没有元素的槽位不管，只处理有元素的槽位；处理有元素的槽位的逻辑分为三大部分：
1）如果这个槽位没有后继结点了（没有形成链表），就重新计算元素移动到新的哈希表中位置并直接移动过去，重新计算桶位的算法还是：
e.hash&(newCap-1)2）如果槽位有后继结点并且已近树化了（已经是红黑树了），那就将红黑树拆分后，在新的哈希表中重新hash并散列到新的Node数组中
3）如果槽位有后继结点但是没有树化（已经是链表了），那就还是用尾插法把元素移动到新的哈希表中，需要注意的是：
A：扩容后，若e.hash&oldCap=0，那么元素在扩容后的位置=原始位置(newTab[j] = loHead)
B：扩容后，若hash&oldCap!=0，那么元素在扩容后的位置=原始位置+旧数组大小( newTab[j + oldCap] = hiHead)。
6、HashMap 的 table 的容量如何确定？loadFactor 是什么？ 该容量如何变化？这种变化会带来什么问题？
（1）HashMap的table数组的容量是通过capaticy参数控制的，默认的数组大小是16，最大额数组大小是2^30。我们可以在HashMap的构造方法中传入指定的容量数值，尤其是数据量大的时候指定初始容量非常有必要。
（2）loadFatory是装载因子，作用是判断当前哈希表是否可以扩容了。范围是0-1，默认是0.75.和他类似的一个参数是阈值threshold，在一切都是默认值的情况下，阈值是12
（3）扩容时，调用 resize() 方法，将 table 长度变为原来的两倍（注意是 table 长度，而不是 threshold）
这一问之后有可能会再问，加载因子默认为什么设置为0.75？
**选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折衷选择， **
加载因子过高，例如为1，虽然减少了空间开销，提高了空间利用率，但同时也增加了查询时间成本；
加载因子过低，例如0.5，虽然可以减少查询时间成本，但是空间利用率很低，同时提高了rehash操作的次数。
7、说说你对红黑树的了解？
红黑树是一种自平衡的二叉查找树，但是每个节点上增加一个存储位表示节点的颜色（红色或黑色），红黑树的查找、删除、插入操作最坏的时间复杂度都可以达到O(lgn)。
总的来说，红黑树除了符合二叉查找树的基本特性外，还具有以下几个特性：
- 红黑树的结点是红色的或黑色的；
- 红黑树的根节点是黑色的；
- 叶子节点（NULL结点）都是黑色的；
- 每个红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）；
- 从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点；
- 新加入到红黑树的节点为红色节点。
8、为什么在jdk1.8要使用红黑树，使用二叉搜索树或者平衡树不可以吗？
- （1）二叉搜索树在给定的数据有序时会出现退化为链表的情况
二叉搜索树的思想是：左子树结点比父节点小，右子树结点比父节点大。当给的数据处于无序状态的时候二叉搜索树的性能非常好，只有O(logn)，但是当给的数据有序的时对于二叉搜索树是灾难，基于二叉搜索树规则构建的树会退化为单链表。即如下图所示：
- （2）平衡树的维护成本太高，不适合HashMap这样有频繁修改的的场景。
平衡树(AVL)就是用来解决二叉搜索树会退化为链表对问题二提出的。它的原理如下：
a. 平衡树具有二叉搜索树的全部特性
b. 平衡树要求左子树和右子树的高度差不能超过1
通过平衡树，我们解决了二叉查找树的缺点。对于有 n 个节点的平衡树，最坏的查找时间复杂度也为 O(logn)。 但是由于平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个 要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过 左旋 和 右旋 来进行调整，使之再次成为一颗符合要求的平衡树。
最后就会导致为了维护一个这个平衡树，带来了可能比只是用单链表还高的消耗，这时不可取得。因此为了解决这个问题，工程师们又想到了红黑树。红黑树的性质如下：
a. 具有二叉查找树数的所有特点
b.根节点是黑色的
c.每个叶子节点都是黑色的空节点，即叶子节点不存值
d.任意相邻的结点都不能是相同的颜色
e.任意结点到其任意叶子节点的路径上的黑色结点的数目相同
正是由于红黑树的这些特性，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁调整。但是在效率方面，红黑树确实不及平衡树，可以说使用红黑树就是一种折中的方案。
9、为什么不直接上来就使用红黑树，而是达到阈值了才转化为红黑树？
-
首先维护一个树的成本比维护一个链表的成本要高。
-
再者设置链表树化的阈值为8是因为链表的长度达到8的概率很低，看HashMap源码中的一段注释：
画红线的翻译过来就是说：在具有良好分布的用户hashCode的用法中，很少使用到红黑树。 理想情况下，在随机hashCodes下，bin中节点的 频率遵循泊松分布 ，默认调整大小阈值为0.75，平均参数约为0.5，尽管 由于存在较大差异调整粒度。 忽略差异，预期列表大小k的出现是**（exp（-0.5）* pow（0.5，k）/阶乘（k）**）。
也就是说，想让一个链表的长度达到8的概率极低，几乎是不可能事件。
因此综合这两点，为啥一定要维护一个红黑树呢？没必要啊！！！
10、jdk1.7和jdk1.8中HashMap有哪些不同？
（1）在jdk1.8中当链表的长度大于等于8的时候会转换诶红黑树；
（2）jdk1.8中采用的是尾插法，而jdk1.7中采用的是头插法；
（3）jdk1.8简化了hash算法；
（4）jdk1.8修改了resize()的逻辑，使得jdk1.8在resize时不会出现循环链表的问题；
（5）jdk1.8中talbe数组的类型改为了Node，jdk1.7中的类型是Entry类型；
如果你说了jdk1.8中采用的是尾插法，而jdk1.7中采用的是头插法，人家就会问jdk1.8为啥使用尾插法？
- 首先是为了解决在多先线程环境下由于头插法带来的形成环形链表的问题；
- 在jdk1.8中引入了红黑树，为了统计链表总的结点个数，以便判断是否需要树化，于是他就遍历了一遍链表并使用一个binCount的变量计数，当遍历完之指针就是在最后一个节点上指着呢，采用尾插顺理成章。
11、HashMap，LinkedHashMap，TreeMap 有什么区别？
LinkedHashMap是HashMap的子类，他维护了一个双向链表，因此他可以保证元素的插入顺序和元素的遍历顺序是相同的；效率比HashMap低。
TreeMap就是一个红黑树的实现，实现 SortMap 接口，能够把它保存的记录根据键排序
12、HashMap和Hashtable的区别？
（1） HashMap的基类是AbstractMap, Hashtable的基类是Dictionary, 他们共同实现了Map接口
（2）HashMap的初始容量是16，Hashtable的初始容量都是11,负载因子都是0.75。但是扩容机制不同, HashMap是旧数组的2×旧表长度, 而Hashtable是2×旧表长度+1
（3） HashMap是非线程安全的，而Hashtable是线程安全的，因为所有的方法都使用了synchronized.
（4） HashMap使用迭代器迭代, Hashtable可以使用迭代器和枚举。
（6） HashMap中K和V都可以是null（存放在table[0]）,但是Hashtable中都不能是null.
（7） HashMap中取消了contains方法，使用了containsKey和containsValue,但是Hashtable中三个方法都有
（9）对象的定位方法不同:
- Hashtable:使用K的hashCode直接作为hash值,和数组长度进行求余运算,得到键值对在数组中的位置,然后再使用equals方法形成链表。
- HashMap:使用K的hashCode进行高低16位异或运算作为hash值,和数组的长度减一进行&运算， 得到键值对在数组中的位置，然后再使用equals方法形成链表。说一下计算桶的位置为什么是这个样子，就是因为扩容的时候是2的n次方进行扩容, hash值在和2的n次方进行求余运算和&运算的结果一样, 但是&运算要快的多。同时正是因为扩容倍数的特殊性，导致扩容后不需要重新键值对在新数组的位置只需要判断K的hash值多出来的那一位是0还是1. 如果是0, 新表中键值对的位置和旧表-样。 如果是1,新表中键值对的位置等于旧表的位置+旧表的长度。
（9）Hashtable由于是线程安全的，因此采用了一种快速失败的机制。允许多个线程同时修改但不会抛出异常；HashMap采用了一种安全失败机制的机制，他不允许在遍历元素的时候，集合发生改，如果发生改变就会抛出异常。
13、Java 中的另一个线程安全的与 HashMap 极其类似的类是什么？同样是线程安全，它与 Hashtable 在线程同步上有什么不同？
ConcurrentHashMap是J.U.C下提供的一个并发容器，他是HashMap的线程安全版本，采用分段锁提高了效率，但是在Hashtable中是将整个hash表使用synchronized锁起来，并发性没有前者好。
- JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基于 Segment，包含多个 HashEntry。
- JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry<K,V>）。锁粒度降低了
