Java基础(二)

• 问 Java中有哪些容器(集合类)
  答: Java中的集合类主要是由Collection和Map这两个接口派生出来的,其中Collection接口又派生出三个子接口,分别是Set,List,Queue.所有的Java集合类,都是Set,List,Queue.Map这四个接口的实现类,这四个接口将集合分成了四个大类,其中

1. Set代表无序的,元素不可重复的集合.
2. List代表有序的,元素可以重复的集合.
3. Queue代表先进先出(FIFO)的队列
4. 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包下提供了大量支持高效并发访问的集合类,它们既能包装良好的访问性能,有能包装线程安全.这些集合类可以分为两部分,它们的特征如下:

1. 以Concurrent开头的集合类:
   以Concurrent开头的集合类代表了支持并发访问的集合,它们可以支持多个线程并发写入访问,这些写入的线程的所有操作都是线程安全的,但读取操作不必锁定.以Concurrent开头的集合类采用了更复杂的算法来保证永远不会锁住整个集合,因此在并发写入时有较好的性能.
2. 以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最经典,以此为例

1. 首次扩容
   先判断数组是否为空,若数组为空则进行第一次扩容(resize)
2. 计算索引
   通过hash算法,计算键值对在数组中的索引
3. 插入数据
   如果当前位置为空,则直接插入数据
   如果当前位置元素非空,且Key存在,则直接覆盖其value
   如果当前位置元素非空,且key不存在,则将数据链到链表末端
   若链表长度达到8,则将链表转成红黑树,并将数据插入树中
4. 再次扩容
   如果数组元素个数(size)吃过threshold,则再次进行扩容操作.

拓展阅读

HashMap添加数据的详细过程

HashMap添加数据过程

• 问: 如何得到一个线程安全的Map?
  答: 1. 使用Collections工具类,将线程不安全的Map包装成线程安全的Map;

2. 使用java.util.concurrent包下的Map,如ConcurrentHashMap;
3. 不建议使用HashTable,虽然线程安全,但性能较差.

• 问 HashMap有啥特点

1. HashMap是线程不安全的实现,高效率
2. HashMap可以使用null作为key或value

• HashMap为什么线程不安全?
  答: HashMap在并发执行put操作时,可能会导致形成循环链表,从而引起死循环.

• HashMap如何实现线程安全?

1. 直接使用Hashtable类
2. 直接使用ConcurrentHashMap
3. 使用Collections将HashMap包装成线程安全的Map

• 问 介绍下ConcurrentHashMap是如何实现的?
  答: jdk1.7和jdk1.8中不同
  在1.7中ConcurrentHashMap由Segment数据结构和HashEntry数组结构构成. 采取分段锁来保证安全性. Segment扮演锁的角色,HashEntry用于存储键值对数据.

  
  在jdk1.7中ConcurrentHashMap的数据结构
  

  在1.8中的实现已经摒弃了Segment的概念,直接使用了Node数组+链表+红黑树的数据结构来实现.并发控制使用Synchronized和CAS来操作.