面试必备：集合框架 - 图1

常见面试题

  1. List是否可以存null,Set是否可以存null,List和Map的区别？
  2. 说一说 HashMap原理、put()原理、get()原理、扩容原理?
    1. 进阶：默认初始长度是16，并且每次自动扩展或者手动初始化，必须是2的幂次，为什么？
    2. 针对 HashMap 中某个 Entry 链太长，查找的时间复杂度可能达到 O(n)，怎么优化？
    3. 高并发下的HashMap：你了解重新调整HashMap大小存在什么问题吗？
    4. HashMap遇到Hash碰撞的时候，除了拉链法解决，还是什么其他的方法吗？
    5. JDK1.7和JDK1.8的HashMap有什么区别？
    6. 重写HashCode()一定要重写Equals()吗？
    7. 为什么String, Interger这样的类适合作为键？
    8. 为什么HashMap选择红黑树而不选择AVL树？MySQL选择B+树而不选择红黑树？
  3. ConcurrentHashMap（CHM）
    1. CHM如何求size? 如何保证求size过程中插入了数据，最终结果的正确性？
    2. CHM的数据结构? — JDK1.7 Segment数组+HashEntry数组
    3. CHM是先插入再扩容还是先扩容再插入？HashMap呢？

详解

1. List

ArrayList 内部实现用数组，快速随机访问，但是插入删除慢，因为要移动其他元素；
LinkedList 内部实现用双向链表，插入删除快，但是随机访问慢。优点在于：将零散的内存关联起来，利用率高。

1.1 面试题：List是否可以存null,Set是否可以存null,List和Map的区别？

a. List中的元素：有序、可重复、可为NULL；
b. Set中的元素：无序、不可重复、只有一个NULL；
c. Map中的元素：无序、Key不重，Value可重、可一个NULL Key,多个NULL值；

2. Queue

队列是一种特殊的线性表，常被用于缓存、线程池场景。

3. Set

不允许出现重复元素。常用的是HashSet、TreeSet、LinkedHashSet。

4. Map

常用的是HashMap、ConcurrentHashMap、TreeMap。

4.1 HashMap原理

  1. 底层实现使用的是：数组+链表的数据结构。
    1. 面试题：默认初始长度是16，并且每次自动扩展或者手动初始化，必须是2的幂次，为什么？
      1. 为了服务key到index的Hash算法。
      2. Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。
  2. put原理：（扩容机制）
    1. 根据key获取相应的Hash值：int hash = hash(key.hash.hashcode())
    2. 根据Hash值和数组长度确定引用位置：int index = hashCode(Key)&(length-1)。
    3. 经典面试题1：Put（）当两个对象的HashCode相同会发生什么？，就放入链表。新来的Entry插入链表时，使用的是”头插法”。—为什么呢？因为HashMap的开发者认为，后插入的Entry被查找的概率比较大。
    4. 经典面试题2：针对 HashMap 中某个 Entry 链太长，查找的时间复杂度可能达到 O(n)，怎么优化？
    5. 经典面试题3：高并发下的HashMap：你了解重新调整HashMap大小存在什么问题吗？
      1. Hashmap的Resize包含扩容和ReHash两个步骤，ReHash在多线程并发的情况下可能会形成链表环。
      2. 原因是什么？— 因为扩容前后链表中元素的顺序反了。
      3. 老生常谈，HashMap的死循环 占小狼
    6. 经典面试题4：HashMap遇到Hash碰撞的时候，除了拉链法解决，还是什么其他的方法吗？
      1. 开放定址法
      2. 线性探测再散列
      3. 再Hash
  3. get原理：
    1. 根据HashCode获取对应Index；
    2. 遍历该数组所在链表:key.equals();
    3. 如果2个Key的HashCode相同，如何获取Value?
      1. 找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。
  4. 经典面试题：
    1. JDK1.7和JDK1.8的HashMap有什么区别？
      1. 为了加快查询效率，JDK1.8的HashMap引入了红黑树结构，当链表长度>8并且数组长度>=64时，该链表就会改成红黑树结构，从而加快查询效率。当Node节点数<=6时，红黑树又退化为链表。
    2. 重写HashCode()一定要重写Equals()吗？— 要
    3. 为什么String, Interger这样的类适合作为键？
      1. String, Interger这样的类作为HashMap的键是再适合不过了，而且String最为常用。因为String对象是不可变的，而且已经重写了equals()和hashCode()方法了。
      2. 不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。
      3. 因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。
    4. 为什么HashMap选择红黑树而不选择AVL树？MySQL选择B+树而不选择红黑树？
      1. HashMap和AVL树的区别？
  5. Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析
  6. Java进阶（六）从ConcurrentHashMap的演进看Java多线程核心技术

4.2 HashMap-1.8分析

https://blog.csdn.net/wushiwude/article/details/75331926
1. HashMap中关于红黑树的三个重要参数

  2. 常见面试题
  3. 1. List是否可以存null,Set是否可以存null,List和Map的区别？
  4. 2. 说一说 HashMap原理、put()原理、get()原理、扩容原理?
  5.   a. 进阶：默认初始长度是16，并且每次自动扩展或者手动初始化，必须是2的幂次，为什么？
  6.   b. 针对 HashMap 中某个 Entry 链太长，查找的时间复杂度可能达到 O(n)，怎么优化？
  7.   c. 高并发下的HashMap：你了解重新调整HashMap大小存在什么问题吗？
  8.   d. HashMap遇到Hash碰撞的时候，除了拉链法解决，还是什么其他的方法吗？
  9.   e. JDK1.7和JDK1.8的HashMap有什么区别？
  10.   f. 重写HashCode()一定要重写Equals()吗？
  11.   g. 为什么String, Interger这样的类适合作为键？
  12.   h. 为什么HashMap选择红黑树而不选择AVL树？MySQL选择B+树而不选择红黑树？
  13. 3. ConcurrentHashMap（CHM）
  14.   a. CHM如何求size? 如何保证求size过程中插入了数据，最终结果的正确性？
  15.   b. CHM的数据结构? -- JDK1.7 Segment数组+HashEntry数组
  16.   c. CHM是先插入再扩容还是先扩容再插入？HashMap呢？ 
  18. 详解
  19. 1. List
  20. ArrayList 内部实现用数组，快速随机访问，但是插入删除慢，因为要移动其他元素；
  21. LinkedList 内部实现用双向链表，插入删除快，但是随机访问慢。优点在于：将零散的内存关联起来，利用率高。
  22. 1.1 面试题：List是否可以存null,Set是否可以存null,List和Map的区别？
  23.   a. List中的元素：有序、可重复、可为NULL；
  24.   b. Set中的元素：无序、不可重复、只有一个NULL；
  25.   c. Map中的元素：无序、Key不重，Value可重、可一个NULL Key,多个NULL值；
  26. 2. Queue
  27. 队列是一种特殊的线性表，常被用于缓存、线程池场景。
  28. 3. Set
  29. 不允许出现重复元素。常用的是HashSet、TreeSet、LinkedHashSet。
  30. 4. Map
  31. 常用的是HashMap、ConcurrentHashMap、TreeMap。
  32. 4.1 HashMap原理
  33. 1. 底层实现使用的是：数组+链表的数据结构。
  34.   a. 面试题：默认初始长度是16，并且每次自动扩展或者手动初始化，必须是2的幂次，为什么？
  35.     ⅰ. 为了服务key到index的Hash算法。
  36.     ⅱ. Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。
  37. 2. put原理：（扩容机制）
  38.   a. 根据key获取相应的Hash值：int hash = hash(key.hash.hashcode())
  39.   b. 根据Hash值和数组长度确定引用位置：int index = hashCode(Key)&(length-1)。
  40.   c. 经典面试题1：Put（）当两个对象的HashCode相同会发生什么？，就放入链表。新来的Entry插入链表时，使用的是"头插法"。--为什么呢？因为HashMap的开发者认为，后插入的Entry被查找的概率比较大。
  41.   d. 经典面试题2：针对 HashMap 中某个 Entry 链太长，查找的时间复杂度可能达到 O(n)，怎么优化？
  42.   e. 经典面试题3：高并发下的HashMap：你了解重新调整HashMap大小存在什么问题吗？
  43.     ⅰ. Hashmap的Resize包含扩容和ReHash两个步骤，ReHash在多线程并发的情况下可能会形成链表环。
  44.     ⅱ. 原因是什么？-- 因为扩容前后链表中元素的顺序反了。
  45.     ⅲ. 老生常谈，HashMap的死循环  占小狼
  46.   f. 经典面试题4：HashMap遇到Hash碰撞的时候，除了拉链法解决，还是什么其他的方法吗？
  47.     ⅰ. 开放定址法
  48.     ⅱ. 线性探测再散列
  49.     ⅲ. 再Hash
  50. 3. get原理：
  51.   a. 根据HashCode获取对应Index；
  52.   b. 遍历该数组所在链表:key.equals();
  53.   c. 如果2个Key的HashCode相同，如何获取Value?
  54.     ⅰ. 找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。
  55. 4. 经典面试题：
  56.   a. JDK1.7和JDK1.8的HashMap有什么区别？
  57.     ⅰ. 为了加快查询效率，JDK1.8的HashMap引入了红黑树结构，当链表长度>8并且数组长度>=64时，该链表就会改成红黑树结构，从而加快查询效率。当Node节点数<=6时，红黑树又退化为链表。
  58.   b. 重写HashCode()一定要重写Equals()吗？-- 要
  59.   c. 为什么String, Interger这样的类适合作为键？
  60.     ⅰ. String, Interger这样的类作为HashMap的键是再适合不过了，而且String最为常用。因为String对象是不可变的，而且已经重写了equals()和hashCode()方法了。
  61.     ⅱ. 不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。
  62.     ⅲ. 因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。
  63.   d. 为什么HashMap选择红黑树而不选择AVL树？MySQL选择B+树而不选择红黑树？
  64.     ⅰ. HashMap和AVL树的区别？
  65. 5. Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析
  66. 6. Java进阶（六）从ConcurrentHashMap的演进看Java多线程核心技术
  68. 4.2 HashMap-1.8分析
  69. https://blog.csdn.net/wushiwude/article/details/75331926
  71. 1. HashMap中关于红黑树的三个重要参数
  72. //一个桶的树化阈值
  73. //当桶中元素个数>=这个值时，需要使用红黑树节点替换链表节点
  74. //这个值必须为 8，要不然频繁转换效率也不高
  75. static final int TREEIFY_THRESHOLD = 8;
  77. //一个树的链表还原阈值
  78. //当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构
  79. //这个值应该比上面那个小，至少为 6，避免频繁转换
  80. static final int UNTREEIFY_THRESHOLD = 6;
  82. //哈希表的最小树形化容量
  83. //当哈希表中的容量大于这个值时，表中的桶才能进行树形化
  84. //否则桶内元素太多时会扩容，而不是树形化
  85. //为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
  86. static final int MIN_TREEIFY_CAPACITY = 64;
  89. 2. 求Size
  90. JDK1.7 和 JDK1.8 对 size 的计算是不一样的。 1.7 中是先不加锁计算三次，如果三次结果不一样在加锁。
  91. JDK1.8 size 是通过对 baseCount 和 counterCell 进行 CAS 计算，最终通过 baseCount 和遍CounterCell 数组得出 size。
  93. 4.3 ConcurrentHashMap
  94. 聊聊并发（四）——深入分析 ConcurrentHashMap
  95. 1. CHM如何求size? 如何保证求size过程中插入了数据，最终结果的正确性？--modCount
  96. 2. CHM的数据结构? -- JDK1.7 Segment数组+HashEntry数组
  97. 3. CHM是先插入再扩容还是先扩容再插入？HashMap呢？ -- HashMap是先插入再扩容，会有浪费。

面试必备：集合框架 - 图2

  1. 求Size
    JDK1.7 和 JDK1.8 对 size 的计算是不一样的。 1.7 中是先不加锁计算三次，如果三次结果不一样在加锁。
    JDK1.8 size 是通过对 baseCount 和 counterCell 进行 CAS 计算，最终通过 baseCount 和遍CounterCell 数组得出 size。

    4.3 ConcurrentHashMap

    聊聊并发（四）——深入分析 ConcurrentHashMap

  2. CHM如何求size? 如何保证求size过程中插入了数据，最终结果的正确性？—modCount

  3. CHM的数据结构? — JDK1.7 Segment数组+HashEntry数组
  4. CHM是先插入再扩容还是先扩容再插入？HashMap呢？ — HashMap是先插入再扩容，会有浪费。