《面试必备知识》——Java集合47问

集合框架图

1. HashTable(HashMap)插入的流程:

• HashMap使用一个类似于数组链表的结构。
• 当程序试图将一个key-value对放入HashMap中时，程序首先根据该 key的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry的 value，但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部。
• 从 JDK 1.8 开始，一个桶存储的链表长度大于 8 时会将链表转换为红黑树。

2. 存1000个数需要多大的HashMap？

关于HashMap容量的初始化，还有这么多学问

• 1000/0.75+1

3. HashMap的负载因子是多少？

• 0.75

HashMap的负载因子为什么默认是0.75？这篇文章告诉你答案

4. hash加密如何加盐？

• 在要加密的内容上拼接上一个随机生成的字符串，该字符串就是盐，然后将拼接完毕后的字符串进行hash加密，提高了密码的安全性
• hash加密特点：
  • 原始密码经哈希函数计算后得到一个哈希值
  • 改变原始密码，哈希函数计算出的哈希值也会相应改变
  • 同样的密码，哈希值也是相同的
  • 哈希函数是单向、不可逆的。也就是说从哈希值，你无法推算出原始的密码是多少
• hash密码破解方法：
  • 猜密码：
    • 字典破解；
    • 暴力破解
  • 查表法：
    • 首先将一些比较常用的密码的哈希值算好，然后建立一张表，当然密码越多，这张表就越大。当你知道某个密码的哈希值时，你只需要在你建立好的表中查找该哈希值，如果找到了，你就知道对应的密码了。

5. 如何衡量一个好的hash函数？

• 将关键字均匀影射到哈希空间上
• 实现一个较好的解决冲突的方法
• 哈希函数的计算要简单高效

6. hash加密用的是什么加密算法？

• MD5
  • 输入不定长度信息，输出固定长度128-bits的算法。
  • 经过程序流程，生成四个32位数据，最后联合起来成为一个128-bits散列。基本方式为，求余、取余、调整长度、与链接变量进行循环运算。得出结果。
• SHA

7. List、set、Map的区别是什么？

• List是一个继承于Collection的接口，即List是集合中的一种。List是有序的队列，List中的每一个元素都有一个索引。和Set不同，List中允许有重复的元素，可以插入多个null元素。实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。
• set是一个继承于Collection的接口，Set是一种不包括重复元素的Collection。 它是一个无序容器，你无法保证每个元素的存储顺序。与List一样，它同样允许null的存在但是仅有一个。由于Set接口的特殊性，所有传入Set集合中的元素都必须不同，关于API方面。Set的API和Collection完全一样。实现了Set接口的集合有：HashSet、TreeSet、LinkedHashSet、EnumSet。
• map与List、Set接口不同，它是由一系列键值对组成的集合，提供了key到Value的映射。在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value，所以它不能存在相同的key值，当然value值可以相同。实现map的集合有：HashMap、HashTable、TreeMap、WeakHashMap。
• 总结：
  • List、Set都是继承自Collection接口，Map则不是
  • List特点：元素有放入顺序，元素可重复 ，Set特点：元素无放入顺序，元素不可重复，重复元素会覆盖掉，（注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的，加入Set 的Object必须定义equals()方法 ，另外list支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。）
  • Set和List对比：
    • Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
    • List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。
  • Map适合储存键值对的数据
  • 线程安全集合类与非线程安全集合类 :
    • LinkedList、ArrayList、HashSet是非线程安全的，Vector是线程安全的;
    • HashMap是非线程安全的，HashTable是线程安全的;
    • StringBuilder是非线程安全的，StringBuffer是线程安全的。

8. ConcurrentHashMap的实现原理？

• HashMap在多线程下访问下导致死循环问题

• ConcurrentHashMap底层实现原理(JDK1.7 & 1.8)

• 在JDK1.7中，ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成，如下图所示：

  

  • Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁，也就是上面的提到的锁分离技术，而每一个Segment元素存储的是HashEntry数组+链表，这个和HashMap的数据存储结构一样。
  • put操作：
    • 从上Segment的继承体系可以看出，Segment实现了ReentrantLock,也就带有锁的功能，当执行put操作时，会进行第一次key的hash来定位Segment的位置，如果该Segment还没有初始化，即通过CAS操作进行赋值，然后进行第二次hash操作，找到相应的HashEntry的位置，这里会利用继承过来的锁的特性，在将数据插入指定的HashEntry位置时（链表的尾端），会通过继承ReentrantLock的tryLock（）方法尝试去获取锁，如果获取成功就直接插入相应的位置，如果已经有线程获取该Segment的锁，那当前线程会以自旋的方式去继续的调用tryLock（）方法去获取锁，超过指定次数就挂起，等待唤醒
  • get操作：
    • ConcurrentHashMap的get操作跟HashMap类似，只是ConcurrentHashMap第一次需要经过一次hash定位到Segment的位置，然后再hash定位到指定的HashEntry，遍历该HashEntry下的链表进行对比，成功就返回，不成功就返回null
  • size操作:
    • 第一种方案他会使用不加锁的模式去尝试多次计算ConcurrentHashMap的size，最多三次，比较前后两次计算的结果，结果一致就认为当前没有元素加入，计算的结果是准确的
    • 第二种方案是如果第一种方案不符合，他就会给每个Segment加上锁，然后计算ConcurrentHashMap的size返回

• JDK1.8直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized和CAS来操作，整个看起来就像是优化过且线程安全的HashMap，虽然在JDK1.8中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本

  

  • put操作：

    1. 如果没有初始化就先调用initTable（）方法来进行初始化过程
    2. 如果没有hash冲突（该桶为空）就直接CAS插入
    3. 如果还在进行扩容操作就先进行扩容
    4. 如果存在hash冲突，就对该桶的头节点进行加锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入，
    5. 最后一个如果该链表的数量大于阈值8，就要先转换成黑红树的结构，break再一次进入循环
    6. 如果添加成功就调用addCount（）方法统计size，并且检查是否需要扩容
    • 在并发处理中使用的是乐观锁，当有冲突的时候才进行并发处理

  • get操作：

    • 计算hash值，定位到该table索引位置，如果是首节点符合就返回
    • 如果遇到扩容的时候，会调用标志正在扩容节点ForwardingNode的find方法，查找该节点，匹配就返回
    • 以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null

  • size操作：

    • 在JDK1.8版本中，对于size的计算，在扩容和addCount()方法就已经有处理了，JDK1.7是在调用size()方法才去计算，其实在并发集合中去计算size是没有多大的意义的，因为size是实时在变的，只能计算某一刻的大小，但是某一刻太快了，人的感知是一个时间段，所以并不是很精确

• 总结：

  • JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树,

9. HashMap的实现原理？（存取原理）

• HashMap以数组+链表+红黑树的结构来实现的。
• 数组中的每一个节点称为一个桶，每个节点用来存储一个键值对。
• 在查询的时候：
  • 首先通过计算key的hash值来找到该key对应的桶
  • 然后如果此时桶上对应的key就是要找的key，则直接命中
  • 否则查看后续节点
    • 如果后续节点是树节点，则调用树的方法查找该key
    • 如果是链式节点，则通过循环遍历链查找该key
• 在插入时：
  • 首先通过计算key的hash值找到该key对应的桶
  • 如果桶上没有发生碰撞，则直接插入
  • 如果碰撞了，则需要进行冲突处理：
    • 如果该桶使用红黑树处理冲突，则调用红黑树的方法插入
    • 否则采用链式方法进行插入。如果链长达到了临界值，就把链转为红黑树
  • 如果桶中存在重复的键值，则为改键替换新值。
  • 如果size大于阈值，则进行扩容。

10. hash冲突的解决方法有哪些？

• 开放定址法
  • 发生冲突时在散列表（也就是数组里）里去寻找合适的位置存取对应的元素
    • 线性探索
      • 直接找相邻的位置
    • 平方探索
      • 不找相邻的，跳跃探索。比如按照 i^2 的规律来跳跃探测
    • 双散列（再哈希）
• 再哈希法
  • 有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数计算地址，直到无冲突
• 链地址法（HashMap采用的方法）
  • 每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向 链表连接起来
• 建立公共溢出区

11. hash算法是什么？

• 哈希（Hash）算法，即散列函数。它是一种单向密码体制，即它是一个从明文到密文的不可逆的映射，只有加密过程，没有解密过程。同时，哈希函数可以将任意长度的输入经过变化以后得到固定长度的输出。哈希函数的这种单向特征和输出数据长度固定的特征使得它可以生成消息或者数据。

12. jdk1.7版hashmap在多线程环境下的死循环问题介绍一下？

• jdk1.7版hashmap在多线程环境下的死循环问题
• Java7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。
• Java8在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。

13. HashMap的底层数据结构是什么？

• 数组+链表+红黑树（JDK1.8）

14. HashMap在Java7和Java8的区别？

• Java7：
  • 在数组中的每一个节点称为entry
  • 采用头插法进行节点插入
  • （使用头插***导致HashMap在多线程环境下进行扩容时，出现死循环的问题）
• Java8：
  • 在数组中的每一个节点称为node
  • 采用尾插法进行节点插入

15. HashMap默认初始化大小是多少？为啥是这么多？为啥大小都是2的幂？

• 默认大小16
• 因为index的计算公式为：index = HashCode（Key） & （Length- 1）
• 当使用2的幂的数字作为长度时，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。
• 只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。
• 这是为了实现均匀分布。
• 而选用16的话应该是一个经验值，是考虑了初始数组的大小不宜过大也不宜过小，且还得是2的幂。

16. HashMap的扩容方式？负载因子是多少？为什是这么多？

• 扩容后的容量为扩容前的两倍
• 负载因子0.75
• 如果负载因子太大，假设为1，那么HashMap的空间利用率较高，但是hash冲突严重，链表较长，查询效率低
• 如果负载因子较小，假设为0.5，那么HashMap的冲突较少，查询效率高，但是空间利用率低，1m的数据需要用2m的空间来存储。
• 0.75就是综合考虑了空间利用率和查询时间的结果。

17. HashMap的主要参数都有哪些？

• 负载因子和初始容量

18. HashMap是怎么处理hash碰撞的？

• 链地址法（HashMap采用的方法）
  • 每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向 链表连接起来

19. hash的计算规则？

• index = HashCode（Key） & （Length- 1）

20. HashMap为什么在单链长度为8和6的时候进行链-树转换？

• 看下面

21. 为什么要使用红黑树？

• 红黑树的时间复杂度为O(logN)，链表的时间复杂度为O(N)，当节点数越多，红黑树查询性能的提升越明显

22. 为什么不一开始就使用红黑树？

• 红黑树节点占用的空间大概是链表节点空间的两倍，当节点数目较少的时候，链表的查询速度与红黑树的查询速度相近
• 因此，综合考虑空间利用率和查询速度，只有当链表的长度超过阈值的时候才转成红黑树，同理，当长度小于阈值的时候则再转成链表

23. 8是如何得出来的？

• 首先，如果hashcode分布良好的话，红黑树的形式是很少概率会被用上的
• 在理想情况下，链表长度(哈希冲突)符合泊松分布，长度越长，概率越低，当长度为8的时候，概率小于千万分之一
• 因此，设置为8，可以保证在通常情况下，不会发生链表到红黑树的转换
• 对于hash函数设计不合理的情况，将链表转成红黑树就相当于一种保底策略，确保在极端情况下的查询效率

24. 红黑树转回链表阈值为什么是6？

• 如果设置为8的话，会导致在链表和红黑树之间不断的振荡转化，浪费资源
• 中间多一个差值7来缓冲，能够有效防止链表和树之间的频繁转换

25. 多线程环境下的hashmap替代方案有哪些？有哪些线程安全的hashmap

• 使用Collections.synchronizedMap(Map)创建线程安全的map集合；
  • synchronizedMap实现原理：
    • synchronizedMap里面维护了一个普通的对象Map和排斥锁mutex。
    • 该类有两个构造函数
      • 一个需要传递mutex对象和map对象。此时将mutex赋值为传入对象
      • 另一个需要传递map对象，此时的mutex贼赋值为this，也就是调用该方法的map对象。
    • 创建出synchronizedMap对象后，再操作map时，会对方法进行加锁。
• Hashtable
• ConcurrentHashMap
• 考虑到线程并发度的问题，一般使用ConcurrentHashMap，其性能和效率明显高于前两者

26. Hashtable的特点介绍一下？

• Hashtable相比于hashmap，它是线程安全的，但是他的效率低下。
• 原因是他对数据操作时会对整个方法进行上锁
• 与HashMap的区别：
  • Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null。
    • hashtable,concurrenthashmap它们是用于多线程的，并发的 ，如果map.get(key)得到了null，不能判断到底是映射的value是null,还是因为没有找到对应的key而为空，而用于单线程状态的hashmap却可以用containKey（key） 去判断到底是否包含了这个null。
    • hashtable不能用containKey(key)来判断到底是否含有key的原因是因为一个线程先get(key)再containKey(key)，这两个方法的中间时刻，其他线程怎么操作这个key都会可能发生，例如删掉这个key
  • 实现方法不同：
    • Hashtable 继承了 Dictionary类，而 HashMap 继承的是 AbstractMap 类。
  • 初始化容量不同：
    • HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。
  • 扩容机制不同：
    • 当现有容量大于总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 + 1
  • 迭代器不同：
    • HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是 fail-fast 的。
      • Hashtable 除了可以使用 entrySet 进行遍历以外，还可以基于枚举的方式来进行遍历 elements（Enumeration）
      • hashtable的failfast是用synchronized实现的
    • 所以，当一个线程在遍历HashMap 时，如果有其它线程改变了HashMap 的结构，将抛出ConcurrentModificationException 异常，而Hashtable 不会。

27. fail-fast和fail-safe区别？

• 并发修改：
  • 当一个或多个线程正在遍历一个集合Collection，此时另一个线程修改了这个集合的内容（添加，删除或者修改）。
• fail-fast（快速失败）：
  • java集合中的一种机制， 在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改）（list的set就不会有），则会抛出Concurrent Modification Exception。
  • 原理：
    • 迭代器在遍历过程中是直接访问内部数据的，因此内部的数据在遍历的过程中不该被修改。
    • 为了保证不被修改，迭代器内部维护了一个标记 “mode” ，当集合结构改变（添加删除或者修改），标记"mode"会被修改，而迭代器每次的hasNext()和next()方法都会检查该"mode"是否被改变，当检测到被修改时，抛出Concurrent Modification Exception。
    • 这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。
    • 因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。
  • 场景：
    • java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）算是一种安全机制吧。
• 安全失败（fail—safe）：
  • java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。
  • fail-safe任何对集合结构的修改都会在一个复制的集合上进行修改，因此不会抛出ConcurrentModificationException
  • 问题：
    • 需要复制集合，产生大量的无效对象，开销大
    • 无法保证读取的数据是目前原始数据结构中的数据。

28. ArrayList的特点介绍一下？

• 简介
  • ArrayList是数组列表，主要用来装载数据，当装载的是基本类型的数据时，储存它们对应的包装类。
  • 底层实现是数组Object[] elementData
  • 与其相似的是LinkedList，相比之下，ArrayList随机访问速度快，但是新增和删除的速度慢。
  • ArrayList线程不安全，使用频率高

29. ArrayList如何去除重复元素？

• 创建一个新的list
• 将旧的list的元素逐个添加到新的list中
• 中间过程通过contains方法判断是否有重复，重复则不添加
  • contains方法底层调用indexOf方法
  • 再底层调用equals方法来进行对象比较

30. ArrayList缩容方法？

• trimToSize方法

• 通过调用上述方法可以让ArrayList的容量修改为当前元素个数大小，实现最小化实例存储

31. ArrayList扩容流程介绍一下？

• 先计算新数组的大小
  • 一般为原数组大小的1.5倍
  • 如果不足的话，则扩容到期望大小
    • addAll方法
• 然后按照新数组的大小来创建新数组
• 将旧数组的元素移动到新数组中
• 将引用指向新数组

32. ArrayList为什么线程不安全还使用他呢？

• 因为ArrayList在正常使用的场景中，都是用来做查询的，不会涉及太频繁的增删，如果涉及频繁的增删的话，可以采用LinkedList，如果还需要线程安全的话，可以使用vector。

33. ArrayList的底层实现是数组，添加数据的话，会有问题吗？

• ArrayList可以通过构造函数指定底层数组的大小
• 无参构造器赋值底层数组为一个默认的空数组，只有真正添加数据时，才分配默认10的初始容量。
• ArrayList通过扩容的方式来实现长度动态增长。
• 比如如果一个10的数组装满了，再新增的时候，会重新定义一个长度为10+10/2的数组，然后把原数组的数据原封不动的复制到新数组中，这个时候再把指向原数组的地址换到新数组。

34. ArrayList的默认数组大小为什么是10？

• 这个应该没有什么具体的原因，应该是一个经验值。

35. ArrayList在增删的时候是怎么做的么？主要说一下他为啥慢。

• 首先，在新增方面，ArrayList有指定index新增，也有直接新增的
• 在新增之前，会先校验数组的长度是否足够，不足的话会进行扩容。
• 指定位置的新增：是在校验之后，对数组进行copy。比如说，要在5这个位置插入元素，则复制原数组从5的位置到末尾的数组，然后将其放在原数组5+1的位置处，最后将新增元素放到5的位置，则完成了新增。由此可见，ArrayList在指定位置的新增效率很低。
• 直接新增的话，是在校验之后，直接在数组的尾部进行添加，由于不用复制数组，因此速度较快
• 其次，在删除方面，ArrayList所采用的方法与新增相似，都是采用数组copy的方法
• 比如说，要删除5位置的元素，那ArrayList就将5+1到数组末尾的元素复制到5位置处，5位置处的元素被覆盖了，看起来就像是被删除了。由此可见，删除方法效率同样很低。

36. ArrayList（int initialCapacity）会不会初始化数组大小？

• ==不会初始化数组大小==！
• 虽然对ArrayList设置了初始大小，但是我们打印List大小的时候还是0，我们操作下标set值的时候也会报错，数组下标越界。
• 集合内部维护了一个size属性，但是直接初始化容量是不会设置size的，在进行set或者打印大小时，都会直接打印size的值，因此size还是为0

37. ArrayList插入删除一定慢么？

• 这取决于插入和删除的位置距离数组的末端有多远。
• ArrayList作为堆栈来用还是比较合适的，push和pop操作完全不涉及数据移动操作。

38. ArrayList是线程安全的么？

• 不是，线程安全的数组容器时vector。
• Vector的实现很简单，就是把所有的方法统统加上synchronized就完事了。
• 除此以外，还可以使用Collections.synchronizedList将普通ArrayList包装成一个线程安全版本的数组容器，原理与Vector类似，就是给所有方法套上一层synchronized。

39. ArrayList用来做队列合适么？

• 队列一般是FIFO（先入先出）的，如果用ArrayList做队列，就需要在数组尾部追加数据，数组头部删除数据
• 因此总会有一个操作涉及到数组数据的搬迁，这个是比较耗费性能的。
• ArrayList不适合做队列。

40. ArrayList的遍历和LinkedList遍历性能比较如何？

• 论遍历ArrayList要比LinkedList快得多，ArrayList遍历最大的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。

41. Arrays.asList()方法

• 返回的是是Arrays的内部类，没有实现集合的修改方法
• 此处体现的是适配器模式，只是转换了接口，后台的数据仍然是数组
• 因此调用add/remove/clear方***抛出异常

传递的数组必须是对象数组，而不是基本类型。

Arrays.asList()是泛型方法，传入的对象必须是对象数组。

int[] myArray = { 1, 2, 3 }; List myList = Arrays.asList(myArray); System.out.println(myList.size());//1 System.out.println(myList.get(0));//数组地址值 System.out.println(myList.get(1));//报错：ArrayIndexOutOfBoundsException int [] array=(int[]) myList.get(0); System.out.println(array[0]);//1

当传入一个原生数据类型数组时，Arrays.asList() 的真正得到的参数就不是数组中的元素，而是数组对象本身！此时List 的唯一元素就是这个数组，这也就解释了上面的代码。

我们使用包装类型数组就可以解决这个问题。

使用集合的修改方法:add()、remove()、clear()会抛出异常。

Arrays.asList() 方法返回的并不是 java.util.ArrayList ，而是 java.util.Arrays 的一个内部类java.util.Arrays$ArrayList,这个内部类并没有实现集合的修改方法或者说并没有重写这些方法。

如何正确的将数组转换为ArrayList?

最简便的方法(推荐)

List list = new ArrayList<>(Arrays.asList("a", "b", "c"))

使用 Java8 的Stream(推荐)

Integer [] myArray = { 1, 2, 3 }; List myList = Arrays.stream(myArray).collect(Collectors.toList()); //基本类型也可以实现转换（依赖boxed的装箱操作） int [] myArray2 = { 1, 2, 3 }; List myList = Arrays.stream(myArray2).boxed().collect(Collectors.toList());

42. 同步容器和并发容器介绍一下？

• 同步容器：
  • Vector、Stack、HashTable
  • Collections类中提供的静态工厂方法创建的类

43. 同步容器（如Vector）的所有操作一定是线程安全的吗？

• 虽然同步容器的所有方法都加了锁，但是对这些容器的复合操作无法保证其线程安全性。需要客户端通过主动加锁来保证。如下例子：

• 此时可以通过加锁的方式来解决

public void deleteLast() {  synchronized (v) {  int index = v.size() - 1;  v.remove(index);  } }

• 在使用同步容器的时候，如果涉及到多个线程同时执行删除操作，就要考虑下是否需要加锁。
• 同步容器由于对其所有方法都加了锁，这就导致多个线程访问同一个容器的时候，只能进行顺序访问，即使是不同的操作，也要排队，如get和add要排队执行。这就大大的降低了容器的并发能力
• 并发容器
  • java.util.concurent包下，提供了大量支持高效并发的访问的集合类，我们称之为并发容器。
  • 在ConcurrentHashMap中增加了对常用复合操作的支持，比如putIfAbsent()、replace()，这2个操作都是原子操作，可以保证线程安全。
  • 并发包中的CopyOnWriteArrayList和CopyOnWriteArraySet是Copy-On-Write的两种实现。
  • Copy-On-Write容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。
  • CopyOnWriteArrayList中add/remove等写方法是需要加锁的，而读方法是没有加锁的。
  • 这样做的好处是我们可以对CopyOnWrite容器进行并发的读，当然，这里读到的数据可能不是最新的。因为写时复制的思想是通过延时更新的策略来实现数据的最终一致性的，并非强一致性。
  • 但是，作为代替Vector的CopyOnWriteArrayList并没有解决同步容器的复合操作的线程安全性问题。
• 总结：
  • 在并发场景中，建议直接使用java.util.concurent包中提供的容器类，如果需要复合操作时，建议使用有些容器自身提供的复合方法。

44. ConcurrentHashMap扩容详解

1.7的rehash

• 每个Segment只管它自己的扩容，互相之间并不影响。换句话说，可以出现这个 Segment的长度为2，另一个Segment的长度为4的情况（只要是2的n次幂）

• 如上图所示，对链表中的元素进行遍历，将最后一段新下标相同的连续元素中的第一个记为lastRun节点
• 从lastRun节点开始到链表的结尾可以整体迁移到新数组对应的下标位置
• 而从链表的头结点到lastRun处就只能逐个复制移动

1.8的扩容

• 首先，由一个线程来完成创建和初始化新表的操作

• 然后，由多个线程来协助迁移元素

• 每个线程需要迁移的元素范围是固定的，都是一部分

• 通过一个全局变量transferIndex来表示目前仍未分配线程进行迁移的部分

• 当一个线程完成了自己的部分后，就可以去进行新的一部分元素的迁移，直到transferIndex归0，整个迁移过程完成

• 迁移一条链表的过程与1.7类似，也采用了lastrun的做法

• 同样采用了头插法

• 因此最后其实会分成两条链表进行迁移，一条是从lastrun开始的正序链表，另外一条是从头到lastrun的反序链表

• 在扩容的过程中，如果当前链表的元素迁移完毕，会将头结点变为ForwardingNode，此时头结点的hash值为-1。

• 根据个人理解，出现hash值为-1的情况，一般是正在扩容的过程中，因此此时新来的线程应该进来协助扩容

• 注意，推进步长(即每个线程负责的扩容范围是需要与CPU核心数结合一起确定)，最小值为16

计算大小

• 1.8：
  • 当需要修改元素数量时，线程会先去 CAS 修改 baseCount 加1，若成功即返回。若失败，则线程被分配到某个 CounterCell ，然后操作 value 加1。若成功，则返回。否则，给当前线程重新分配一个 CounterCell，再尝试给 value 加1。（这里简略的说，实际更复杂）
  • 最后统计总和，就是baseCount + 各个CounterCell
  • CounterCell 类似一个数组
• 1.7：
  • 首先采用乐观的思想，统计每个segment数组的元素个数
  • 重复上述过程，判断前后得到的元素个数是否相等
  • 如果相等，那么直接返回，否则重试两次
  • 如果仍然不成功，那么给所有segment数组加锁，再进行统计

45. 不同集合容量与扩容系数？

• ArrayList

  • 1.7：容量10，饿汉式，扩容1.5倍+1
  • 1.8：容量10，懒汉式，扩容1.5倍。1.5倍大小不足时，按照需要的容量进行扩容

• vector

  • 容量10，饿汉式，默认扩容2倍，构造函数指定了扩容大小则按指定的进行扩容

• HashMap

  • 初始容量16，负载因子0.75，扩容2倍
  • 树形化阈值：8，总64元素
  • 链式化阈值：6，下一次元素迁移中变回来

• HashTable

  • 初始容量11，负载因子0.75，扩容2倍+1

• ConcurrentHashMap

  • 初始容量16，负载因子0.75，扩容2倍

46. java8的ConcurrentHashMap为何放弃分段锁？

• 在JDK1.7中，通过控制Segment的个数来控制并发级别（Segment的个数在ConcurrentHashMap创建后是不可以改变的）

• 随着元素的增多，每个Segment包含的元素越多，锁的粒度会越来越大，竞争会逐渐激烈

• 而且分段会造成内存空间的碎片化，比较浪费内存空间

• 优点：

  • 相比于将整个map加锁的方法，分段机制能够提高并发程度

• 在JDK1.8时，如果发生hash冲突，会对链表的头结点使用synchronized加锁，然后进行插入操作

• 如果没有冲突，就使用CAS来进行插入

• 随着元素的增多，会进行扩容操作，锁的粒度维持在一个较低的水平

• 使用synchronized加锁，可以避免所有节点都继承ReentranLock，因为只需要链表的头节点进行加锁操作就可以了，没必要所有节点都具备加锁功能，能够有效减少内存的开销

• synchronized通过锁升级等相应的处理后，性能与ReentranLock持平

47. hashmap线程不安全的表现有哪些？

• put操作
  • 两个线程，在插入K-V键值对的时候都计算到了同一个桶位置，一个线程先插入，后面一个线程后插入，后面线程的键值对会覆盖掉前面的键值对
• 扩容操作
  • 扩容的时候是通过++size>阈值来判断的，多线程执行++size的结果会不准确导致无法扩容
  • 多个线程进入扩容逻辑，第一个线程把扩容后的table和阈值赋值以后，第二个线程进来，有可能会导致直接扩容四倍或者更多倍
• 删除操作
  • 有可能把别人刚更新的节点给删除了