集合类(一)

  Java   20分钟   283浏览   0评论

2.1 Java中有哪些容器(集合类)?

参考答案

Java中的集合类主要由Collection和Map这两个接口派生而出,其中Collection接口又派生出三个子接口,分别是Set、List、Queue。所有的Java集合类,都是Set、List、Queue、Map这四个接口的实现类,这四个接口将集合分成了四大类,其中

  • Set代表无序的,元素不可重复的集合;
  • List代表有序的,元素可以重复的集合;
  • Queue代表先进先出(FIFO)的队列;
  • Map代表具有映射关系(key-value)的集合。

这些接口拥有众多的实现类,其中最常用的实现类有HashSet、TreeSet、ArrayList、LinkedList、ArrayDeque、HashMap、TreeMap等。

扩展阅读

Collection体系的继承树:

img

Map体系的继承树:

img

注:紫色框体代表接口,其中加粗的是代表四类集合的接口。蓝色框体代表实现类,其中有阴影的是常用实现类。

2.2 Java中的容器,线程安全和线程不安全的分别有哪些?

参考答案

java.util包下的集合类大部分都是线程不安全的,例如我们常用的HashSet、TreeSet、ArrayList、LinkedList、ArrayDeque、HashMap、TreeMap,这些都是线程不安全的集合类,但是它们的优点是性能好。如果需要使用线程安全的集合类,则可以使用Collections工具类提供的synchronizedXxx()方法,将这些集合类包装成线程安全的集合类。

java.util包下也有线程安全的集合类,例如Vector、Hashtable。这些集合类都是比较古老的API,虽然实现了线程安全,但是性能很差。所以即便是需要使用线程安全的集合类,也建议将线程不安全的集合类包装成线程安全集合类的方式,而不是直接使用这些古老的API。

从Java5开始,Java在java.util.concurrent包下提供了大量支持高效并发访问的集合类,它们既能包装良好的访问性能,有能包装线程安全。这些集合类可以分为两部分,它们的特征如下:

  • 以Concurrent开头的集合类:

    以Concurrent开头的集合类代表了支持并发访问的集合,它们可以支持多个线程并发写入访问,这些写入线程的所有操作都是线程安全的,但读取操作不必锁定。以Concurrent开头的集合类采用了更复杂的算法来保证永远不会锁住整个集合,因此在并发写入时有较好的性能。

  • 以CopyOnWrite开头的集合类:

    以CopyOnWrite开头的集合类采用复制底层数组的方式来实现写操作。当线程对此类集合执行读取操作时,线程将会直接读取集合本身,无须加锁与阻塞。当线程对此类集合执行写入操作时,集合会在底层复制一份新的数组,接下来对新的数组执行写入操作。由于对集合的写入操作都是对数组的副本执行操作,因此它是线程安全的。

扩展阅读

java.util.concurrent包下线程安全的集合类的体系结构:

img

2.3 Map接口有哪些实现类?

参考答案

Map接口有很多实现类,其中比较常用的有HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap。

对于不需要排序的场景,优先考虑使用HashMap,因为它是性能最好的Map实现。如果需要保证线程安全,则可以使用ConcurrentHashMap。它的性能好于Hashtable,因为它在put时采用分段锁/CAS的加锁机制,而不是像Hashtable那样,无论是put还是get都做同步处理。

对于需要排序的场景,如果需要按插入顺序排序则可以使用LinkedHashMap,如果需要将key按自然顺序排列甚至是自定义顺序排列,则可以选择TreeMap。如果需要保证线程安全,则可以使用Collections工具类将上述实现类包装成线程安全的Map。

2.4 描述一下Map put的过程

参考答案

HashMap是最经典的Map实现,下面以它的视角介绍put的过程:

  1. 首次扩容:

    先判断数组是否为空,若数组为空则进行第一次扩容(resize);

  2. 计算索引:

    通过hash算法,计算键值对在数组中的索引;

  3. 插入数据:

    • 如果当前位置元素为空,则直接插入数据;
    • 如果当前位置元素非空,且key已存在,则直接覆盖其value;
    • 如果当前位置元素非空,且key不存在,则将数据链到链表末端;
    • 若链表长度达到8,则将链表转换成红黑树,并将数据插入树中;
  4. 再次扩容

    如果数组中元素个数(size)超过threshold,则再次进行扩容操作。

扩展阅读

HashMap添加数据的详细过程,如下图:

img

2.5 如何得到一个线程安全的Map?

参考答案

  1. 使用Collections工具类,将线程不安全的Map包装成线程安全的Map;
  2. 使用java.util.concurrent包下的Map,如ConcurrentHashMap;
  3. 不建议使用Hashtable,虽然Hashtable是线程安全的,但是性能较差。

2.6 HashMap有什么特点?

参考答案

  1. HashMap是线程不安全的实现;
  2. HashMap可以使用null作为key或value。

2.7 JDK7和JDK8中的HashMap有什么区别?

参考答案

JDK7中的HashMap,是基于数组+链表来实现的,它的底层维护一个Entry数组。它会根据计算的hashCode将对应的KV键值对存储到该数组中,一旦发生hashCode冲突,那么就会将该KV键值对放到对应的已有元素的后面, 此时便形成了一个链表式的存储结构。

JDK7中HashMap的实现方案有一个明显的缺点,即当Hash冲突严重时,在桶上形成的链表会变得越来越长,这样在查询时的效率就会越来越低,其时间复杂度为O(N)。

JDK8中的HashMap,是基于数组+链表+红黑树来实现的,它的底层维护一个Node数组。当链表的存储的数据个数大于等于8的时候,不再采用链表存储,而采用了红黑树存储结构。这么做主要是在查询的时间复杂度上进行优化,链表为O(N),而红黑树一直是O(logN),可以大大的提高查找性能。

2.8 介绍一下HashMap底层的实现原理

参考答案

它基于hash算法,通过put方法和get方法存储和获取对象。

存储对象时,我们将K/V传给put方法时,它调用K的hashCode计算hash从而得到bucket位置,进一步存储,HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时,我们将K传给get,它调用hashCode计算hash从而得到bucket位置,并进一步调用equals()方法确定键值对。

如果发生碰撞的时候,HashMap通过链表将产生碰撞冲突的元素组织起来。在Java 8中,如果一个bucket中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度。

2.9 介绍一下HashMap的扩容机制

参考答案

  1. 数组的初始容量为16,而容量是以2的次方扩充的,一是为了提高性能使用足够大的数组,二是为了能使用位运算代替取模预算(据说提升了5~8倍)。
  2. 数组是否需要扩充是通过负载因子判断的,如果当前元素个数为数组容量的0.75时,就会扩充数组。这个0.75就是默认的负载因子,可由构造器传入。我们也可以设置大于1的负载因子,这样数组就不会扩充,牺牲性能,节省内存。
  3. 为了解决碰撞,数组中的元素是单向链表类型。当链表长度到达一个阈值时(7或8),会将链表转换成红黑树提高性能。而当链表长度缩小到另一个阈值时(6),又会将红黑树转换回单向链表提高性能。
  4. 对于第三点补充说明,检查链表长度转换成红黑树之前,还会先检测当前数组数组是否到达一个阈值(64),如果没有到达这个容量,会放弃转换,先去扩充数组。所以上面也说了链表长度的阈值是7或8,因为会有一次放弃转换的操作。

扩展阅读

例如我们从16扩展为32时,具体的变化如下所示:

img

因此元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:

img

因此,我们在扩充HashMap的时候,不需要重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图:

img

这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。

2.10 HashMap中的循环链表是如何产生的?

参考答案

在多线程的情况下,当重新调整HashMap大小的时候,就会存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历。如果条件竞争发生了,那么就会产生死循环了。

2.11 HashMap为什么用红黑树而不用B树?

参考答案

B/B+树多用于外存上时,B/B+也被成为一个磁盘友好的数据结构。

HashMap本来是数组+链表的形式,链表由于其查找慢的特点,所以需要被查找效率更高的树结构来替换。如果用B/B+树的话,在数据量不是很多的情况下,数据都会“挤在”一个结点里面,这个时候遍历效率就退化成了链表。

2.12 HashMap为什么线程不安全?

参考答案

HashMap在并发执行put操作时,可能会导致形成循环链表,从而引起死循环。

2.13 HashMap如何实现线程安全?

参考答案

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

2.14 HashMap是如何解决哈希冲突的?

参考答案

为了解决碰撞,数组中的元素是单向链表类型。当链表长度到达一个阈值时,会将链表转换成红黑树提高性能。而当链表长度缩小到另一个阈值时,又会将红黑树转换回单向链表提高性能。

2.15 说一说HashMap和HashTable的区别

参考答案

  1. Hashtable是一个线程安全的Map实现,但HashMap是线程不安全的实现,所以HashMap比Hashtable的性能高一点。
  2. Hashtable不允许使用null作为key和value,如果试图把null值放进Hashtable中,将会引发空指针异常,但HashMap可以使用null作为key或value。

扩展阅读

从Hashtable的类名上就可以看出它是一个古老的类,它的命名甚至没有遵守Java的命名规范:每个单词的首字母都应该大写。也许当初开发Hashtable的工程师也没有注意到这一点,后来大量Java程序中使用了Hashtable类,所以这个类名也就不能改为HashTable了,否则将导致大量程序需要改写。

与Vector类似的是,尽量少用Hashtable实现类,即使需要创建线程安全的Map实现类,也无须使用Hashtable实现类,可以通过Collections工具类把HashMap变成线程安全的Map。

2.16 HashMap与ConcurrentHashMap有什么区别?

参考答案

HashMap是非线程安全的,这意味着不应该在多线程中对这些Map进行修改操作,否则会产生数据不一致的问题,甚至还会因为并发插入元素而导致链表成环,这样在查找时就会发生死循环,影响到整个应用程序。

Collections工具类可以将一个Map转换成线程安全的实现,其实也就是通过一个包装类,然后把所有功能都委托给传入的Map,而包装类是基于synchronized关键字来保证线程安全的(Hashtable也是基于synchronized关键字),底层使用的是互斥锁,性能与吞吐量比较低。

ConcurrentHashMap的实现细节远没有这么简单,因此性能也要高上许多。它没有使用一个全局锁来锁住自己,而是采用了减少锁粒度的方法,尽量减少因为竞争锁而导致的阻塞与冲突,而且ConcurrentHashMap的检索操作是不需要锁的。

2.17 介绍一下ConcurrentHashMap是怎么实现的?

参考答案

JDK 1.7中的实现:

在 jdk 1.7 中,ConcurrentHashMap 是由 Segment 数据结构和 HashEntry 数组结构构成,采取分段锁来保证安全性。Segment 是 ReentrantLock 重入锁,在 ConcurrentHashMap 中扮演锁的角色,HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组,一个 Segment 里包含一个 HashEntry 数组,Segment 的结构和 HashMap 类似,是一个数组和链表结构。

img

JDK 1.8中的实现:

JDK1.8 的实现已经摒弃了 Segment 的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 Synchronized 和 CAS 来操作,整个看起来就像是优化过且线程安全的 HashMap,虽然在 JDK1.8 中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本。

img

2.18 ConcurrentHashMap是怎么分段分组的?

参考答案

get操作:

Segment的get操作实现非常简单和高效,先经过一次再散列,然后使用这个散列值通过散列运算定位到 Segment,再通过散列算法定位到元素。get操作的高效之处在于整个get过程都不需要加锁,除非读到空的值才会加锁重读。原因就是将使用的共享变量定义成 volatile 类型。

put操作:

当执行put操作时,会经历两个步骤:

  1. 判断是否需要扩容;
  2. 定位到添加元素的位置,将其放入 HashEntry 数组中。

插入过程会进行第一次 key 的 hash 来定位 Segment 的位置,如果该 Segment 还没有初始化,即通过 CAS 操作进行赋值,然后进行第二次 hash 操作,找到相应的 HashEntry 的位置,这里会利用继承过来的锁的特性,在将数据插入指定的 HashEntry 位置时(尾插法),会通过继承 ReentrantLock 的 tryLock() 方法尝试去获取锁,如果获取成功就直接插入相应的位置,如果已经有线程获取该Segment的锁,那当前线程会以自旋的方式去继续的调用 tryLock() 方法去获取锁,超过指定次数就挂起,等待唤醒。

2.19 说一说你对LinkedHashMap的理解

参考答案

LinkedHashMap使用双向链表来维护key-value对的顺序(其实只需要考虑key的顺序),该链表负责维护Map的迭代顺序,迭代顺序与key-value对的插入顺序保持一致。

LinkedHashMap可以避免对HashMap、Hashtable里的key-value对进行排序(只要插入key-value对时保持顺序即可),同时又可避免使用TreeMap所增加的成本。

LinkedHashMap需要维护元素的插入顺序,因此性能略低于HashMap的性能。但因为它以链表来维护内部顺序,所以在迭代访问Map里的全部元素时将有较好的性能。

2.20 请介绍LinkedHashMap的底层原理

参考答案

LinkedHashMap继承于HashMap,它在HashMap的基础上,通过维护一条双向链表,解决了HashMap不能随时保持遍历顺序和插入顺序一致的问题。在实现上,LinkedHashMap很多方法直接继承自HashMap,仅为维护双向链表重写了部分方法。

如下图,淡蓝色的箭头表示前驱引用,红色箭头表示后继引用。每当有新的键值对节点插入时,新节点最终会接在tail引用指向的节点后面。而tail引用则会移动到新的节点上,这样一个双向链表就建立起来了。

如果你觉得文章对你有帮助,那就请作者喝杯咖啡吧☕
微信
支付宝
  0 条评论