一. 基础知识
1.1 什么是hashMap？
HashMap是我们非常常用的数据结构，由数组和链表组合构成的数据结构。数组里面每个地方都存了Key-Value的实例，在Java7叫Entry，在Java8中叫Node。
1.2 特点
1、线程不安全 2、动态扩容 3、默认容量16 4、负载因子为 0.75
1.3 HashMap的底层数据结构
JDK 1.7
大方向上，HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。每一个节点都会保存自身的hash、key、value、以及下个节点，
JDK 1.8
- Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树 组成。
- java8之前是头插法，就是说新来的值会取代原有的值，原有的值就顺推到链表中去，但是，在java8之后，都是所用尾部插入。
二. 面试题
2.1 Java8 为什么要引入红黑树？
根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。为了降低这部分的开销，在 Java8 中，当链表中的元素达到了 8 个时，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。
2.2 1.8之后为什么要改成尾部插入？
使用头插会改变链表上数据的顺序，链表上的数据会下移。在多线程的环境下，容易形成环形链表。但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。
2.3 HashMap的存取过程
get
查询数据相对来说就比较简单了，首先计算出hash值，然后去数组查询，是红黑树就去红黑树查，链表就遍历链表查询就可以了。
put
往map插入元素的时候首先通过对key hashcode, 然后与数组长度-1 进行位运算(&) ((n-1)&hash)，找到数组中的位置之后，如果数组中没有元素直接存入，反之则判断key是否相同，key相同就覆盖，否则就会插入到链表的尾部，如果链表的长度超过8，则会转换成红黑树，最后判断数组长度是否超过默认的长度*负载因子也就是12，超过则进行扩容。
2.4 HashMap是怎么扩容的呢？
两个因素会影响hashMap的扩容：Capacity：HashMap当前长度。LoadFactor：负载因子：0.75f。就比如当前的容量大小为100，当你存进第76个的时候，那就进行扩容。扩容的过程分为两步1、扩容：创建一个新的Entry空数组，长度是原数组的2倍。2、ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。
2.5 扩容之后为什么要重新Hash呢，为什么不直接复制过去？
是因为长度扩大以后，Hash的规则也随之改变。Hash的公式---> index = HashCode（Key） & （Length - 1）原来长度（Length）是8你位运算出来的值是2 ，新的长度是16你位运算出来的值明显不一样了。
2.6 hashMap为什么线程不安全？
虽然1.8已经将头插改成了尾插，那不是意味着Java8就可以把HashMap用在多线程中。因为不会出现死循环了，但是通过源码看到put/get方法都没有加同步锁，多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全还是无法保证。
2.7 既然hashMap是线程不安全的，有什么方法可以获得一个线程安全的吗
1、hashtable 2、Collections.synchronizedMap() 3、ConcurrentHashMap
2.8 HashMap默认初始化大小是多少？为啥是这么多？为啥大小都是2的幂
HashMap作为一种数据结构，元素在put的过程中需要进行hash运算，目的是计算出该元素存放在hashMap中的具体位置，公式： hashcode(key) & (length-1)。hash运算的过程其实就是对目标元素的Key进行hashcode，再对Map的容量进行取模，公式：hashcode(key)%length
Java之所有使用位运算(&)来代替取模运算(%)，最主要的考虑就是效率。位运算(&)效率要比代替取模运算(%)高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。
那么，为什么可以使用位运算(&)来实现取模运算(%)呢？这实现的原理如下：
X % 2^n = X & (2^n – 1)
假设n为3，则2^3 = 8，表示成2进制就是1000。2^3 -1 = 7 ，即0111。此时X & (2^3 – 1) 就相当于取X的2进制的最后三位数。从2进制角度来看，X / 8相当于 X >> 3，即把X右移3位，此时得到了X / 8的商，而被移掉的部分(后三位)，则是X % 8，也就是余数。
举几个例子，运算过程如下如：
所以，return h & (length-1); 需要保证length的长度是2^n 的时候才可以实现取模运算了。因为位运算直接对内存数据进行操作，不需要转成十进制，所以位运算要比取模运算的效率更高。
而作为默认容量，太大和太小都不合适，所以16就作为一个比较合适的经验值被采用了。为了保证任何情况下Map的容量都是2的幂，HashMap在两个地方都做了限制。首先是，如果用户制定了初始容量，那么HashMap会计算出比该数大的第一个2的幂作为初始容量。另外，在扩容的时候，也是进行成倍的扩容，即4变成8，8变成16。
2.9 负载因子是多少？为什是这么多?
在HashMap中，threshold = loadFactor * capacity。loadFactor是装载因子，表示HashMap满的程度，默认值为0.75f，设置成0.75有一个好处，那就是0.75正好是3/4，而capacity又是2的幂。所以，两个数的乘积都是整数。
2.10 HashMap是怎么处理hash碰撞的
hash碰撞以put方法为例，首先会根据key计算出hash值，到数组中去寻址，如果该位置上没有值得话，就直接插入数据如果有值得话，判断key是否相等，如果相等的话，就直接覆盖数据，如果key不相等的话，这个时候就产生了hash冲突。hash碰撞时数据的存放方式jdk1.7的解决办法：链表，jdk1.8的解决办法：链表 + 红黑树。将key-value值存入到一个链表当中，如果链表比较长的话，我们去遍历这个链表，此时时间复杂度是O(n)，时间比较长，那么jdk1.8版本就用了红黑树，当这个链表的长度大于等于8的话，那么他就会转为红黑树，这个时候时间复杂度是O(logn)。
2.11 hash的计算规则？
具体实现上，由两个方法int hash(Object k)和int indexFor(int h, int length)来实现。
hash ：该方法主要是将Object转换成一个整型。
indexFor ：该方法主要是将hash生成的整型转换成链表数组中的下标。
2.12 HashTable与CurrentHashMap
HashTable
1、HashTable，它是线程安全的，它在所有涉及到多线程操作的都加上了synchronized关键字来锁住整个table，这就意味着所有的线程都在竞争一把锁，在多线程的环境下，它是安全的，但是无疑是效率低下的。
2、HashTable中key和value都不允许为null；HashMap中空值可以作为Key，也可以有一个/多个Key的value值为空值；
3、HashMap和HashTable内部的数组初始化和扩容方式也不相同HashMap的hash数组默认长度大小为16，扩容方式为2的指数：length_HashMap = 16 * 2n（n为扩容次数）HashTable的hash数组默认长度大小为11，扩容方式为两倍加一：length_HashTable = 上一次HashTable数组长度 * 2 + 1
CurrentHashMap
见单独篇幅
2.13 TreeMap和LinkedHashmap
TreeMap和LinkedHashmap都是有序的。（TreeMap默认是key升序，LinkedHashmap默认是数据插入顺序）TreeMap是基于比较器Comparator来实现有序的。LinkedHashmap是基于链表来实现数据插入有序的。
2.14 java中hashmap在扩容时能否get或put
如果外部方法在调用HashMap时没有任何同步或加锁，那么HashMap在扩容时，很可能查询到的是空数据
HashMap做扩容时，在resize()方法中，先将创建好的新数组赋值给成员变量table，然后才进行数组中元素的搬迁。
三. 思考题
既然HashMap并不会直接接收用户传入的初始容量，那么为什么《阿里巴巴Java开发手册》还是建议开发者在创建HashMap的时候制定一个初始容量呢？这个容量设置成多少合适呢？为什么？