Java集合必会14问

1）说说常见的集合有哪些吧？

答：Map接口和Collection接口是所有集合框架的父接口：

  1. Collection接口的子接口包括：Set接口和List接口
  2. Map接口的实现类主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等
  3. Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等
  4. List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等

2）HashMap与HashTable的区别？

答：

  1. HashMap没有考虑同步，是线程不安全的；Hashtable使用了synchronized关键字，是线程安全的；
  2. HashMap允许K/V都为null；后者K/V都不允许为null；
  3. HashMap继承自AbstractMap类；而Hashtable继承自Dictionary类；

3）HashMap的put方法的具体流程？

图引用自：https://blog.csdn.net/u011240877/article/details/53358305

答：下面先来分析一下源码

  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  2.                boolean evict) {
  3.     HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
  4.     // 1.如果table为空或者长度为0，即没有元素，那么使用resize()方法扩容
  5.     if ((tab = table) == null || (n = tab.length) == 0)
  6.         n = (tab = resize()).length;
  7.     // 2.计算插入存储的数组索引i，此处计算方法同 1.7 中的indexFor()方法
  8.     // 如果数组为空，即不存在Hash冲突，则直接插入数组
  9.     if ((p = tab[i = (n - 1) & hash]) == null)
  10.         tab[i] = newNode(hash, key, value, null);
  11.     // 3.插入时，如果发生Hash冲突，则依次往下判断
  12.     else {
  13.         HashMap.Node<K,V> e; K k;
  14.         // a.判断table[i]的元素的key是否与需要插入的key一样，若相同则直接用新的value覆盖掉旧的value
  15.         // 判断原则equals() - 所以需要当key的对象重写该方法
  16.         if (p.hash == hash &&
  17.                 ((k = p.key) == key || (key != null && key.equals(k))))
  18.             e = p;
  19.         // b.继续判断：需要插入的数据结构是红黑树还是链表
  20.         // 如果是红黑树，则直接在树中插入 or 更新键值对
  21.         else if (p instanceof HashMap.TreeNode)
  22.             e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  23.         // 如果是链表，则在链表中插入 or 更新键值对
  24.         else {
  25.             // i .遍历table[i]，判断key是否已存在：采用equals对比当前遍历结点的key与需要插入数据的key
  26.             //    如果存在相同的，则直接覆盖
  27.             // ii.遍历完毕后任务发现上述情况，则直接在链表尾部插入数据
  28.             //    插入完成后判断链表长度是否 > 8：若是，则把链表转换成红黑树
  29.             for (int binCount = 0; ; ++binCount) {
  30.                 if ((e = p.next) == null) {
  31.                     p.next = newNode(hash, key, value, null);
  32.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  33.                         treeifyBin(tab, hash);
  34.                     break;
  35.                 }
  36.                 if (e.hash == hash &&
  37.                         ((k = e.key) == key || (key != null && key.equals(k))))
  38.                     break;
  39.                 p = e;
  40.             }
  41.         }
  42.         // 对于i 情况的后续操作：发现key已存在，直接用新value覆盖旧value&返回旧value
  43.         if (e != null) { // existing mapping for key
  44.             V oldValue = e.value;
  45.             if (!onlyIfAbsent || oldValue == null)
  46.                 e.value = value;
  47.             afterNodeAccess(e);
  48.             return oldValue;
  49.         }
  50.     }
  51.     ++modCount;
  52.     // 插入成功后，判断实际存在的键值对数量size > 最大容量
  53.     // 如果大于则进行扩容
  54.     if (++size > threshold)
  55.         resize();
  56.     // 插入成功时会调用的方法（默认实现为空）
  57.     afterNodeInsertion(evict);
  58.     return null;
  59. }

图片简单总结为：
image.png

4）HashMap的扩容操作是怎么实现的？

答：通过分析源码我们知道了HashMap通过resize()方法进行扩容或者初始化的操作，下面是对源码进行的一些简单分析：

  1. /**
  2.  * 该函数有2中使用情况：1.初始化哈希表；2.当前数组容量过小，需要扩容
  3.  */
  4. final Node<K,V>[] resize() {
  5.     Node<K,V>[] oldTab = table;// 扩容前的数组（当前数组）
  6.     int oldCap = (oldTab == null) ? 0 : oldTab.length;// 扩容前的数组容量（数组长度）
  7.     int oldThr = threshold;// 扩容前数组的阈值
  8.     int newCap, newThr = 0;
  10.     if (oldCap > 0) {
  11.         // 针对情况2：若扩容前的数组容量超过最大值，则不再扩容
  12.         if (oldCap >= MAXIMUM_CAPACITY) {
  13.             threshold = Integer.MAX_VALUE;
  14.             return oldTab;
  15.         }
  16.         // 针对情况2：若没有超过最大值，就扩容为原来的2倍（左移1位）
  17.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  18.                 oldCap >= DEFAULT_INITIAL_CAPACITY)
  19.             newThr = oldThr << 1; // double threshold
  20.     }
  22.     // 针对情况1：初始化哈希表（采用指定或者使用默认值的方式）
  23.     else if (oldThr > 0) // initial capacity was placed in threshold
  24.         newCap = oldThr;
  25.     else {               // zero initial threshold signifies using defaults
  26.         newCap = DEFAULT_INITIAL_CAPACITY;
  27.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  28.     }
  30.     // 计算新的resize上限
  31.     if (newThr == 0) {
  32.         float ft = (float)newCap * loadFactor;
  33.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  34.                 (int)ft : Integer.MAX_VALUE);
  35.     }
  36.     threshold = newThr;
  37.     @SuppressWarnings({"rawtypes","unchecked"})
  38.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  39.     table = newTab;
  40.     if (oldTab != null) {
  41.         // 把每一个bucket都移动到新的bucket中去
  42.         for (int j = 0; j < oldCap; ++j) {
  43.             Node<K,V> e;
  44.             if ((e = oldTab[j]) != null) {
  45.                 oldTab[j] = null;
  46.                 if (e.next == null)
  47.                     newTab[e.hash & (newCap - 1)] = e;
  48.                 else if (e instanceof TreeNode)
  49.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  50.                 else { // preserve order
  51.                     Node<K,V> loHead = null, loTail = null;
  52.                     Node<K,V> hiHead = null, hiTail = null;
  53.                     Node<K,V> next;
  54.                     do {
  55.                         next = e.next;
  56.                         if ((e.hash & oldCap) == 0) {
  57.                             if (loTail == null)
  58.                                 loHead = e;
  59.                             else
  60.                                 loTail.next = e;
  61.                             loTail = e;
  62.                         }
  63.                         else {
  64.                             if (hiTail == null)
  65.                                 hiHead = e;
  66.                             else
  67.                                 hiTail.next = e;
  68.                             hiTail = e;
  69.                         }
  70.                     } while ((e = next) != null);
  71.                     if (loTail != null) {
  72.                         loTail.next = null;
  73.                         newTab[j] = loHead;
  74.                     }
  75.                     if (hiTail != null) {
  76.                         hiTail.next = null;
  77.                         newTab[j + oldCap] = hiHead;
  78.                     }
  79.                 }
  80.             }
  81.         }
  82.     }
  83.     return newTab;
  84. }