关于后端:一文搞懂所有Java集合面试题

刚刚经验过秋招，看了大量的面经，顺便将常见的 Java 汇合常考知识点总结了一下，并依据被问到的频率大抵做了一个标注。一颗星示意知识点须要理解，被问到的频率不高，面试时起码能说个差不多。两颗星示意被问到的频率较高或对了解 Java 有着重要的作用，倡议熟练掌握。三颗星示意被问到的频率十分高，倡议深刻了解并熟练掌握其相干常识，不便面试时拓展（不便装逼），给面试官留下个好印象。

举荐浏览：一文搞懂所有 Java 基础知识面试题

罕用的汇合类有哪些？＊＊＊

Map 接口和 Collection 接口是所有汇合框架的父接口。下图中的实线和虚线看着有些乱，其中接口与接口之间如果有分割为继承关系，类与类之间如果有分割为继承关系，类与接口之间则是类实现接口。重点把握的抽象类有 HashMap，LinkedList，HashTable，ArrayList，HashSet，Stack，TreeSet，TreeMap。留神：Collection 接口不是 Map 的父接口。

List，Set，Map 三者的区别？＊＊＊

• List：有序汇合 （有序指存入的程序和取出的程序雷同，不是依照元素的某些个性排序）， 可存储反复元素，可存储多个null。
• Set：无序汇合 （元素存入和取出程序不肯定雷同）， 不可存储反复元素，只能存储一个null。
• Map：应用键值对的形式对元素进行存储，key是无序的，且是惟一的。value值不惟一。不同的 key 值能够对应雷同的 value 值。

罕用汇合框架底层数据结构 ＊＊＊

• List：

  1. ArrayList：数组
  2. LinkedList：双线链表

• Set：

  1. HashSet：底层基于 HashMap 实现，HashSet存入读取元素的形式和 HashMap 中的 Key 是统一的。
  2. TreeSet：红黑树

• Map：

  1. HashMap：JDK1.8 之前 HashMap 由数组 + 链表组成的，JDK1.8 之后有数组 + 链表 / 红黑树组成，当链表长度大于 8 时，链表转化为红黑树，当长度小于 6 时，从红黑树转化为链表。这样做的目标是能进步 HashMap 的性能，因为红黑树的查找元素的工夫复杂度远小于链表。
  2. HashTable：数组 + 链表
  3. TreeMap：红黑树

哪些汇合类是线程平安的？＊＊＊

• Vector：相当于有同步机制的ArrayList
• Stack：栈
• HashTable
• enumeration：枚举

迭代器 Iterator 是什么 ＊

Iterator 是 Java 迭代器最简略的实现，它不是一个汇合，它是一种用于拜访汇合的办法，Iterator接口提供遍历任何 Collection 的接口。

Java 汇合的疾速失败机制“fail-fast”和平安失败机制“fail-safe”是什么？＊＊＊

• 疾速失败

  Java 的疾速失败机制是 Java 汇合框架中的一种谬误检测机制，当多个线程同时对汇合中的内容进行批改时可能就会抛出 ConcurrentModificationException 异样。其实不仅仅是在多线程状态下，在单线程中用加强 for 循环中一边遍历汇合一边批改汇合的元素也会抛出 ConcurrentModificationException 异样。看上面代码

  public class Main{public static void main(String[] args) {List<Integer> list = new ArrayList<>();
          for(Integer i : list){list.remove(i);  // 运行时抛出 ConcurrentModificationException 异样
          }
      }
  }

  正确的做法是用迭代器的 remove() 办法，便可失常运行。

  public class Main{public static void main(String[] args) {List<Integer> list = new ArrayList<>();
      Iterator<Integer> it = list.iterator();
          while(it.hasNext()){it.remove();
          }
      }
  }

  造成这种状况的起因是什么？仔细的同学可能曾经发现两次调用的 remove() 办法不同，一个带参数据，一个不带参数，这个前面再说，通过查看 ArrayList 源码，找到了抛出异样的代码

  final void checkForComodification() {if (modCount != expectedModCount)
                throw new ConcurrentModificationException();}

  从下面代码中能够看到如果 modCount 和expectedModCount这两个变量不相等就会抛出 ConcurrentModificationException 异样。那这两个变量又是什么呢？持续看源码

  protected transient int modCount = 0; // 在 AbstractList 中定义的变量

  int expectedModCount = modCount;// 在 ArrayList 中的外部类 Itr 中定义的变量

  从下面代码能够看到，modCount初始值为 0，而 expectedModCount 初始值等于 modCount。也就是说在遍历的时候间接调用汇合的remove() 办法会导致 modCount 不等于 expectedModCount 进而抛出 ConcurrentModificationException 异样，而应用迭代器的 remove() 办法则不会呈现这种问题。那么只能在看看 remove() 办法的源码找找起因了

      public E remove(int index) {rangeCheck(index);
  
          modCount++;
          E oldValue = elementData(index);
  
          int numMoved = size - index - 1;
          if (numMoved > 0)
              System.arraycopy(elementData, index+1, elementData, index,
                               numMoved);
          elementData[--size] = null; // clear to let GC do its work
  
          return oldValue;
      }

  从下面代码中能够看到只有 modCount++ 了，而 expectedModCount 没有操作，当每一次迭代时，迭代器会比拟 expectedModCount 和modCount的值是否相等，所以在调用 remove() 办法后，modCount不等于 expectedModCount 了，这时就了报 ConcurrentModificationException 异样。但用迭代器中 remove() 的办法为什么不抛异样呢？原来 迭代器调用的 remove() 办法和下面的 remove() 办法不是同一个！迭代器调用的 remove() 办法长这样：

          public void remove() {if (lastRet < 0)
                  throw new IllegalStateException();
              checkForComodification();
  
              try {ArrayList.this.remove(lastRet);
                  cursor = lastRet;
                  lastRet = -1;
                  expectedModCount = modCount;    // 这行代码保障了 expectedModCount 和 modCount 是相等的
              } catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();
              }
          }

  从下面代码能够看到 expectedModCount = modCount，所以迭代器的remove() 办法保障了 expectedModCount 和modCount是相等的，进而保障了在加强 for 循环中批改汇合内容不会报 ConcurrentModificationException 异样。

  下面介绍的只是单线程的状况，用迭代器调用 remove() 办法即可失常运行，但如果是多线程会怎么样呢？

  答案是在多线程的状况下即应用了迭代器调用 remove() 办法，还是会报 ConcurrentModificationException 异样。这又是为什么呢？还是要从 expectedModCount 和modCount这两个变量动手剖析，刚刚说了 modCount 在AbstractList类中定义，而 expectedModCount 在ArrayList外部类中定义，所以 modCount 是个共享变量而 expectedModCount 是属于线程各自的。简略说，线程 1 更新了 modCount 和属于本人的 expectedModCount，而在线程 2 看来只有modCount 更新了，expectedModCount并未更新，所以会抛出 ConcurrentModificationException 异样。

• 平安失败

  采纳平安失败机制的汇合容器，在遍历时不是间接在汇合内容上拜访的，而是先复制原有汇合内容，在拷贝的汇合上进行遍历。所以在遍历过程中对原汇合所作的批改并不能被迭代器检测到，所以不会抛出 ConcurrentModificationException 异样。毛病是迭代器遍历的是开始遍历那一刻拿到的汇合拷贝，在遍历期间原汇合产生了批改，迭代器是无法访问到批改后的内容。java.util.concurrent包下的容器都是平安失败，能够在多线程下并发应用。

如何边遍历边移除 Collection 中的元素？＊＊＊

从上文 “疾速失败机制” 可知在遍历汇合时如果间接调用 remove() 办法会抛出 ConcurrentModificationException 异样，所以应用迭代器中调用 remove() 办法。

Array 和 ArrayList 有何区别？＊＊＊

• Array能够蕴含根本类型和对象类型，ArrayList只能蕴含对象类型。
• Array大小是固定的，ArrayList的大小是动态变化的。(ArrayList的扩容是个常见面试题)
• 相比于 Array，ArrayList 有着更多的内置办法，如addAll()，removeAll()。
• 对于根本类型数据，ArrayList 应用主动装箱来缩小编码工作量；而当解决固定大小的根本数据类型的时候，这种形式绝对比较慢，这时候应该应用Array。

comparable 和 comparator 的区别？＊＊

• comparable接口出自 java.lang 包，能够了解为一个内比拟器，因为实现了 Comparable 接口的类能够和本人比拟，要和其余实现了 Comparable 接口类比拟，能够应用 compareTo(Object obj) 办法。compareTo办法的返回值是int，有三种状况：

  1. 返回正整数（比拟者大于被比拟者）
  2. 返回 0（比拟者等于被比拟者）
  3. 返回负整数（比拟者小于被比拟者）
• comparator接口出自 java.util 包，它有一个compare(Object obj1, Object obj2) 办法用来排序，返回值同样是 int，有三种状况，和compareTo 相似。

它们之间的区别：很多包装类都实现了 comparable 接口，像 Integer、String 等，所以间接调用 Collections.sort() 间接能够应用。如果对类外面自带的天然排序不称心，而又不能批改其源代码的状况下，应用 Comparator 就比拟适合。此外应用 Comparator 能够防止增加额定的代码与咱们的指标类耦合，同时能够定义多种排序规定，这一点是 Comparable 接口没法做到的，从灵活性和扩展性讲 Comparator 更优，故在面对自定义排序的需要时，能够优先思考应用 Comparator 接口。

Collection 和 Collections 有什么区别？＊＊

• Collection 是一个 汇合接口。它提供了对汇合对象进行基本操作的通用接口办法。
• Collections 是一个包装类。它蕴含有各种无关汇合操作的 动态多态办法 ，例如罕用的sort() 办法。此类 不能实例化 ，就像一 个工具类 ，服务于 Java 的Collection 框架。

List 汇合

遍历一个 List 有哪些不同的形式？＊＊

先说一下常见的元素在内存中的存储形式，次要有两种：

1. 顺序存储（Random Access）：相邻的数据元素在内存中的地位也是相邻的，能够依据元素的地位（如 ArrayList 中的下表）读取元素。
2. 链式存储（Sequential Access）：每个数据元素蕴含它下一个元素的内存地址，在内存中不要求相邻。例如LinkedList。

次要的遍历形式次要有三种：

1. for循环遍历：遍历者本人在汇合内部保护一个计数器，顺次读取每一个地位的元素。
2. Iterator遍历：基于顺序存储汇合的 Iterator 能够间接按地位拜访数据。基于链式存储汇合的Iterator，须要保留以后遍历的地位，而后依据以后地位来向前或者向后挪动指针。
3. foreach遍历：foreach 外部也是采纳了 Iterator 的形式实现，但应用时不须要显示地申明Iterator。

那么对于以上三种遍历形式应该如何选取呢？

在 Java 汇合框架中，提供了一个 RandomAccess 接口，该接口没有办法，只是一个标记。通常用来标记 List 的实现是否反对 RandomAccess。所以在遍历时，能够先判断是否反对RandomAccess（list instanceof RandomAccess），如果反对可用 for 循环遍历，否则倡议用 Iterator 或 foreach 遍历。

ArrayList 的扩容机制 ＊＊＊

先说下结论，个别面试时须要记住，ArrayList的初始容量为 10，扩容时对是旧的容量值加上旧的容量数值进行右移一位（位运算，相当于除以 2，位运算的效率更高），所以每次扩容都是旧的容量的 1.5 倍。

具体的实现大家可查看下 ArrayList 的源码。

ArrayList 和 LinkedList 的区别是什么？＊＊＊

• 是否线程平安：ArrayList和 LinkedList 都是不保障线程平安的
• 底层实现：ArrayList的底层实现是数组，LinkedList的底层是双向链表。
• 内存占用：ArrayList会存在肯定的空间节约，因为每次扩容都是之前的 1.5 倍，而 LinkedList 中的每个元素要寄存间接后继和间接前驱以及数据，所以对于每个元素的存储都要比 ArrayList 破费更多的空间。
• 利用场景：ArrayList的底层数据结构是数组，所以在插入和删除元素时的工夫复杂度都会收到地位的影响，均匀工夫复杂度为 o(n)，在读取元素的时候能够依据下标间接查找到元素，不受地位的影响，均匀工夫复杂度为 o(1)，所以 ArrayList 更加实用于多读，少增删的场景 。LinkedList 的底层数据结构是双向链表，所以插入和删除元素不受地位的影响，均匀工夫复杂度为 o(1)，如果是在指定地位插入则是 o(n)，因为在插入之前须要先找到该地位，读取元素的均匀工夫复杂度为 o(n)。所以 LinkedList 更加实用于多增删，少读写的场景。

ArrayList 和 Vector 的区别是什么？＊＊＊

• 相同点

  1. 都实现了 List 接口
  2. 底层数据结构都是数组

• 不同点

  1. 线程平安：Vector应用了 Synchronized 来实现线程同步，所以是线程平安的，而 ArrayList 是线程不平安的。
  2. 性能：因为 Vector 应用了 Synchronized 进行加锁，所以性能不如ArrayList。
  3. 扩容：ArrayList和 Vector 都会依据须要动静的调整容量，然而 ArrayList 每次扩容为旧容量的 1.5 倍，而 Vector 每次扩容为旧容量的 2 倍。

简述 ArrayList、Vector、LinkedList 的存储性能和个性？＊＊＊

• ArrayList底层数据结构为数组，对元素的读取速度快，而增删数据慢，线程不平安。
• LinkedList底层为双向链表，对元素的增删数据快，读取慢，线程不平安。
• Vector的底层数据结构为数组，用 Synchronized 来保障线程平安，性能较差，但线程平安。

Set 汇合

说一下 HashSet 的实现原理 ＊＊＊

HashSet的底层是 HashMap，默认构造函数是构建一个初始容量为 16，负载因子为 0.75 的HashMap。HashSet 的值寄存于 HashMap 的key上，HashMap的 value 对立为PRESENT。

HashSet 如何查看反复？（HashSet 是如何保证数据不可反复的？）＊＊＊

这外面波及到了 HasCode() 和equals()两个办法。

• equals()

  先看下 String 类中重写的 equals 办法。

      public boolean equals(Object anObject) {if (this == anObject) {return true;}
          if (anObject instanceof String) {String anotherString = (String)anObject;
              int n = value.length;
              if (n == anotherString.value.length) {char v1[] = value;
                  char v2[] = anotherString.value;
                  int i = 0;
                  while (n-- != 0) {if (v1[i] != v2[i])
                          return false;
                      i++;
                  }
                  return true;
              }
          }
          return false;
      }
  

  从源码中能够看到：

  1. equals办法首先比拟的是内存地址，如果内存地址雷同，间接返回 true；如果内存地址不同，再比拟对象的类型，类型不同间接返回false；类型雷同，再比拟值是否雷同；值雷同返回true，值不同返回false。总结一下，equals 会比拟 内存地址、对象类型、以及值 ，内存地址雷同，equals 肯定返回 true；对象类型和值雷同，equals 办法肯定返回true。
  2. 如果没有重写 equals 办法，那么 equals 和==的作用雷同，比拟的是对象的地址值。

• hashCode

  hashCode办法返回对象的散列码，返回值是 int 类型的散列码。散列码的作用是确定该对象在哈希表中的索引地位。

  对于 hashCode 有一些约定：

  1. 两个对象相等，则 hashCode 肯定雷同。
  2. 两个对象有雷同的 hashCode 值，它们不肯定相等。
  3. hashCode()办法默认是对堆上的对象产生独特值，如果没有重写 hashCode() 办法，则该类的两个对象的 hashCode 值必定不同

介绍完 equals()办法和 hashCode()办法，持续说下 HashSet 是如何查看反复的。

HashSet的特点是存储元素时无序且惟一，在向 HashSet 中增加对象时，首相会计算对象的 HashCode 值来确定对象的存储地位，如果该地位没有其余对象，间接将该对象增加到该地位；如果该存储地位有存储其余对象（新增加的对象和该存储地位的对象的 HashCode 值雷同），调用 equals 办法判断两个对象是否雷同，如果雷同，则增加对象失败，如果不雷同，则会将该对象从新散列到其余地位。

HashSet 与 HashMap 的区别 ＊＊＊

Map 汇合

HashMap 在 JDK1.7 和 JDK1.8 中有哪些不同？HashMap 的底层实现 ＊＊＊

• JDK1.7 的底层数据结构(数组 + 链表)

• JDK1.8 的底层数据结构(数组 + 链表)

• JDK1.7 的 Hash 函数

  static final int hash(int h){h ^= (h >>> 20) ^ (h >>>12);
      return h^(h >>> 7) ^ (h >>> 4);
  }

• JDK1.8 的 Hash 函数

  static final int hash(Onject key){    
      int h;    
      return (key == null) ? 0 : (h = key.hashCode())^(h >>> 16);
  }

  JDK1.8 的函数通过了一次异或一次位运算一共两次扰动，而 JDK1.7 通过了四次位运算五次异或一共九次扰动。这里简略解释下 JDK1.8 的 hash 函数，面试常常问这个，两次扰动别离是 key.hashCode() 与key.hashCode()右移 16 位进行异或。这样做的目标是，高 16 位不变，低 16 位与高 16 位进行异或操作，进而缩小碰撞的产生，高下 Bit 都参加到 Hash 的计算。如何不进行扰动解决，因为 hash 值有 32 位，间接对数组的长度求余，起作用只是 hash 值的几个低位。

HashMap 在 JDK1.7 和 JDK1.8 中有哪些不同点：

HashMap 的长度为什么是 2 的幂次方 ＊＊＊

因为 HashMap 是通过 key 的 hash 值来确定存储的地位，但 Hash 值的范畴是 -2147483648 到 2147483647，不可能建设一个这么大的数组来笼罩所有 hash 值。所以在计算完 hash 值后会对数组的长度进行取余操作，如果数组的长度是 2 的幂次方，(length - 1)&hash等同于 hash%length，能够用(length - 1)&hash 这种位运算来代替 % 取余的操作进而进步性能。

HashMap 的 put 办法的具体流程？＊＊

HashMap 的次要流程能够看上面这个流程图，逻辑十分清晰。

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

• 初始值为 16，负载因子为 0.75，阈值为负载因子 * 容量
• resize()办法是在 hashmap 中的键值对大于阀值时或者初始化时，就调用 resize() 办法进行扩容。
• 每次扩容，容量都是之前的两倍

• 扩容时有个判断 e.hash & oldCap 是否为零，也就是相当于 hash 值对数组长度的取余操作，若等于 0，则地位不变，若等于 1，地位变为原地位加旧容量。

  源码如下：

  final Node<K,V>[] resize() {Node<K,V>[] 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;
          }else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                   oldCap >= DEFAULT_INITIAL_CAPACITY)
              newThr = oldThr << 1;  // 没有超过最大值就变为原来的 2 倍
      }
      else if (oldThr > 0) 
          newCap = oldThr;
  
      else {               
          newCap = DEFAULT_INITIAL_CAPACITY;
          newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
      }
  
      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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
      table = newTab;
      if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {
              Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap);
                  else { 
                      Node<K,V> loHead = null, loTail = null;//loHead,loTail 代表扩容后在原地位
                      Node<K,V> hiHead = null, hiTail = null;//hiHead,hiTail 代表扩容后在原地位 + 旧容量
                      Node<K,V> next;
                      do {             
                          next = e.next;
                          if ((e.hash & oldCap) == 0) { // 判断是否为零，为零赋值到 loHead，不为零赋值到 hiHead
                              if (loTail == null)
                                  loHead = e;
                              else                                
                                  loTail.next = e;
                              loTail = e;                           
                          }
                          else {if (hiTail == null)
                                  hiHead = e;
                              else
                                  hiTail.next = e;
                              hiTail = e;
                          }
                      } while ((e = next) != null);
                      if (loTail != null) {
                          loTail.next = null;
                          newTab[j] = loHead;   //loHead 放在原地位
                      }
                      if (hiTail != null) {
                          hiTail.next = null;
                          newTab[j + oldCap] = hiHead;  //hiHead 放在原地位 + 旧容量
                      }
                  }
              }
          }
      }
      return newTab;
  }
  

HashMap 默认加载因子为什么抉择 0.75？

这个次要是思考空间利用率和查问老本的一个折中。如果加载因子过高，空间利用率进步，然而会使得哈希抵触的概率减少；如果加载因子过低，会频繁扩容，哈希抵触概率升高，然而会使得空间利用率变低。具体为什么是 0.75，不是 0.74 或 0.76，这是一个基于数学分析（泊松散布）和行业规定一起失去的一个论断。

为什么要将链表直达红黑树的阈值设为 8？为什么不一开始间接应用红黑树？

可能有很多人会问，既然红黑树性能这么好，为什么不一开始间接应用红黑树，而是先用链表，链表长度大于 8 时，才转换为红红黑树。

• 因为红黑树的节点所占的空间是一般链表节点的两倍，但查找的工夫复杂度低，所以只有当节点特地多时，红黑树的长处能力体现进去。至于为什么是 8，是通过数据分析统计进去的一个后果，链表长度达到 8 的概率是很低的，综合链表和红黑树的性能优缺点思考将大于 8 的链表转化为红黑树。
• 链表转化为红黑树除了 链表长度大于 8，还要 HashMap 中的数组长度大于 64。也就是如果 HashMap 长度小于 64，链表长度大于 8 是不会转化为红黑树的，而是间接扩容。

HashMap 是怎么解决哈希抵触的？＊＊＊

哈希抵触：hashMap在存储元素时会先计算 key 的 hash 值来确定存储地位，因为 key 的 hash 值计算最初有个对数组长度取余的操作，所以即便不同的 key 也可能计算出雷同的 hash 值，这样就引起了 hash 抵触。hashMap的底层构造中的链表 / 红黑树就是用来解决这个问题的。

HashMap中的哈希抵触解决形式能够次要从三方面思考（以 JDK1.8 为背景）

• 拉链法

  HasMap中的数据结构为数组 + 链表 / 红黑树，当不同的 key 计算出的 hash 值雷同时，就用链表的模式将 Node 结点（抵触的 key 及key对应的value）挂在数组前面。

• hash 函数

  key的 hash 值通过两次扰动，key的 hashCode 值与 key 的hashCode值的右移 16 位进行异或，而后对数组的长度取余（理论为了进步性能用的是位运算，但目标和取余一样），这样做能够让 hashCode 取值出的高位也参加运算，进一步升高 hash 抵触的概率，使得数据分布更均匀。

• 红黑树

  在拉链法中，如果 hash 抵触特地重大，则会导致数组上挂的链表长度过长，性能变差，因而在链表长度大于 8 时，将链表转化为红黑树，能够进步遍历链表的速度。

HashMap 为什么不间接应用 hashCode()解决后的哈希值间接作为 table 的下标？＊＊＊

hashCode()解决后的哈希值范畴太大，不可能在内存建设这么大的数组。

是否应用任何类作为 Map 的 key？＊＊＊

能够，但要留神以下两点：

• 如果类重写了 equals() 办法，也应该重写 hashCode() 办法。
• 最好定义 key 类是不可变的，这样 key 对应的 hashCode() 值能够被缓存起来，性能更好，这也是为什么 String 特地适宜作为 HashMap 的key。

为什么 HashMap 中 String、Integer 这样的包装类适宜作为 Key？＊＊＊

• 这些包装类都是 final 润饰，是不可变性的，保障了 key 的不可更改性，不会呈现放入和获取时哈希值不同的状况。
• 它们外部曾经重写过 hashcode(),equal() 等办法。

如果应用 Object 作为 HashMap 的 Key，应该怎么办呢？＊＊

• 重写 hashCode() 办法，因为须要计算 hash 值确定存储地位
• 重写 equals() 办法，因为须要保障 key 的唯一性。

HashMap 多线程导致死循环问题 ＊＊＊

因为 JDK1.7 的 hashMap 遇到 hash 抵触采纳的是头插法，在多线程状况下会存在死循环问题，但 JDK1.8 曾经改成了尾插法，不存在这个问题了。但须要留神的是 JDK1.8 中的 HashMap 依然是不平安的，在多线程状况下应用依然会呈现线程平安问题。基本上面试时说到这里既能够了，具体流程用口述是很难说清的，感兴趣的能够看这篇文章。HASHMAP 的死循环

ConcurrentHashMap 底层具体实现晓得吗？＊＊

• JDK1.7

  在 JDK1.7 中，ConcurrentHashMap采纳 Segment 数组 + HashEntry数组的形式进行实现。Segment实现了 ReentrantLock，所以Segment 有锁的性质，HashEntry用于存储键值对。一个 ConcurrentHashMap 蕴含着一个 Segment 数组，一个 Segment 蕴含着一个 HashEntry 数组，HashEntry是一个链表构造，如果要获取 HashEntry 中的元素，要先取得 Segment 的锁。

• JDK1.8

  在 JDK1.8 中，不在是 Segment+HashEntry 的构造了，而是和 HashMap 相似的构造，Node 数组 + 链表 / 红黑树，采纳 CAS+synchronized 来保障线程平安。当链表长度大于 8，链表转化为红黑树。在 JDK1.8 中 synchronized 只锁链表或红黑树的头节点，是一种相比于 segment 更为细粒度的锁，锁的竞争变小，所以效率更高。

总结一下：

• JDK1.7 底层是ReentrantLock+Segment+HashEntry，JDK1.8 底层是synchronized+CAS+ 链表 / 红黑树
• JDK1.7 采纳的是分段锁，同时锁住几个 HashEntry，JDK1.8 锁的是 Node 节点，只有没有产生哈希抵触，就不会产生锁的竞争。所以 JDK1.8 相比于 JDK1.7 提供了一种粒度更小的锁，缩小了锁的竞争，进步了ConcurrentHashMap 的并发能力。

HashTable 的底层实现晓得吗？

HashTable的底层数据结构是数组 + 链表，链表次要是为了解决哈希抵触，并且整个数组都是 synchronized 润饰的，所以 HashTable 是线程平安的，但锁的粒度太大，锁的竞争十分强烈，效率很低。

HashMap、ConcurrentHashMap 及 Hashtable 的区别 ＊＊＊

Java 汇合的罕用办法 ＊＊

这些罕用办法是须要背下来的，尽管面试用不上，然而口试或者面试写算法题时会常常用到。

Collection 罕用办法

List 特有办法

LinkedList 特有办法

Map

Stack

Queue