一文搞定面试中HashMap相关问题

　　面试官： 简单聊聊你理解的HashMap基本概念 HashMap是基于哈希表的Map接口的，非同步实现的，以键值对存储数据的集合容器。此实现提供所有可选的映射操作， 并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 数据结构 在JDK7 中，由数组+链表组成 在JDK8 中，由数组+链表+红黑树组成。 其中 链表则是主要为了解决哈希冲突而存在的。当链表过长，则会严重影响 HashMap 的性能，jdk8做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换, 其中 链表的时间复杂度是 O(n)，红黑树时间复杂度是 O(logn) 影响HashMap性能的重要参数 初始容量 capacity： 创建哈希表(数组)时桶的数量，默认为 16。如果太少，很容易触发扩容，如果太多，遍历哈希表会比较慢。 负载因子 loadFactor ：哈希表在其容量自动增加之前可以达到多满的一种尺度，默认为 0.75 阈值 threshold 。 阈值=容量*负载因子。默认12。当元素数量超过阈值时便会触发扩容 单向链表转换为红黑树的时候会先变化为 双向链表 最终转换为 红黑树 ，双向链表跟红黑树是共存的。 红黑树的root节点不一定跟table[i]也就是链表的头节点是同一个，三者同步是靠MoveRootToFront实现的。
　　而HashIterator.remove()会在调用removeNode的时候movable=false。 面试官： 为啥hashmap中链表的个数默认设为8个时，转红黑树？
　　是因为泊松分布
　　源码中的注释：
　　大概的意思是：理想情况下，使用随机的哈希码，容器中节点分布在 hash 桶中的频率遵循 泊松分布 ，按照泊松分布的计算公式计算出了桶中元素个数和概率的对照表，可以看到链表中元素个数为 8 时的概率已经非常小，小于千万分之一概率，所以在选择链表元素个数时， 把长度 8 作为转化的默认转红黑树的阈值。 面试官： 默认加载因子是多少？为什么是 0.75，不是 0.6 或者 0.8 ？
　　当存储的所有节点数 > (16 * 0.75 = 12 )时，就会触发扩容。默认负载因子（0.75）在 时间和空间成本 上提供了很好的折衷。
　　较高的值会降低空间开销，但提高查找成本（体现在大多数的HashMap类的操作，包括get和put）。设置初始大小时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，rehash操作将不会发生。
　　当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为加载因子，每个碰撞位置的链表长度超过８个是几乎不可能的。 面试官： HashMap 的底层数组长度为何总是2的n次方
　　HashMap根据用户传入的初始化容量，利用无符号右移和按位或运算等方式计算出第一个大于该数的2的幂。 使数据分布均匀，减少碰撞 当length为2的n次方时，h & (length-1) = h % length，因为 位运算直接对内存数据进行操作，不需要转成十进制，在速度、效率上比直接取模要快得多 面试官： 说说jdk8 中 HashMap 链表和红黑树的转化条件
　　在数组 同位置 的元素个数又达到了 8个 （代码是>=7,从0开始，及第8个开始 判断是否 转化成红黑树）， 且数组的长度还小于64 的时候，则会扩容数组
　　，或者 当前存入数据 大于阈值threshold 即发生扩容。
　　且 如果数组的长度大于等于64的话，才会将该节点的 链表转换成树。如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。
　　在扩容完成之后，如果某个节点的是树，同时现在该节点的个数又小于等于6个了，则会将该树转为链表。
　　面试官： 简单讲讲jdk8中put和 get方法
　　put方法:
　　上图 流程的边界条件过多，下面是精简的总结： 判断Hashmap是否为空，为空就扩容，不为空计算出key的hash值,定位到对应的数组索引
　　如果此处数组是空的，则调用 resize 进行初始化；如果哈希冲突了，且 key 不存在，向链表后面追加元素（尾插法）如果冲突了，且 key 已经存在，就覆盖掉 value；
　　向后追加时 注意， 优先以链表的形式存放，在数组 同位置 的元素个数又达到了 8个 （代码是>=7,从0开始，及第8个开始 判断是否 转化成红黑树）， 且数组的长度还小于64 的时候，则会扩容数组，或者 当前存入数据 大于阈值threshold 即发生扩容。如果数组的长度大于等于64的话，才会将该节点的链表转换成树。在扩容完成之后，如果某个节点的是树，同时现在该节点的个数又小于等于6个了，则会将该树转为链表。
　　源码摘录：  public V put(K key, V value) {      // 对key的hashCode()做hash         return putVal(hash(key), key, value, false, true);     }  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                    boolean evict) {         Node[] tab; Node p; int n, i;      // 步骤1：tab为空则创建         if ((tab = table) == null || (n = tab.length) == 0)             n = (tab = resize()).length;      // 步骤2：计算index，并对null做处理          if ((p = tab[i = (n - 1) & hash]) == null)             tab[i] = newNode(hash, key, value, null);         else {             Node e; K k;             // 步骤3：节点key存在，直接覆盖value             if (p.hash == hash &&                 ((k = p.key) == key || (key != null && key.equals(k))))                 e = p;             // 步骤4：判断该链为红黑树             else if (p instanceof TreeNode)                 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);             // 步骤5：该链为链表             else {                 for (int binCount = 0; ; ++binCount) {                     if ((e = p.next) == null) {                         p.next = newNode(hash, key, value, null);                         //链表长度大于8转换为红黑树进行处理                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                             treeifyBin(tab, hash);                         break;                     }                     // key已经存在直接覆盖value                     if (e.hash == hash &&                         ((k = e.key) == key || (key != null && key.equals(k))))                         break;                     p = e;                 }             }             if (e != null) { // existing mapping for key                 V oldValue = e.value;                 if (!onlyIfAbsent || oldValue == null)                     e.value = value;                 afterNodeAccess(e);                 return oldValue;             }         }         ++modCount;      // 步骤6：超过最大容量 就扩容         if (++size > threshold)             resize();         afterNodeInsertion(evict);         return null;     }  // 第31行treeifyBin方法部分代码 final void treeifyBin(Node[] tab, int hash) {         int n, index; Node e;      // static final int MIN_TREEIFY_CAPACITY = 64;      // 如果大于8但是数组容量小于64，就进行扩容         if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)             resize();       }
　　get方法：
　　HashMap的get方法就是计算出要获取元素的hash值，去对应位置获取即可。 面试官： 简单说说Jdk7 和Jdk8 的put方法区别是什么？解决哈希冲突时，JDK7 只使用链表，JDK8 使用链表+红黑树，当满足一定条件，链表会转换为红黑树。 链表插入元素时，JDK7 使用头插法插入元素，但在多线程的环境下， 扩容时会造成环形链或数据丢失，出现死循环。 在 transfer函数 中，jdk7中HashMap的transfer函数如下：  void transfer(Entry[] newTable, boolean rehash) {
　　int newCapacity = newTable.length;
　　for (Entry e : table) {
　　while(null != e) {
　　Entry next = e.next;
　　if (rehash) {
　　e.hash = null == e.key ? 0 : hash(e.key);
　　}
　　int i = indexFor(e.hash, newCapacity);
　　e.next = newTable[i];
　　newTable[i] = e;
　　e = next;
　　}
　　}
　　} 总结下该函数的主要作用： 在对table进行扩容到newTable后，需要将原来数据转移到newTable中，注意10-12行代码，这里可以看出在转移元素的过程中，使用的是头插法，也就是链表的顺序会翻转，这里也是形成死循环的关键点 因此，JDK8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了， 但JDK8 的 HashMap 仍然是线程不安全的，在多线程环境下，会发生数据覆盖的情况，导致数据不一致
　　jdk8 putVal()方法中， ... if ((p = tab[i = (n - 1) & hash]) == null)             tab[i] = newNode(hash, key, value, null);         else ...
　　如果没有hash碰撞则会直接插入元素。如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，所以这线程A、B都会进入tab中。
　　假设一种情况，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，这时候会出现一种情况：线程A会把线程B插入的数据给 覆盖 ，发生线程不安全。此处感兴趣的可以见这篇文章[HashMap线程不安全的体现](https://www.cnblogs.com/developer_chan/p/10450908.html) 面试官： 当两个对象的 hashCode 相同会发生什么？
　　因为 hashCode 相同，不一定就是相等的（equals方法比较），所以两个对象所在数组的下标相同，＂碰撞＂就此发生。又因为 HashMap 使用链表存储对象，这个 Node 会存储到链表中 面试官： 如何 解决 hash 冲突？Hashmap解决hash冲突，使用的是链地址法，即数组+链表的形式来解决。 put方法 执行首先判断table[i]位置，如果为空就直接插入，不为空判断和当前值是否相等，相等就覆盖，如果不相等的话，判断是否是红黑树节点，如果不是，就从table[i]位置开始遍历链表，相等覆盖，不相等插入。 扰动函数可以减少碰撞 原理是如果两个不相等的对象返回不同的 hashcode 的话，那么碰撞的几率就会小些。这就意味着存链表结构减小，这样取值的话就不会频繁调用 equal 方法，从而提高 HashMap 的性能（扰动即 Hash 方法内部的算法实现，目的是让不同对象返回不同hashcode）。 使用不可变的、声明作 final 对象，并且采用合适的 equals() 和 hashCode() 方法，将会减少碰撞的发生不可变性使得能够缓存不同键的 hashcode，这将提高整个获取对象的速度，使用 String、Integer 这样的 wrapper 类作为键是非常好的选择。 面试官： 你还知道哪些hash算法？
　　Hash函数是指把一个大范围映射到一个小范围，目的往往是为了节省空间，使得数据容易保存。
　　比较出名的有MurmurHash、MD4、MD5等等。 面试官： 你知道 hash 的实现吗？为什么要这样实现？
　　JDK 1.8 中，它是先算出正常的哈希值，然后通过 hashCode()的 高16位异或运算 实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度，功效和质量来考虑的，减少系统的开销，也不会造成因为高位没有参与下标的计算，从而引起的碰撞。 面试官： jdk8中，刚刚你说的hashmap在解决 hash 冲突的时候,选择先用链表，再转红黑树，为什么不直接用红黑树？
　　因为红黑树需要进行左旋，右旋，变色这些操作来保持平衡，而单链表不需要。
　　当数组 同位置 的元素小于 8 个的时候，此时做查询操作，链表结构已经能保证查询性能，红黑树也不会带来明显的查询时间上的优势，反而会增加空间负担。
　　当数组 同位置 的元素大于等于 8 个的时候， 红黑树搜索时间复杂度是 O(logn)，而链表是 O(n)，此时需要红黑树来加快查询速度，但是新增节点的效率变慢了。
　　但如果一开始就用红黑树结构，元素太少，新增效率又比较慢，无疑这是浪费性能的。 如果不用红黑树，用二叉查找树可以么?
　　但是二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢 面试官： 一般用什么作为HashMap的key?
　　一般用Integer、String 这种不可变类当 HashMap 当 key，而且 String 最为常用。 因为字符串是不可变的，所以在它创建的时候 hashcode 就被缓存了，不需要重新计算。这就是 HashMap 中的键往往都使用字符串的原因。 因为获取对象的时候要用到 equals() 和 hashCode() 方法，那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的重写了 hashCode() 以及 equals() 方法。
　　用可变类当 HashMap 的 key 有什么问题?
　　hashcode 可能发生改变，导致 put 进去的值，无法 get 出。如下所示 HashMap, Object> changeMap = new HashMap<>(); List 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如何扩容？何时进行扩容？ HashMap使用的是懒加载，构造完HashMap对象后，只要不进行put 方法插入元素，HashMap并不会去初始化或者扩容table。
　　首次调用put方法时，HashMap如果发现table为空然后调用resize方法进行初始化。
　　jdk7:
　　Hashmap 在容量超过负载因子所定义的容量之后，就会扩容。Java 里的数组是无法自动扩容的，方法是将 Hashmap 的大小扩大为原来数组的两倍，并将原来的对象放入新的数组中。
　　那扩容的具体步骤是什么？让我们看看源码。
　　先来看下JDK7 的代码： void resize(int newCapacity) {            Entry[] oldTable = table;    //引用扩容前的Entry数组         int oldCapacity = oldTable.length;         if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了             threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了             return;         }          Entry[] newTable = new Entry[newCapacity];          transfer(newTable);                         //将数据转移到新的Entry数组里         table = newTable;                                    threshold = (int)(newCapacity * loadFactor);     }
　　这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。 void transfer(Entry[] newTable) {         Entry[] src = table;                           int newCapacity = newTable.length;         for (int j = 0; j < src.length; j++) {              Entry e = src[j];                          if (e != null) {                 src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）                 do {                     Entry next = e.next;                     int i = indexFor(e.hash, newCapacity); //重新计算每个元素在数组中的位置                     e.next = newTable[i];                      newTable[i] = e;                           e = next;                       } while (e != null);             }         }     }
　　newTable[i] 的引用赋给了 e.next ，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到 Entry 链的尾部(如果发生了 hash 冲突的话）。
　　我们继续看下 JDK8 的 resize 源码： final Node[] resize() {         Node[] oldTab = table;         int oldCap = (oldTab == null) ? 0 : oldTab.length;         int oldThr = threshold;         int newCap, newThr = 0;         if (oldCap > 0) {             // 超过最大值就不再扩充了，就只好随你碰撞去吧             if (oldCap >= MAXIMUM_CAPACITY) {                 threshold = Integer.MAX_VALUE;                 return oldTab;             }             // 没超过最大值，就扩充为原来的2倍             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                     oldCap >= DEFAULT_INITIAL_CAPACITY)                 newThr = oldThr << 1; // double threshold         }         else if (oldThr > 0) //初始容量设置为阈值             newCap = oldThr;         else {               // zero initial threshold signifies using defaults             newCap = DEFAULT_INITIAL_CAPACITY;             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);         }             // 计算新的resize上限         if (newThr == 0) {              float ft = (float)newCap * loadFactor;             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                     (int)ft : Integer.MAX_VALUE);         }         threshold = newThr;         @SuppressWarnings({＂rawtypes＂，＂unchecked＂})         Node[] newTab = (Node[])new Node[newCap];         table = newTab;         if (oldTab != null) {             // 把每个bucket都移动到新的buckets中             for (int j = 0; j < oldCap; ++j) {                 Node e;                 if ((e = oldTab[j]) != null) {                     oldTab[j] = null;                     if (e.next == null)                         newTab[e.hash & (newCap - 1)] = e;                     else if (e instanceof TreeNode)                         ((TreeNode)e).split(this, newTab, j, oldCap);                     else { // 链表优化重hash的代码块                         Node loHead = null, loTail = null;                         Node hiHead = null, hiTail = null;                         Node next;                         do {                             next = e.next;                             if ((e.hash & oldCap) == 0) {                                 if (loTail == null)                                     loHead = e;                                 else                                     loTail.next = e;                                 loTail = e;                             }                             // 原索引+oldCap                             else {                                 if (hiTail == null)                                     hiHead = e;                                 else                                     hiTail.next = e;                                 hiTail = e;                             }                         } while ((e = next) != null);                         // 原索引放到bucket里                         if (loTail != null) {                             loTail.next = null;                             newTab[j] = loHead;                         }                         // 原索引+oldCap放到bucket里                         if (hiTail != null) {                             hiTail.next = null;                             newTab[j + oldCap] = hiHead;//resize 之后，元素的位置在原来的位置，或者原来的位置 +oldCap (原来哈希表的长度）。这边先不展开讲，后续提到这块                         }                     }                 }             }         }         return newTab;     }
　　当添加完元素后，如果HashMap发现size（元素总数）大于threshold（阈值），则会调用resize方法进行扩容，然后把扩容后的数组放到新的数组中去。
　　若threshold（阈值）不为空，table的首次初始化大小为阈值，否则初始化为缺省值大小16。
　　当table需要扩容时，扩容后的table大小变为原来的两倍，接下来就是进行扩容后table的调整：
　　假设扩容前的table大小为2的N次方，有put方法可知，元素的table索引为其hash值的后N位确定
　　那么扩容后的table大小即为2的N+1次方，则其中元素的table索引为其hash值的后N+1位确定，比原来多了一位
　　因此，table中的元素只有两种情况： 元素hash值第N+1位为0：不需要进行位置调整 元素hash值第N+1位为1：调整至原索引的两倍位置
　　在resize方法中，第45行的判断即用于确定元素hashi值第N+1位是否为0： 若为0，则使用loHead与loTail，将元素移至新table的原索引处 若不为0，则使用hiHead与hiHead，将元素移至新table的两倍索引处
　　JDK8做了两处优化： JDK7 中 rehash 的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置（头插法）。JDK8 不会倒置，使用尾插法。 不需要像JDK7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成＂原索引+oldCap＂。 面试官： jdk8中的扩容为什么逻辑判断更简单
　　元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
　　因此，我们在扩充HashMap的时候，不需要像JDK7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成＂原索引+oldCap＂ 由于hashmap的索引是根据哈希值的后N位决定的，由于初始数组容量是16（2^4 = 16），所以是哈希码后4位决定索引位置（即当前元素要存到数组的哪个位置）。
　　而扩容是以2的次方扩容的（每次乘以2的次方倍），所以相当于n-1高位+1（这里是第5位0 →1），同时索引值变成哈希值后N+1位（这里是第一次扩容，所以是后5位）。
　　这样原先的哈希码仍然可以用作索引值。
　　这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，
　　因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK8新增的优化点。 面试官： HashMap 为什么不用跳表替换红黑树呢？
　　跳表是以空间换时间的数据结构，红黑树树不需要额外的空间
　　同时HashMap的Entry并没有内在的排序关系，所以也无法使用跳表，因为跳表本身要求要存在排序关系
　　对于 hashmap 的增删改查使用都很频繁，红黑树的特点就是相对来说各种性能比较均衡，稳定 面试官： HashMap 是如何实现 Fail-Fast的？
　　HashMap 做的  增删改 都会引发modCount值的变化，跟版本控制功能类似，可以理解成version，在特定的操作下需要对version进行检查，适用于Fai-Fast机制。
　　在java的集合类中存在一种Fail-Fast的 错误检测机制 ，当多个线程对同一集合的内容进行操作时，可能就会产生此类异常。比如当A通过iterator去遍历某集合的过程中，其他线程修改了此集合，此时会抛出ConcurrentModificationException异常。此类机制就是通过modCount实现的，在迭代器初始化时，会赋值expectedModCount，在迭代过程中判断modCount和expectedModCount是否一致。 面试官： HashMap，HashTable，ConcurrentHash的共同点和区别
　　HashMap 底层由链表+数组+红黑树实现 可以存储null键和null值 线性不安全 初始容量为16，扩容每次都是2的n次幂 加载因子为0.75，当Map中元素总数超过Entry数组的0.75，触发扩容操作. 并发情况下，HashMap进行put操作会引起死循环，导致CPU利用率接近100% HashMap是对Map接口的实现
　　HashTable HashTable的底层也是由链表+数组+红黑树实现。 无论key还是value都不能为null 它是线性安全的，使用了synchronized关键字。 HashTable实现了Map接口和Dictionary抽象类 Hashtable初始容量为11 性能比较低
　　ConcurrentHashMap ConcurrentHashMap的底层是数组+链表+红黑树 不能存储null键和值 ConcurrentHashMap是线程安全的 ConcurrentHashMap使用锁分段技术确保线性安全 JDK8为何又放弃分段锁，是因为多个分段锁浪费内存空间，竞争同一个锁的概率非常小，分段锁反而会造成效率低。 面试官： 简单说说 jdk8对HashMap的优化
　　最后在总结一下jdk7->jdk8的优化： 数组+链表改成了数组+链表+红黑树 链表的插入方式从头插法改成了尾插法 扩容的时候7需要对原数组中的元素进行重新hash定位在新数组的位置，8采用更简单的判断逻辑，位置不变或索引+旧容量大小； 在插入时，7先判断是否需要扩容，再插入；而 8先进行插入，插入完成再判断是否需要扩容；
　　HashMap相关问题在Java面试中是一个非常重要的一块知识，其实笔者一直都想对这部分的作个整理总结，但苦于没有空闲的时间，希望对需要的朋友有所帮助。
　　本篇文章到这里就结束啦，很感谢靓仔你能看到最后，如果觉得文章对你有帮助，别忘记关注我！
　　计算机内功、JAVA源码、职业成长、项目实战、面试相关资料等更多精彩文章在公众号「小牛呼噜噜」