前言

亲爱的家人们，创作很不容易，若对您有帮助的话，请点赞收藏加关注哦，您的关注是我持续创作的动力，谢谢大家！有问题请私信或联系邮箱：fn_kobe@163.com

41、多线程场景下使用 ArrayList

ArrayList 不是线程安全的，如果遇到多线程场景，通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。

List<String> synchronizedList = Collections.synchronizedList(list);
synchronizedList.add("aaa");
synchronizedList.add("bbb");
for (int i = 0; i < synchronizedList.size(); i++) {
System.out.println(synchronizedList.get(i));
}

42、List 和 Set 区别

List , Set 都是继承自Collection 接口
①List 特点：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素重复，插入多个null元素，元素都有索引。常用的实现类有ArrayList、LinkedList 和 Vector。
②Set 特点：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。Set 接口常用实现类是HashSet、LinkedHashSet 以及 TreeSet。
另外 List 支持for循环，通过下标来遍历，也可以=用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。

③Set和List对比
Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
List：和数组类似，List动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。

43、HashSet 实现原理

HashSet 是基于 HashMap 实现的，HashSet的值存放于HashMap的key上，HashMap的value统一为PRESENT，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成。

44、HashSet检查重复和保证数据不可重复

向HashSet 中add ()元素时，判断元素是否存在的依据，不仅要比较hash值，同时还要结合equles方法比较。HashSet 中的add ()方法会使用HashMap 的put()方法。
HashMap 的key是唯一的，由源码看出 HashSet 添加进去的值就是作为 HashMap 的key，并且在HashMap中如果K/V相同时，会用新的V覆盖掉旧的V，然后返回旧的V。所以不会重复（ HashMap 比较key是否相等是先比较 hashcode 再比较equals ）。

45、BlockingQueue

Java.util.concurrent.BlockingQueue是一个队列，在进行检索或移除一个元素的时候，它会等待队列变为非空；当在添加一个元素时，它会等待队列中的可用空间。

BlockingQueue接口是Java集合框架的一部分，主要用于实现生产者-消费者模式。不需要担心等待生产者有可用的空间，或消费者有可用的对象，BlockingQueue的实现类中会处理。

Java提供BlockingQueue的实现，比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue、SynchronousQueue等。

①在 Queue 中 poll()和 remove()区别

相同点：都是返回第一个元素，并在队列中删除返回的对象。
不同点：如果没有元素 poll()会返回 null，而 remove()会直接抛出 NoSuchElementException 异常。

46、Map接口

46.1、HashMap 实现原理

HashMap概述： HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap的数据结构： 在Java编程语言中， 基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

HashMap 基于 Hash 算法实现的：

当我们往Hashmap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标

存储时，如果出现hash值相同的key，此时有两种情况。(1)如果key相同，则覆盖原始值；(2)如果key不同（出现冲突），则将当前的key-value 放入链表中

获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。

理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。

需要注意Jdk 1.8中对HashMap的实现做了优化，当链表中的节点数据超过八个之后，该链表会转为红黑树来提高查询效率，从原来的O(n)到O(logn)

46.2、HashMap在JDK1.7和JDK1.8中不同点

在Java中，保存数据有两种比较简单的数据结构：数组和链表。
数组的特点是：寻址容易，插入和删除困难
链表的特点是：寻址困难，但插入和删除容易；
所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做拉链法的方式可以解决哈希冲突。

JDK1.8之前
JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

JDK1.8之后
相比于之前的版本，jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

46.3、JDK1.7 VS JDK1.8 比较

JDK1.8主要解决或优化问题：

①resize 扩容优化

②引入红黑树，目的是避免单条链表过长而影响查询效率，红黑树算法请参考

③解决多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题。

47、HashMap的put方法流程

①判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

②根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

③判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向

④这里的相同指的是hashCode以及equals；

④判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥插入成功后，判断实际存在的键值对数量size是否超多了 大容量threshold，如果超过，进行扩容。

48、HashMap解决哈希冲突

哈希定义：一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

所有散列函数基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。

哈希碰撞：当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象。

HashMap的数据结构
在Java中，保存数据有两种比较简单的数据结构：
数组和链表数组的特点是：寻址容易，插入和删除困难；
链表的特点是：寻址困难，但插入和删除容易；
将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做链地址法的方式解决哈希冲突，将拥有相同哈希值的对象(img)组织成一个链表放在hash值所对应的 bucket下。

48、HashMap 的长度是2的幂次方

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。
“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且采用二进制位操作 &，相对于%能够提高运算效率。

49、HashMap 与 HashTable 区别

线程安全： HashMap 是非线程安全的，HashTable 是线程安全的；
HashTable 内部的方法基本都经过 synchronized 修饰。（保证线程安全建议使用 ConcurrentHashMap）；

效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；

对Null key 和Null value的支持： HashMap 中，null 作为键，这样的键只有一个，有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛NullPointerException。

初始容量大小和每次扩充容量大小的不同 ：
①创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。
②创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。

底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

推荐使用：推荐在单线程环境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代。
HashMap 和 ConcurrentHashMap 的区别
ConcurrentHashMap对整个桶数组进行分割分段(Segment)，然后在每一个分段上都用lock锁进行保护，相对于HashTable的synchronized 锁的粒度更精细，并发性能更好，而HashMap没有锁机制，不是线程安全的。（JDK1.8之后ConcurrentHashMap启了一种全新的方式实现,利用CAS算法。）
HashMap的键值对允许有null，但是ConCurrentHashMap都不允许

50、如何决定使用 HashMap 还是TreeMap

对于在Map中插入、删除和定位元素这类操作，HashMap是好的选择。
然而，假如你需要对一个有序的key集合进行遍历，TreeMap是更好的选择。基于你的collection的大小，也许向HashMap中添加元素会更快，将map换为TreeMap进行有序key的遍历。