集合框架面试

1.常见的集合有哪些

主要分为3种List、Map、Set

2.ArrayList和LinkedList有什么区别

• 数据结构不同：ArrayList是基于数组实现的，LinkedList是双向链表实现
• 使用场景不同：ArrayList更利于查找，LinkedList利于增删
• 是否支持随机访问：ArrayList是基于数组，所以他可以根据下标进行查找，支持随机访问（实现RandmoAccess接口，做一个标志）。LinkedList是基于链表，所以它没有办法根据序号直接获取元素，不支持随机访问。
• 内存空间不同：ArrayList是基于数组，是一块连续的内存空间，LinkedList 基于链表，内存空间不连续，它们在空间占用上一些额外的消耗。

3.ArrayList的扩容机制

ArrayList是基于数组的集合，数组的容量是定义的时候就确定了，在插入的时候就会去判断是否需要扩容，如果超出当前的容量+1，那么就会扩容，扩容是创建一个1.5倍的数组，然后把原来数组的值拷进去。

4.快速失败(fail-fast)和安全失败(fail-safe)了解吗？

• 快速失败fail-fast 是java集合的一种错误检测机制。原理：迭代?在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 变量。集合在被遍历
  期间如果内容发生变化，就会改变modCount的值。每当迭代?使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
• 安全失败fail-safe：原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代?检测到，所以不会触发Concurrent Modification Exception

5.有哪几种实现ArrayList线程安全的方法

• 使用Vector代替ArrayList，但是不推荐
• 使用Collections.SynchronizedList保证ArrayList，然后操作包装后的list
• CopyOnWriterArrayList代替ArrayList
• 使用ArrayList时候应用程序通过同步机制去控制ArrayList的读写。

6.CopyOnWriteArrayList了解多少

CopyOnWriteArrayList是线程安全的版本的ArrayList。它的名字叫写时复制，采用了读写分离的并发策略。CopyOnWriterArrayList容器允许并发读，读操作是无锁的，性能较高。至于写操作则首先将当前的容器复制一份，然后再副本上执行写操作，结束后再将原来容器的引用指向新容器。

7. Map中Hashmap的数据结构

jdk1.7之前是数组加链表，1.7之后就是数组加链表加红黑树。
其中桶数组是用来存储数据，链表是用来解决冲突，红黑树是为了便于提高查询效率。

• 数据元素通过映射关系，也就是散列函数，映射到桶数组对应的索引位置
• 如果发生冲突，从冲突的位置拉一个链表，放入冲突的元素
• 如果链表长度大于8并且 数组>=64,链表转为红黑树。
• 如果红黑树节点小于6，转为链表。

8.说说红黑树的理解

红黑树本质上也是一种二叉树，为了保持平衡它增加了一下规则

1. 每个节点要么是黑色，要么是红色。
2. 根节点永远是黑色
3. 所有的叶子节点是黑色
4. 每个红色节点的两个子节点是黑色
5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
   
   之所以不用二叉树，红黑树本身就是一种平衡的二叉树，插入，删除查找的最坏时间复杂的都是O（logn）避免了二叉树最坏的情况下的O(n)时间复杂度。

之所以不用平衡二叉树：平衡二叉树是比红黑树更加严格的平衡树，为了保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。

9.红黑树怎么保持平衡

红黑树有两种保持平衡的方式：旋转和染色

10. HashMap的put流程

1. 首先进行哈希值的扰动，获取一个新的哈希值
2. 判断tab是否空位或者长度为0，如果是则进行扩容
3. 进行哈希值的下标计算，如果对应的下标没有存放数据，则直接插入否则就覆盖。
4. 判断ta【i】是否为树节点，否则向链表中插入数据，是则向树中插入节点。
5. 如果链表插入节点，链表长度大于8，则转化为红黑树。
6. 最后所有数据处理完成后，判断是否超过阈值，超过则进行扩容。

11.HashMap是如何查找数据的

1. 使用扰动函数，获取新的哈希值。
2. 计算数组下标，获取节点。
3. 匹配当前节点key是否满足，是直接返回
4. 否则当前节点是否为树节点，是遍历树
5. 否则遍历链表

12.HashMap的哈希/扰动函数是怎么设计的?

HashMap的哈希函数是先拿到 key 的hashcode，是一个32位的int类型的数值，然后让hashcode的高16位和低16位进行异或操作。

static final int hash(Object key)
{ int h;
// key的hashCode和key的hashCode右移16位 异或运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

13.为什么Hashmap的容量是2的倍数

1. 为了方便哈希取值
2. 在扩容的时候，利用扩容的大小也是2的倍数，将已经产生hash碰撞的元素完美的移植到新的table中。

如果初始化HashMap，传一个17的值newHashMap<>，它会怎么处理？

简单来说，如果传递的不是2的倍数，那么会自动向上寻找离得最近的2的倍数，17的2的进制倍数是32。

14.你还知道那些哈希函数的构造方法呢

Hashmap里面的构造方法叫做除留取余法
除此以为还有

• 直接定址法：直接根据key来映射到对应的位置。例如123就放到下标为123的地方
• 数字分析法：取key的某些数组（如十位，百位）作为映射的位置
• 平方取中法：取key平方的中间几位作为映射的位置
• 折叠法：将key分割为位数相同的几段，然后把它们叠加作为映射的位置

15.解决哈希冲突有那些方法

HashMap使用链表的原因就是为了处理哈希冲突，这种方法就是

• 链地址法：在冲突的地方拉一个链表，将冲突的元素放进去。

除此之外的一些解决方法

• 开放地址法：就是在冲突的地方接着寻找下一个，给冲突元素找个空位。（线性探查法、平方探查法）
• 在哈希法：换种哈希函数进行计算，重新计算冲突地址
• 建立公共溢出区：在建立一个数组，把冲突的元素放进去

16.jdk1.8对Hashmap做了哪些优化

1. 数据结构优化为数组，加链表加红黑树
2. 链表插入方式：链表的插入方式从头插法变为了尾插法（原因 ：因为 1.7 头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环）
3. 扩容rehash：扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 新增容量大小。
4. 扩容时机：在插入的时候，1.7前是先判断是否需要扩容，1.8是先进行插入，插入完成在进行判断是否需要扩容。
5. 散列函数：1.7做4次位移和4次异或，1.8只做1次（做4次的话边际效用也不大，改为一次，提升效率）

17.如何自己实现一个HashMap

整体设计：

• 散列函数：hashcode+除留余数法
• 冲突解决法：链地址法
• 扩容：节点重新hash获取位置

18.HashMap是线程安全的吗

HashMap不是线程安全的，可能会发生这些问题

• 扩容死循环（jdk1.7之前）：1.7时候使用的是头插法，在多线程情况下会导致环形链出现，形成死循环。1.8之后使用尾插法，扩容时候会保持原有的链表元素顺序，不会出现环形链问题。
• 多线程put可能导致元素丢失：多线程同时执行put操作，如果计算出来的索引位置是一样的，那么会造成前一个key被后一个key覆盖，从而导致元素的丢失。
• put和get并发，可能导致get为null

19.有什么办法能解决HashMap线程不安全的问题呢？

java中有hashTable，Collections.synchronizedMap以及ConcurrentHashMap可以实现线程安全

• hashTable是直接在操作方法上加上synchronized关键字，锁住整个table数组，粒度比较大。
• Collections.synchronized是使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内部通过对象锁实现
• ConcurrenthashMap在1.7中使用分段锁实现，在jdk1.8中使用cas+Synchronized

20.能具体说一下ConcurrentHashmap的实现吗？

ConcurrentHashmap线程安全在jdk1.7版本是基于分段锁 实现，在jdk1.8是基于CAS+synchronized 实现。

CAS+synchronized
jdk1.8实现线程安全不是在数据结构上下功夫，它的数据结构和HashMap是一样的，数组+链表+红黑树。它实现线
程安全的关键点在于put流程。

21.讲讲LinkedHashMap怎么实现有序的

HashMap是无序的，想要实现有序可以使用LinkedHashMap或者TreeMap

LinkedHashMap维护了一个双向链表，有头尾节点，同时LinkedHashMap节点Entry内部除了继承HashMap的Node属性，还有before和agter用于标识前置节点和后置节点

22.讲讲TreeMap是怎么实现有序的

TreeMap是按照Key的自然顺序或者Comprator的顺序进行排序，内部是通过红黑树来实现。所以要么key所属的类实现Comprator接口，或者自定义一个Comprator的接口比较器，传给TreeMap
进行比较。

23.讲讲HashSet的底层实现？

HashSet的底层就是基于HashMap实现的，除了clone（）、writeObject（）、readObject是hashSet自己实现的外，其他都是调用hashmap方法进行实现的