HashMap常见面试题

  1. 当key为null时,进行put操作，数据会被放在那个桶位？为什么?
    • 数组0的位置
  2. 为什么HashMap内部的散列表数组长度一定时2的次方数?
    • 如果不是2的次方数会出现大量的重复 而且有些位置存放不到数据(散列性差)
  3. HashMap内部的散列表结构,什么时候初始化?以及初始化大小分别有几种情况?
    • 调用put方法的时候初始化, 初始化大小可以根据创建map的时候设置，如果没有设置默认16
  4. HashMap为什么需要扩容,扩容resize()又是如何实现的?
    • 为了map的查询性能，数组长度太小不管优化成什么数据结构重复率也会很高，导致查询变慢。这是牺牲空间提升时间的解决方案
    • 扩容值根据加载因子 数组长度到了一定的位置就会进行扩容，每次数组长度<<1，还会根据新的数组长度计算重复位置链表中的哈希值 把哈希值不同的元素放到新的位置。
  5. JDK8中,HashMap为什么引入红黑树
    • 优化map集合重复过多导致链表查询效率过慢，当链表长度超过7个就会把链表变成红黑树。

      构造方法

  • HashMap()

    • 构造一个空的 HashMap ，默认初始容量（16）和默认负载系数（0.75）。
    • new的时候还没有初始化在第一次put的时候才会初始化
      1. //HashMap的无参构造方法源码
      2. public HashMap() {
      3. //默认加载因子0.75
      4. this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
      5. }

  • HashMap(int initialCapacity, float loadFactor)

    • initialCapacity 设置的数组长度
    • loadFactor 设置负载因子
      1. public HashMap(int initialCapacity, float loadFactor) {
      2.    if (initialCapacity < 0)//数组长度不能小于0 小于0抛出异常
      3.        throw new IllegalArgumentException("Illegal initial capacity: " +
      4.                                           initialCapacity);
      5.    if (initialCapacity > MAXIMUM_CAPACITY)//如果数组长度大于最大长度就把数组长度设置为最大长度
      6.        initialCapacity = MAXIMUM_CAPACITY;
      7.    if (loadFactor <= 0 || Float.isNaN(loadFactor))//如果加载因子小于等于0或者不是数字抛出异常
      8.        throw new IllegalArgumentException("Illegal load factor: " +
      9.                                           loadFactor);
      10.    this.loadFactor = loadFactor;
      11.    this.threshold = tableSizeFor(initialCapacity);
      12. }

  • HashMap(Map<? extends K,? extends V> m)

    • 把传入的map变为Hashmap
      1. public HashMap(Map<? extends K, ? extends V> m) {
      2. this.loadFactor = DEFAULT_LOAD_FACTOR;
      3. putMapEntries(m, false);
      4. }

      put方法

      ```java public V put(K key, V value) { //通过hash方法计算出这个数据存放在Node[]中的index位置 return putVal(hash(key), key, value, false, true); } static final int hash(Object key) { int h; //key如果是null那么就把该数据存放到Node[]中的第一个位置 //如果key不为null那么根据二进制算出该数据存放到Node[]中的index //该index不会越界 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { Node[] tab;//存放HashMap数据的数组 Node p;//当前数据 int n,//数组长度 i;//传进来的数据存放的位置 if ((tab = table) == null || (n = tab.length) == 0)//如果数组为null或者长度为0 n = (tab = resize()).length;//对数据进行扩容 if ((p = tab[i = (n - 1) & hash]) == null)//如果当前位置没有数据就把传过来的数据放在该位置 tab[i] = newNode(hash, key, value, null);//新建一个Node放到该位置 else {//如果当前位置不为null也就是key的哈希值重复 Node e; K k; //如果hash值相同并且2个key也相同把值赋给e if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode)//判断当前位置的数据是不是红黑树如果是树把传进来的数据放进去 e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else {//如果不是树就是链表 把传进来的数据放到最后位置 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //当链表的数据长度大于等于7的时候就把链表转换成红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } 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; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

  1. hashMap数据存放图<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/12363754/1624367782072-93f5a483-d2a9-4c30-83fd-d5a7755f35c2.png#clientId=u3729e950-aac0-4&from=paste&id=u60d0b943&margin=%5Bobject%20Object%5D&name=image.png&originHeight=211&originWidth=682&originalType=url&ratio=1&size=21214&status=done&style=none&taskId=u222b84dc-87d0-4692-b36e-7fb6345dafd)
  2. <a name="E2pNG"></a>
  3. ## get方法
  4. ```java
  5. //get源码根据hash值找到index找到该值如果有重复就遍历列表找到对应的key返回value
  6. //是红黑树就遍历红黑树找到value
  7. public V get(Object key) {
  8.     Node<K,V> e;
  9.     return (e = getNode(hash(key), key)) == null ? null : e.value;
  10. }

remove方法

  1. //删除也是一样根据hash找到位置如果是链表就把上一个node的next属性指向被删除元素的next
  2. //如果是红黑树就删除该元素然后红黑树会进行平衡
  3. public V remove(Object key) {
  4.     Node<K,V> e;
  5.     return (e = removeNode(hash(key), key, null, false, true)) == null ?
  6.         null : e.value;
  7. }

HashMap扩容

  • 当Node[]的内容达到initialCapacityloadFactor就会进行扩容比如默认值(160.75=12)当Node[]元素中有12个值了就会进行扩容是当前数组的2倍长度
  • 而且还会根据数组长度和元素key的哈希值重新计算重复元素在新的Node[]中的index
    1. //扩容源码
    2. final Node<K,V>[] resize() {
    3.   Node<K,V>[] oldTab = table;
    4.   int oldCap = (oldTab == null) ? 0 : oldTab.length;
    5.   int oldThr = threshold;
    6.   int newCap, newThr = 0;
    7.   if (oldCap > 0) {
    8.       if (oldCap >= MAXIMUM_CAPACITY) {
    9.           threshold = Integer.MAX_VALUE;
    10.           return oldTab;
    11.       }
    12.       else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
    13.                oldCap >= DEFAULT_INITIAL_CAPACITY)
    14.           newThr = oldThr << 1; // double threshold
    15.   }
    16.   else if (oldThr > 0) // initial capacity was placed in threshold
    17.       newCap = oldThr;
    18.   else {               // zero initial threshold signifies using defaults
    19.       newCap = DEFAULT_INITIAL_CAPACITY;
    20.       newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    21.   }
    22.   if (newThr == 0) {
    23.       float ft = (float)newCap * loadFactor;
    24.       newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
    25.                 (int)ft : Integer.MAX_VALUE);
    26.   }
    27.   threshold = newThr;
    28.   @SuppressWarnings({"rawtypes","unchecked"})
    29.   Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    30.   table = newTab;
    31.   if (oldTab != null) {
    32.       for (int j = 0; j < oldCap; ++j) {
    33.           Node<K,V> e;
    34.           if ((e = oldTab[j]) != null) {
    35.               oldTab[j] = null;
    36.               if (e.next == null)
    37.                   newTab[e.hash & (newCap - 1)] = e;
    38.               else if (e instanceof TreeNode)
    39.                   ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
    40.               else { // preserve order
    41.                   Node<K,V> loHead = null, loTail = null;
    42.                   Node<K,V> hiHead = null, hiTail = null;
    43.                   Node<K,V> next;
    44.                   do {
    45.                       next = e.next;
    46.                       if ((e.hash & oldCap) == 0) {
    47.                           if (loTail == null)
    48.                               loHead = e;
    49.                           else
    50.                               loTail.next = e;
    51.                           loTail = e;
    52.                       }
    53.                       else {
    54.                           if (hiTail == null)
    55.                               hiHead = e;
    56.                           else
    57.                               hiTail.next = e;
    58.                           hiTail = e;
    59.                       }
    60.                   } while ((e = next) != null);
    61.                   if (loTail != null) {
    62.                       loTail.next = null;
    63.                       newTab[j] = loHead;
    64.                   }
    65.                   if (hiTail != null) {
    66.                       hiTail.next = null;
    67.                       newTab[j + oldCap] = hiHead;
    68.                   }
    69.               }
    70.           }
    71.       }
    72.   }
    73.   return newTab;
    74. }