Java集合面试题汇总

2019-03-22 16:58:20

标签： 转载 Java 集合 面试题

## List、Set 和 Map 介绍

List 和 Set 是继承于 Collection 的两个接口，Map 是 Java.util 包中的接口，Collection 和 Map 没有关系，是相互独立的，但都是属于集合类的一部分。

- List 是有序的集合，可以包含重复的元素，提供了按索引访问的方式
- Set 是无序的集合，不可以包含重复的元素
- Map 是Key-Value 对，不能包含重复的key，但是可以包含相同的 value

## ArrayList 和 LinkedList区别

`ArrayList`

- 数组
- 增删元素和扩容的时候慢，通过索引查询快，通过对象查索引慢
- 当数组无法容纳下此次添加的元素时进行扩容
- 扩容之后容量为原来的1.5倍

`LinkedList`

- 双向链表
- 增删快，通过索引查询慢，通过对象查索引慢

## HashMap 介绍

- JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题
- 为什么线程不安全？多线程PUT操作时可能会覆盖刚PUT进去的值；扩容操作会让链表形成环形数据结构，形成死循环
- 容量的默认大小是 16，负载因子是 0.75
- 为什么容量是2的倍数？在根据hashcode查找数组中元素时，取模性能远远低于与性能，且和2^n-1进行与操作能保证各种不同的hashcode对应的元素也能均匀分布在数组中

## ConcurrentHashMap原理

ConcurrentHashMap 和 HashTable 都是线程安全的，HashTable 在每次同步执行时都要锁住整个结构。ConcurrentHashMap 锁的方式是稍微细粒度的。 ConcurrentHashMap 将 hash 表分为 16 个桶（默认值） 最大并发个数就是Segment的个数，默认值是16，可以通过构造函数改变一经创建不可更改，这个值就是并发的粒度，每一个segment下面管理一个table数组，加锁的时候其实锁住的是整个segment

`Java7`

![](http://file.song-z.com/res/md/image/20190322/1553245374471_6354.jpg)

ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。HashEntry 用来封装映射表的键 / 值对；Segment 用来充当锁的角色，每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。

`Java8`

![](http://file.song-z.com/res/md/image/20190322/1553245385277_3278.jpg)

- 为进一步提高并发性，放弃了分段锁，锁的级别控制在了更细粒度的table元素级别，也就是说只需要锁住这个链表的head节点，并不会影响其他的table元素的读写，好处在于并发的粒度更细，影响更小，从而并发效率更好
- 使用CAS + synchronized 来保证实现put操作：如果Key对应的数组元素为null，则通过CAS操作将其设置为当前值。如果Key对应的数组元素（也即链表表头或者树的根元素）不为null，则对该元素使用synchronized关键字申请锁，然后进行操作。如果该put操作使得当前链表长度超过一定阈值，则将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(log(N))，插入操作完成之后如果所有元素的数量大于当前容量（默认16）*负载因子（默认0.75）就进行扩容。

上一篇：JAVA中BigDecimal加减乘除下一篇：Java容易搞错的知识点

分享到：QQ空间新浪微博腾讯微博人人网微信

登录