1. HashMap的内部实现原理是什么?

HashMap内部实现原理是数组+链表,通过散列算法将key值散列到数组中,如果到相同的位置,则通过拉链法解决散列冲突。在JDK8中新增了红黑树结构,当HashMap中的散列冲突链表结构超过8个数据时,会从链表结构转换为红黑树结构。

2. HashMap的key值能否是null,如果能,key=null如何存储以及如何读取的?如果不能,为什么?

HashMap的key值可以是null。如果key=null,则会将它放置在数组下标为0的位置。

3. HashMap如何实现扩容?

HashMap扩容和初始容器大小与负载因子有关。HashMap的初始容器大小为16,默认的负载因子为0.75,当实际容量超过16*0.75=12个元素时会进行扩容。扩容后的容器大小是扩容前的2倍,第一次扩容后的容器大小为32。

4. 设置HashMap的容量有没有注意的地方,为什么?

指定HashMap的容量时,建议是2的幂次方。

HashMap在寻址是会key的hash值与容器长度做与运算,(n - 1) & hash。当n的长度为2的幂次方时,n-1的二进制形式就会是111111,这样与操作效率会非常的快。

5. HashMap是否是线程安全的?如果不是,多线程下并发操作它可能会带来什么问题?如果是,它是怎么实现的?

HashMap不是线程安全的。如果在多线程下并发操作不仅会导致脏数据,甚至可能会造成死循环。(关于死循环产生的原因参考https://www.cnblogs.com/yulinfeng/p/8558983.html

6. LinkedHashMap的内部实现原理是什么?它是否支持key=null?

LinkedHashMap是插入有序的Map集合。它直接继承了HashMap,所以很多都直接复用了HashMap方法,所以也支持key=null。它在内部除了沿用HashMap的底层结构,还单独维护了一个双向链表,在对Map进行put操作时,同时还会将数据写到了链表的尾部,保证了插入有序。

7. TreeMap的内部实现原理是什么?它是否支持key=null?

TreeMap结构也是有序的,不同的是它是字典有序,由于它底层是红黑树结构,插入时会进行比较key值的顺序,所以不允许key=null的情况。

8. 介绍下Hashtable

Hashtable是线程安全的Map类型,但它的线程安全代价是为整个散列表加锁,效率很低,几乎已经废弃。如果要使用线程安全的Map,应该使用ConcurrentHashMap,它的实现是分段锁,能最大的提高效率。

9. 以上三种Map类型分别可以应用到哪些场景?你在哪些场景下使用过?

HashMap的使用场景很多,这个使用场景就太多了,比如用作本地缓存。

LinkedHashMap因为它的链表结构可以实现LRU(最近最少使用),即缓存空间有限,当元素多余缓存空间,可淘汰掉最近最少使用的元素。在LinkedHashMap维护了一个accessOrder字段,默认为false,当设置为true时,如果访问一个key值,就会将这个元素放置链表头部,这样在链表尾部的元素就是不常用的元素,空间不足直接remove末尾的元素即可。所以当要实现LRU缓存时,就可以将accessOrder设置为true实现。

TreeMap没有实际应用过,如果有需要排序的场景则使用TreeMap

Set

10. HashSet的内部实现原理是什么,它有什么特点?

HashSet集合的特点是不允许有重复的元素,且无序的,允许null值。它在内部维护一个HashMap,存储在HashSet中的元素实际上存储在HashMap的key中。

11. LinkedHashSet的内部实现原理是什么,它有什么特点?

LinkedHashSet继承自HashMap,在内部维护一个双向链表保证插入有序,允许null值。

12. TreeSet的内部实现原理是什么,它有什么特点?

TreeSet是一个有序的集合,它的作用是提供有序的Set集合,TreeSet是基于TreeMap实现的。不允许有null值。

13. 以上三种Set类型分别可以应用到哪些场景?你在哪些场景下使用过?

HashSet可应用于批量查询时去重。

如果需要返回的数据和入参的数据顺序一致则可以使用LinkedHashSet。

List

14. ArrayList的内部实现原理什么?

底层通过数组实现,创建一个ArrayList对象实例时不会初始化数组,当插入第一条数据时会创建一个大小为10的数组。

15. 既然ArrayList的底层实现是数组,那定义ArrayList时,需要定义它的大小吗?

可以不用定义容器的大小,默认大小为10,当容量大小不足时此时将会进行扩容。

16. ArrayList的扩容机制是什么?

每次新增的容量是旧容量的一半,扩容后调用System.arraycopy方法拷贝到新的数组。

17. 如果初始化ArrayList时,定义一个容量大小为11,此时扩容了几次,容量大小为16呢?

不进行扩容。

18. LinkedList的内部实现原理是什么?

底层通过链表实现,所以不存在扩容。

19. Vector和ArrayList、LinkedList的区别?

Vector是线程安全的额,ArrayList、LinkedList不是线程安全的。Vector的线程安全是为每个方法加上synchronized关键字,效率不高,不常用。

20. ArrayList与LinkedList分别可以应用到哪些场景?

大多数情况下使用ArrayList,因为ArrayList是数组实现,它随机读取的速度更快,但插入指定位置慢;LinkedList由于是链表实现,所以随机读取的速度慢,但插入指定位置快。

关注CoderBuff公众号,回复“面试”获取更多
08-19 10:56