- 问 Java中有哪些容器(集合类)
答: Java中的集合类主要是由Collection和Map这两个接口派生出来的,其中Collection接口又派生出三个子接口,分别是Set,List,Queue.所有的Java集合类,都是Set,List,Queue.Map这四个接口的实现类,这四个接口将集合分成了四个大类,其中
- Set代表无序的,元素不可重复的集合.
- List代表有序的,元素可以重复的集合.
- Queue代表先进先出(FIFO)的队列
- Map代表具有映射关系(Key-Value)的集合
拓展阅读
Collection体系的继承树
Collection体系的继承树
Map体系的继承树
Map体系的继承树
注:紫色框体代表接口,其中加粗的代表四类集合的接口. 蓝色框代表实现类,其中有阴影的是常用实现类
- 问:Java中的容器,线程安全和线程不安全的分别有哪些?
答: java.util包下的集合类大部分都是线程不安全的,例如常用的HashSet.TreeSet.ArrayList.LinkedList.ArrayDeque.HashMap.TreeMap,这些都是线程不安全的集合类,优点是性能好. 如果需要使用线程安全的集合类,则可以使用Collections工具类提供的synchronizedXxx(),将这些集合类包装成线程安全的集合类
java.util包下也有线程安全的集合类,例如Vector,Hashtable.这些集合类都是比较古老的API. 虽然实现了线程安全,但是性能很差.
从Java5开始,Java在java.util.concurrent包下提供了大量支持高效并发访问的集合类,它们既能包装良好的访问性能,有能包装线程安全.这些集合类可以分为两部分,它们的特征如下:
- 以Concurrent开头的集合类:
以Concurrent开头的集合类代表了支持并发访问的集合,它们可以支持多个线程并发写入访问,这些写入的线程的所有操作都是线程安全的,但读取操作不必锁定.以Concurrent开头的集合类采用了更复杂的算法来保证永远不会锁住整个集合,因此在并发写入时有较好的性能. - 以CopyOnWrite开头的集合类:
以CopyOnWrite开头的集合类采用复制底层数组的方式来实现写操作.当线程对此类集合执行读操作时,线程将会直接读取集合本身,无须加锁与阻塞.当线程对此类集合执行写入操作时,集合会在底层复制一份新的数组,接下来对新的数组执行写入操作. 由于对集合的写入操作都是对数组的副本执行操作,因此它是线程安全的.
拓展阅读
java.util.concurrent包下的线程安全的类的体系结构
concurrent包下线程安全的集合类
- 问 Map接口有哪些实现类?
答:常用的有HashMap.LinkedHashMap.TreeMap.ConcurrentHashMap.
对于无需排序的场景,优先考虑HashMap. 因为它是性能最好的Map实现. 如果要保证线程安全,则使用ConcurrentHashMap. 它的性能好于Hashtable,因为在put时会采用分段锁/CAS的加锁机制,而不是像HashTable,put和get都做同步处理.
如果需要排序,按插入顺序排序则可以使用LinkHashMap. 如果要Key按照自然顺序排序甚至自定义顺序排序,则可以选择TreeMap. 如果要保证线程安全,则可以使用Collections工具类包装成线程安全的Map - 问: 描述下Map put的过程
答: HashMap最经典,以此为例
- 首次扩容
先判断数组是否为空,若数组为空则进行第一次扩容(resize) - 计算索引
通过hash算法,计算键值对在数组中的索引 - 插入数据
如果当前位置为空,则直接插入数据
如果当前位置元素非空,且Key存在,则直接覆盖其value
如果当前位置元素非空,且key不存在,则将数据链到链表末端
若链表长度达到8,则将链表转成红黑树,并将数据插入树中 - 再次扩容
如果数组元素个数(size)吃过threshold,则再次进行扩容操作.
拓展阅读
HashMap添加数据的详细过程
HashMap添加数据过程
- 问: 如何得到一个线程安全的Map?
答: 1. 使用Collections工具类,将线程不安全的Map包装成线程安全的Map;
- 使用java.util.concurrent包下的Map,如ConcurrentHashMap;
- 不建议使用HashTable,虽然线程安全,但性能较差.
- 问 HashMap有啥特点
- HashMap是线程不安全的实现,高效率
- HashMap可以使用null作为key或value
HashMap为什么线程不安全?
答: HashMap在并发执行put操作时,可能会导致形成循环链表,从而引起死循环.HashMap如何实现线程安全?
- 直接使用Hashtable类
- 直接使用ConcurrentHashMap
- 使用Collections将HashMap包装成线程安全的Map
-
问 介绍下ConcurrentHashMap是如何实现的?
答: jdk1.7和jdk1.8中不同
在1.7中ConcurrentHashMap由Segment数据结构和HashEntry数组结构构成. 采取分段锁来保证安全性. Segment扮演锁的角色,HashEntry用于存储键值对数据.
在jdk1.7中ConcurrentHashMap的数据结构
在1.8中的实现已经摒弃了Segment的概念,直接使用了Node数组+链表+红黑树的数据结构来实现.并发控制使用Synchronized和CAS来操作.
