文章目录
- 前言
- 41、多线程使用 ArrayList
- 42、List 和 Set 区别
- 43、HashSet 实现原理
- 44、HashSet检查重复和保证数据不可重复
- 45、BlockingQueue
- 46、Map接口
- 46.1、HashMap实现原理
- 46.2、HashMap在JDK1.7和JDK1.8中不同点
- 46.3、JDK1.7 VS JDK1.8 比较
- 47、HashMap的put方法流程
- 48、HashMap解决哈希冲突
- 48、HashMap 长度是2的幂次方
- 49、HashMap 与 HashTable 区别
- 50、如何决定使用 HashMap 还是TreeMap
前言
亲爱的家人们，创作很不容易，若对您有帮助的话，请点赞收藏加关注哦，您的关注是我持续创作的动力，谢谢大家！有问题请私信或联系邮箱：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 区别
相同点：都继承自Collection 接口
①List 特点：一个有序容器，元素可重复，插入多个null元素，元素都有索引。常用实现类：ArrayList、LinkedList 和 Vector。
②Set 特点：一个无序容器，不可存储重复元素，只允许存一个null元素，保证元素唯一性。常用实现类：HashSet、LinkedHashSet 以及 TreeSet。
③Set和List对比
Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
List：List动态增长，查找元素效率高，插入删除元素效率低，会引起其他元素位置改变。
43、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概述：基于哈希表Map接口的非同步实现。提供所有可选映射操作，并允许使用null值和null键。不保证映射顺序。
HashMap数据结构： 在Java编程语言中， 两种基本结构：一个是数组，另外一个是模拟指针（引用），所有数据结构都可用这两个基本结构来构造。HashMap是一个“链表散列”的数据结构，即数组和链表的结合体。
HashMap基于Hash算法实现：
①往Hashmap中put元素，利用keyhashCode重新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之后：当链表长度大于阈值（默认为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数据结构
数组特点：寻址容易，插入和删除困难；
链表特点：寻址困难，但插入和删除容易；
将数组和链表结合，发挥各自优势，使用链地址法解决哈希冲突，将拥有相同哈希值对象组织成一个链表放在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
HashMap：在Map中插入、删除和定位元素。
TreeMap：对一个有序的key集合遍历。
