2_Java集合

Java集合面试题汇总

1. 常见的集合有哪些？

• Java的集合类主要由两个根接口Collection和Map派生出来的。
• Collection：
  • List：代表有序可重复集合，可直接根据元素的索引来访问
  • Set：代表无序不可重复集合，只能根据元素本身来访问
• Map：
  • Map：代表存储key-value对的集合，可以根据元素的key来访问value

2. 集合分类有哪些？

• List：
  • ArrayList：底层为数组Object[] elementData；线程不安全；第一次扩容为10，后续按1.5倍扩容；改查效率高
  • LinkedList：底层为双向链表Node结点；线程不安全；增删效率高
  • Vector：底层为数组Object[] elementData；线程安全；第一次扩容为10，后续按2倍扩容
• Set：
  • HashSet：底层是HashMap；数组+链表+红黑树；线程不安全；第一次扩容为16，后续按0.75倍扩容，直至变成树
    • LinkedHashSet：底层是LinkedHashMap；数组+双向链表；允许按插入顺序取出元素
  • TreeSet：底层是TreeMap；通过比较器，实现元素的排序
• Map：
  • HashMap：底层是key-value键值对存储，数组+链表+红黑树；线程不安全；第一次扩容为16，后续按0.75倍扩容，直至变成树
    • LinkedHashMap：
  • HashTable：底层是key-value键值对存储；存储元素的键值对不能为null；线程安全
    • Properties
  • SortedMap
    • TreeMap：使用无参也是无序的；但是也带比较器的构造器，可以实现键排序

3. Arraylist与 LinkedList 异同点？

• Arraylist 底层使用的是Object数组；LinkedList 底层使用的是双向循环链表数据结构；
• Arraylist 改查效率高；LinkedList增删效率高
• 都是线程不安全的

4.说一说ArrayList 的扩容机制？

• ArrayList扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。默认情况下，新的容量会是原容量的1.5倍。

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

• 数组+链表+红黑树
• 当链表超过 8 且数据总量table超过 64 才会转红黑树

6. 解决hash冲突的办法有哪些？HashMap用的哪种？

• 开放定址法（找一个hash不冲突的地方）、在哈希法（hash函数计算）

• 链地址法：将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。

7. HashMap默认加载因子是多少？为什么是 0.75，不是0.6 或者 0.8 ？

• 0.75是对空间和时间效率的一个平衡选择

• 如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值

• 相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于

8. HashMap 中 key 的存储索引是怎么计算的？

• 取key的 hashCode 值、根据 hashcode 计算出hash值、通过取模计算下标

9. HashMap 的put方法流程？

• 首先根据 key 的值计算 hash 值，找到该元素在数组中存储的下标；
• 如果数组是空的，则调用 resize 进行初始化；如果没有哈希冲突直接放在对应的数组下标里；
• 如果冲突了，且 key 已经存在，就覆盖掉 value；
• 如果冲突后，发现该节点是红黑树，就将这个节点挂在树上；
• 如果冲突后是链表，判断该链表是否大于 8 ，如果大于 8 并且数组容量小于 64，就进行扩容；如果链表节点大于 8 并且数组的容量大于 64，则将这个结构转换为红黑树；否则，链表插入键值对，若 key 存在，就覆盖掉 value。

10. HashMap 的扩容方式？

• HashMap 在容量超过负载因子所定义的临界值之后，就会扩容。Java 里的数组是无法自动扩容的，方法

  是将 HashMap 的大小扩大为原来数组的两倍，并将原来的对象放入新的数组中。

11. HashMap为什么线程不安全？

• 多线程的put可能导致元素的丢失。如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失
• put和get并发时，可能导致get为null。

12. ConcurrentHashMap 的实现原理是什么?

• 数组 +链表+红黑树+ CAS + synchronized 实现更加低粒度的锁,也就是说只需要锁住这个链表头结点（红黑树的根节点），就不会影响其他的哈希桶元素的读写，大大提高了并发度
• 数组扩容，ConcurrentHashMap引入了多线程并发扩容，多个线程对原始数组进行分片，每个线程去负责一个分片的数据迁移，从而提升了扩容的效率
• ConcurrentHashMap中有size方法来获取总的元素个数，在多线程并发场景下，为保证原子性的前提下去实现元素个数的累加的性能是很低的。所以进行了两个点的优化
  • 当线程竞争不激烈时，直接采用cas算法来实现元素个数的原子递增
  • 当线程竞争激烈时，使用数组来维护元素个数，如果要增加总元素个数时，直接从数组中随机选取一个，再通过cas算法来实现原子递增。它的核心思想是引入了数组来实现对并发更新的一个负载。

13. ConcurrentHashMap 的 put 方法执行逻辑是什么？

• 根据 key 计算出 hash值。判断是否需要进行初始化。
• 定位到 Node，拿到首节点 f，判断首节点 f：
  • 如果为 null ，则通过cas的方式尝试添加。
  • 如果为 f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容。
  • 如果都不满足 ，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入。
• 当在链表长度达到8的时候，数组扩容或者将链表转换为红黑树

14. ConcurrentHashMap 的 get 方法是否要加锁，为什么？

• get 方法不需要加锁。因为 Node 的元素 val 和指针 next 是用 volatile 修饰的，在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。

15. ConcurrentHashMap 不支持 key 或者 value 为null 的原因？

• 没有关系。哈希桶 table 用volatile修饰主要是保证在数组扩容的时候保证可见性。

16. ConcurrentHashMap 不支持 key 或者 value 为null 的原因？

• 因为 ConcurrentHashMap 是用于多线程的 ，如果map.get(key) 得到了 null ，无法判断，是映射的value是 null ，还是没有找到对应的key而为 null ，这就有了二义性。

17. ConcurrentHashMap 和Hashtable的效率哪个更高？为什么？

• ConcurrentHashMap 的效率要高于Hashtable，因为Hashtable给整个哈希表加了一把大锁从而实现线程安全；而ConcurrentHashMap 的锁粒度更低，给链表头结点加锁

18. 说一下Hashtable的锁机制 ?

• Hashtable是使用Synchronized来实现线程安全的，给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞等待需要的锁被释放，性能很差

19. HashSet 和 HashMap 区别?

20. Collection框架中实现比较要怎么做？

• 实体类实现Comparable接口，并实现 compareTo(T t) 方法，称为内部比较器。
• 创建一个外部比较器，这个外部比较器要实现Comparator接口的 compare(T t1, T t2)方法。

21. Iterator 和 ListIterator 有什么区别？

• 遍历。使用Iterator，可以遍历所有集合，如Map，List，Set；但只能在向前方向上遍历集合中的元素。使用ListIterator，只能遍历List实现的对象，但可以向前和向后遍历集合中的元素
• 添加元素。Iterator无法向集合中添加元素；而，ListIteror可以向集合添加元素。
• 修改元素。Iterator无法修改集合中的元素；而，ListIterator可以使用set()修改集合中的元素
• 索引。Iterator无法获取集合中元素的索引；而，使用ListIterator，可以获取集合中元素的索引。

22. 讲一讲快速失败(fail-fast)和安全失败(fail-safe)

• 快速失败(fail-fast)

  • 在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。
  • java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），比如HashMap、ArrayList 这些集合类。

• 安全失败(fail-safe)

  • 采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

  • 场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改，比

    如：ConcurrentHashMap。