JAVA--HashMap热门面试题

1. 为什么我们建议在定义hashmap的时候，就指定它的初始化大小呢？

答：在当我们对hashmap初始化时，如果没有为其设置初始化容量，那么系统会默认创建一个容量为16的大小的集合。当我们向hashmap中添加元素时，如果hashmap的容量值超过了它的临界值（默认16*0.75=12）时，（0.75是hashmap的加载因子）hashmap将会重新扩容到下一个2的指数次幂（2^4=16 下一个2的指数次幂是2^5=32）。由于hashmap扩容要进行resize的操作，频繁的resize，会导致hashmap的性能下降，所以建议在确定hashmap集合的大小的情况下，指定其初始化大小，避免做过多的resize操作，导致性能下降。

2. hashmap什么时候进行扩容？

答：当我们不断的向hashmap中添加元素时，它会判断hashmap当前的容量值(当前元素的个数)是否超过了它的临界值（在没有指定其初始化大小时，默认16*0.75=12），如果添加的元素个数超过了临界值，它就会开始进行扩容。

3. hashmap在扩容时，扩容到多大？

答：hashmap在扩容时，它会扩容到下一个2的指数次幂，即当前容量的2倍，比如当前容量是2^4=16，将会扩容到下一个2的指数次幂2^5=32.

4. hashmap是如何进行扩容的？

答：hashmap进行扩容时会调用resize()函数，重新计算hashmap所需的新的容量，然后重新定义一个新的容器，将原数组数据进行hash, 放入新的容器中。这个过程将会导致hashmap的性能下降。

resize()函数的源码：

//hashmap 扩容操作
final node<k,v>[] resize() {
  //保存当前table
  node<k,v>[] oldtab = table;
  //保存当前table的容量
  int oldcap = (oldtab == null) ? 0 : oldtab.length;
  //保存当前阈值
  int oldthr = threshold;
  //初始化新的table容量和阈值
  int newcap, newthr = 0;
  
  //1. resize()函数在size(hashmap当前的元素个数) > threshold(当前阈值，默认16*0.75=12)时调用。
  //当oldcap(hashmap的元素个数)大于0表示原来的table表非空，oldcap(threshold)为oldcap x load_factor(加载因子：0.75)
  if (oldcap > 0) {
    //若旧table容量大于等于最大容量，更新阈值为integer.max_value(最大整形值)，这样以后就不会自动扩容了
    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 //阈值翻倍
  }
  
  //2. resize()函数在table为空被调用。oldcap小于等于0且oldthr大于0，表示用户使用hashmap的构造函数创建了一个hashmap，
  //使用的构造函数为hashmap(int initialcapacity, float loadfactor)或hashmap(int initialcapacity)或hashmap(map<? extends k, ? extends v> m)，
  //导致了oldtab为null,oldcap为0，oldthr为用户指定的hashmap的初始化容量
  else if (oldthr > 0) // initial capacity was placed in threshold
    newcap = oldthr; //当table没有初始化时，threshold为初始容量， threshold = tablesizefor(t);
  
  //3. resize()函数在table为空被调用。oldcap小于等于0且oldthr大于0，表示用户使用hashmap的无参构造函数hashmap()函数创建了一个hashmap，
  //此时，所有值均采用默认值，oldtab(table)表为空，oldcap为0，oldthr等于0.
  else {        // zero initial threshold signifies using defaults
    newcap = default_initial_capacity;
    newthr = (int)(default_load_factor * default_initial_capacity);
  }
  //如果新的阈值为0
  if (newthr == 0) {
    float ft = (float)newcap * loadfactor; //新的tbale容量*加载因子
    newthr = (newcap < maximum_capacity && ft < (float)maximum_capacity ?
         (int)ft : integer.max_value);
  }
  threshold = newthr;
  @suppresswarnings({"rawtypes","unchecked"})
    //初始化table
    node<k,v>[] newtab = (node<k,v>[])new node[newcap];
  table = newtab;
  if (oldtab != null) {
    //把oldtab中的节点rehash到newtab中去
    for (int j = 0; j < oldcap; ++j) {
      node<k,v> e;
      if ((e = oldtab[j]) != null) {
        oldtab[j] = null;
      //如果节点是单个节点，直接在newtab中进行重定位
        if (e.next == null)
          newtab[e.hash & (newcap - 1)] = e;
      //如果节点是treenode节点，要进行红黑树的rehash操作
        else if (e instanceof treenode)
          ((treenode<k,v>)e).split(this, newtab, j, oldcap);
      //如果是链表，进行链表的rehash操作
        else { // preserve order
          node<k,v> lohead = null, lotail = null;
          node<k,v> hihead = null, hitail = null;
          node<k,v> next;
        //将同一桶中的元素根据(e.hash & oldcap)是否为0进行分割，分成两个不同的链表，完成rehash操作
          do {
            next = e.next;
         //根据算法 e.hash & oldcap 判断节点位置rehash后是否发生改变，最高位==0，这是索引不变的链表
            if ((e.hash & oldcap) == 0) {
              if (lotail == null)
                lohead = e;
              else
                lotail.next = e;
              lotail = e;
            }
         //最高位==1，这是索引发生改变的链表
            else {
              if (hitail == null)
                hihead = e;
              else
                hitail.next = e;
              hitail = e;
            }
          } while ((e = next) != null);
          if (lotail != null) { //原bucket位置的尾指针不为空(即还有node)
            lotail.next = null;  //链表最后一个节点为null
            newtab[j] = lohead; //链表的头指针放在新桶的相同下标(j)处
          }
          if (hitail != null) {
            hitail.next = null;
            newtab[j + oldcap] = hihead; //rehash后节点新的位置一定为原来基础上加上oldcap
          }
        }
      }
    }
  }
  return newtab;
}

5. 为什么说hashmap是线程不安全的？

答：hashmap在多线程并发时线程不安全，主要表现在下面两个方面：

(1) 当向hashmap中put(添加)元素时导致的多线程数据不一致

比如有两个线程 a 和 b ，首先 a 希望插入一个 key-value键值对到hashmap 中，它首先计算记录所要落到的 hash 桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程 a 的时间片用完了，而此时线程 b 被调度得以执行，和线程 a 一样执行，只不过线程 b 成功将记录插到了桶里面。假设线程 a 插入的记录计算出来的 hash 桶索引和线程 b 要插入的记录计算出来的 hash 桶索引是一样的，那么当线程 b 成功插入之后，线程 a 再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程 b 插入的记录，这样线程 b 插入的记录就凭空消失了，造成了数据不一致的行为。

简单来说就是在多线程环境下，向hashmap集合中添加元素会存在覆盖的现象，导致了线程不安全。

(2) 当hashmap进行扩容调用resize()函数时引起死循环

hashmap在put的时候，插入的元素超过了容量（由负载因子决定）的范围就会触发扩容操作，就是rehash，这个会重新将原数组的内容重新hash到新的扩容数组中，在多线程的环境下，存在同时其他的元素也在进行put操作，如果hash值相同，可能出现同时在同一数组下用链表表示，造成闭环，导致在get时会出现死循环，所以hashmap是线程不安全的。

hashmap的线程不安全主要体现在下面两个方面：

1.在jdk1.7中，当并发执行扩容操作时会造成环形链和数据丢失的情况。

2.在jdk1.8中，在并发执行put操作时会发生数据覆盖的情况。

6. 说说hashmap 的数据结构

hashmap是一个key-value键值对的数据结构，从结构上来讲在jdk1.8之前是用数组加链表的方式实现，jdk1.8加了红黑树，hashmap数组的默认初始长度是16，hashmap数组只允许一个key为null，允许多个value为null

hashmap的内部实现，hashmap是使用数组+链表+红黑树的形式实现的，其中数组是一个一个node[]数组，我们叫他hash桶数组，它上面存放的是key-value键值对的节点。hashmap是用hash表来存储的，在hashmap里为解决hash冲突，使用链地址法，简单来说就是数组加链表的形式来解决，当数据被hash后，得到数组下标，把数据放在对应下标的链表中。

hashmap是基于哈希表的map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。hashmap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。hashmap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个hashmap的时候，就会初始化一个数组。hashmap主干为一个entry数组，而每个entry存放着一个键值对和同时指向另一个entry的引用，如果发生哈希冲突，该引用即指向另一个entry。

hashmap是由数组+链表结构组成，数组是hashmap主体，链表则是为了解决哈希冲突而存在，如果对于entry不含链表的位置，对其操作的时间复杂度为o(1)，如果定位到具有链表的位置，则时间复杂度为o(n)。

hashmap中重要字段:

transient int size ：实际储存的key-value对个数

int threshold ：阀值，当表为空的时候，该值初始容量为16，后期扩容使用

final float loadfactor ：负载因子，代表表的填充度，默认为0.75

transient int modcount ： 用于快速失败，迭代时抛出异常

在jdk1.8中 hashmap底层改为链表+数组+红黑树的形式，当hash冲突多次在同一个位置发生的时候，（确切的说是该位置链表长度大于8时），在此位置将用红黑树来储存数据提高读取效率.

hashmap 包含如下几个构造器：

hashmap()：构建一个初始容量为 16，负载因子为 0.75 的 hashmap。

hashmap(int initialcapacity)：构建一个初始容量为 initialcapacity，负载因子为 0.75 的 hashmap。

hashmap(int initialcapacity, float loadfactor)：以指定初始容量、指定的负载因子创建一个 hashmap。

hashmap的基础构造器hashmap(int initialcapacity, float loadfactor)带有两个参数，它们是初始容量initialcapacity和负载因子loadfactor。

负载因子loadfactor衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是o(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。

hashmap的实现中，通过threshold字段来判断hashmap的最大容量：

threshold = (int)(capacity * loadfactor);

结合负载因子的定义公式可知，threshold就是在此loadfactor和capacity对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。默认的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时， resize后的hashmap容量是容量的两倍：

7. hashmap 的工作原理是什么?

一，存储方式：  java中的hashmap是以键值对(key-value)的形式存储元素的。

二，调用原理： hashmap需要一个hash函数，它使用hashcode()和equals()方法来向集合/从集合添加和检索元素。当调用put()方法的时候，hashmap会计算key的hash值，然后把键值对存储在集合中合适的索引上。如果key已经存在了，value会被更新成新值。

hashmap的实现原理：

1. 利用key的hashcode重新hash计算出当前对象的元素在数组中的下标

2. 存储时，如果出现hash值相同的key，此时有两种情况。(1)如果key相同，则覆盖原始值；(2)如果key不同（出现冲突），则将当前的key-value放入链表中

3. 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。

4. 理解了以上过程就不难明白hashmap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。

纯属个人总结，如有不对的，欢迎指出！感谢诸君的支持，点个赞吧！

以上就是java--hashmap高频率面试题的详细内容，更多关于java hashmap面试题的资料请关注其它相关文章！