java面试-集合

List、Set、Map三者的区别?

List 存储 不唯一 但有序的一组数据；

Set 存储不重复的元素；

Map 存储键值对，key 不能重复，不同key 可以映射到同一个对象；

List 有哪几种？之间有什么区别？

• 底层：ArrayList 底层由数组实现，数组的内存是连续的； LinkedList 底层是双向链表，是不连续的。

• 访问：ArrayList 可随机访问，直接定位到元素；LinkedList 需要遍历，效率比 LinkedList 高。

• 尾部添加或删除元素：ArrayList 不用移动其他元素，直接写入数据，而 LinkedList 需要创建新节点或删除节点，效率比 LinkedList 高；

• 头部或中间的插入或删除元素：ArrayList 需要移动后面的元素，效率比 LinkedList 低；

• 扩容：ArrayList 容量不够时需要扩容，此时效率比较低;

• 线程安全：Vector 跟 ArrayList 实现一致，唯一的区别是使用了 synchronized 保证线程安全；

有哪些 Map 实现类，之间有什么区别？

HashMap 最通用的非线程安全的Map；

HashTable 继承于 Dictionary，键值不允许为NULL，性能不如 HashMap，用 synchrized 保证线程安全，并发性能不如 ConcurrentHashMap；

LinkedHashMap 是 HashMap 的子类，用双向链表记录插入顺序；

TreeMap 实现了 SortedMap 接口，按key升序存储在红黑树；

ConcurrentHashMap 用了CAS + synchronized 关键字实现线程安全，锁粒度比较小，并发性能比较高。

HashMap 的底层数据结构

JDK8 以后，HashMap 使用 数组+链表+红黑树 的结构

HashMap 为什么要有链表转换成红黑树？

为了提升hash冲突时的查找性能，链表的查找性能是O(n)，而红黑树的查找性能是O( log(n) )

HashMap 什么时候使用链表，什么时候使用红黑树？

默认情况下使用链表；

链表长度超过8时，如果数组长度小于64 通过扩容缩短链表，如果数组长度大于64则将链表转换成红黑树以提升访问效率；

如果同一个位置的元素小于6个，就将红黑树转换回链表。

HashMap 的容量有什么限制？这样限制的好处是什么？

HashMap 的容量必须是2的n次方，当我们传入容量时，会计算出大于它的最小的2的n次方；

容量限制为2的n次方的好处是，可以将散列函数的取模运算转换成位运算，也就是容量值减一再与hash 位与运算，从而提高性能；

在扩容时更容易确定数据位置，旧容量与hash位与结果等于0的放在旧位置，等于1的放在新位置，新位置=旧位置+旧容量；

HashMap 的插入流程是怎么样的？

经过四个步骤，第一个步骤，如果数组为空，就初始化数组；

第二个步骤定位数据在数组中的位置；

第三个步骤，放置数据到数组的对应位置；

第四个步骤，如果节点总数超过一定阈值就进行扩容。其中放置数据的过程中，不管存储冲突数据的结构是红黑树还是链表，都遍历所有节点，如果节点的key 和传入数据的key 相等，就更新对应节点，放置数据的过程结束，如果找不到key 相同的节点，就新建节点，如果结构是红黑树，则需要重新平衡，如果结构是链表，并且链表节点数大于8，就将链表转换成红黑树。

HashMap 的扩容流程

分为三步，第一步，创建新数组，新数组的容量是旧数组容量的2倍；

第二步，遍历旧数组；

第三步，针对某个位置下的所有节点，将其hash值与旧容量值进行位与运算，结果等于0的节点，形成一个链表放置到新数组的旧位置，如果链表长度大于8，就转换成红黑树；将其hash值与旧容量值进行位与运算，结果等于1的节点，形成一个链表放置到新数组的新位置，新位置=旧位置+旧容量，如果链表长度大于8，就转换成红黑树；