集合类(二)

  Java   21分钟   269浏览   0评论

2.21 请介绍TreeMap的底层原理

参考答案

TreeMap基于红黑树(Red-Black tree)实现。映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。TreeMap的基本操作containsKey、get、put、remove方法,它的时间复杂度是log(N)。

TreeMap包含几个重要的成员变量:root、size、comparator。其中root是红黑树的根节点。它是Entry类型,Entry是红黑树的节点,它包含了红黑树的6个基本组成:key、value、left、right、parent和color。Entry节点根据根据Key排序,包含的内容是value。Entry中key比较大小是根据比较器comparator来进行判断的。size是红黑树的节点个数。

2.22 Map和Set有什么区别?

参考答案

Set代表无序的,元素不可重复的集合;

Map代表具有映射关系(key-value)的集合,其所有的key是一个Set集合,即key无序且不能重复。

2.23 List和Set有什么区别?

参考答案

Set代表无序的,元素不可重复的集合;

List代表有序的,元素可以重复的集合。

2.24 ArrayList和LinkedList有什么区别?

参考答案

  1. ArrayList的实现是基于数组,LinkedList的实现是基于双向链表;
  2. 对于随机访问ArrayList要优于LinkedList,ArrayList可以根据下标以O(1)时间复杂度对元素进行随机访问,而LinkedList的每一个元素都依靠地址指针和它后一个元素连接在一起,查找某个元素的时间复杂度是O(N);
  3. 对于插入和删除操作,LinkedList要优于ArrayList,因为当元素被添加到LinkedList任意位置的时候,不需要像ArrayList那样重新计算大小或者是更新索引;
  4. LinkedList比ArrayList更占内存,因为LinkedList的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素。

2.25 有哪些线程安全的List?

参考答案

  1. Vector

    Vector是比较古老的API,虽然保证了线程安全,但是由于效率低一般不建议使用。

  2. Collections.SynchronizedList

    SynchronizedList是Collections的内部类,Collections提供了synchronizedList方法,可以将一个线程不安全的List包装成线程安全的List,即SynchronizedList。它比Vector有更好的扩展性和兼容性,但是它所有的方法都带有同步锁,也不是性能最优的List。

  3. CopyOnWriteArrayList

    CopyOnWriteArrayList是Java 1.5在java.util.concurrent包下增加的类,它采用复制底层数组的方式来实现写操作。当线程对此类集合执行读取操作时,线程将会直接读取集合本身,无须加锁与阻塞。当线程对此类集合执行写入操作时,集合会在底层复制一份新的数组,接下来对新的数组执行写入操作。由于对集合的写入操作都是对数组的副本执行操作,因此它是线程安全的。在所有线程安全的List中,它是性能最优的方案。

2.26 介绍一下ArrayList的数据结构?

参考答案

ArrayList的底层是用数组来实现的,默认第一次插入元素时创建大小为10的数组,超出限制时会增加50%的容量,并且数据以 System.arraycopy() 复制到新的数组,因此最好能给出数组大小的预估值。

按数组下标访问元素的性能很高,这是数组的基本优势。直接在数组末尾加入元素的性能也高,但如果按下标插入、删除元素,则要用 System.arraycopy() 来移动部分受影响的元素,性能就变差了,这是基本劣势。

2.27 谈谈CopyOnWriteArrayList的原理

参考答案

CopyOnWriteArrayList是Java并发包里提供的并发类,简单来说它就是一个线程安全且读操作无锁的ArrayList。正如其名字一样,在写操作时会复制一份新的List,在新的List上完成写操作,然后再将原引用指向新的List。这样就保证了写操作的线程安全。

CopyOnWriteArrayList允许线程并发访问读操作,这个时候是没有加锁限制的,性能较高。而写操作的时候,则首先将容器复制一份,然后在新的副本上执行写操作,这个时候写操作是上锁的。结束之后再将原容器的引用指向新容器。注意,在上锁执行写操作的过程中,如果有需要读操作,会作用在原容器上。因此上锁的写操作不会影响到并发访问的读操作。

  • 优点:读操作性能很高,因为无需任何同步措施,比较适用于读多写少的并发场景。在遍历传统的List时,若中途有别的线程对其进行修改,则会抛出ConcurrentModificationException异常。而CopyOnWriteArrayList由于其"读写分离"的思想,遍历和修改操作分别作用在不同的List容器,所以在使用迭代器进行遍历时候,也就不会抛出ConcurrentModificationException异常了。
  • 缺点:一是内存占用问题,毕竟每次执行写操作都要将原容器拷贝一份,数据量大时,对内存压力较大,可能会引起频繁GC。二是无法保证实时性,Vector对于读写操作均加锁同步,可以保证读和写的强一致性。而CopyOnWriteArrayList由于其实现策略的原因,写和读分别作用在新老不同容器上,在写操作执行过程中,读不会阻塞但读取到的却是老容器的数据。

2.28 说一说TreeSet和HashSet的区别

参考答案

HashSet、TreeSet中的元素都是不能重复的,并且它们都是线程不安全的,二者的区别是:

  1. HashSet中的元素可以是null,但TreeSet中的元素不能是null;
  2. HashSet不能保证元素的排列顺序,而TreeSet支持自然排序、定制排序两种排序的方式;
  3. HashSet底层是采用哈希表实现的,而TreeSet底层是采用红黑树实现的。

2.29 说一说HashSet的底层结构

参考答案

HashSet是基于HashMap实现的,默认构造函数是构建一个初始容量为16,负载因子为0.75 的HashMap。它封装了一个 HashMap 对象来存储所有的集合元素,所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存,而 HashMap 的 value 则存储了一个 PRESENT,它是一个静态的 Object 对象。

2.30 BlockingQueue中有哪些方法,为什么这样设计?

参考答案

为了应对不同的业务场景,BlockingQueue 提供了4 组不同的方法用于插入、移除以及对队列中的元素进行检查。如果请求的操作不能得到立即执行的话,每组方法的表现是不同的。这些方法如下:

抛异常 特定值 阻塞 超时
插入 add(e) offer(e) put(e) offer(e, time, unit)
移除 remove() poll() take() poll(time, unit)
检查 element() peek()

四组不同的行为方式含义如下:

  • 抛异常:如果操作无法立即执行,则抛一个异常;
  • 特定值:如果操作无法立即执行,则返回一个特定的值(一般是 true / false)。
  • 阻塞:如果操作无法立即执行,则该方法调用将会发生阻塞,直到能够执行;
  • 超时:如果操作无法立即执行,则该方法调用将会发生阻塞,直到能够执行。但等待时间不会超过给定值,并返回一个特定值以告知该操作是否成功(典型的是true / false)。

2.31 BlockingQueue是怎么实现的?

参考答案

BlockingQueue是一个接口,它的实现类有ArrayBlockingQueue、DelayQueue、 LinkedBlockingQueue、PriorityBlockingQueue、SynchronousQueue等。它们的区别主要体现在存储结构上或对元素操作上的不同,但是对于put与take操作的原理是类似的。下面以ArrayBlockingQueue为例,来说明BlockingQueue的实现原理。

首先看一下ArrayBlockingQueue的构造函数,它初始化了put和take函数中用到的关键成员变量,这两个变量的类型分别是ReentrantLock和Condition。ReentrantLock是AbstractQueuedSynchronizer(AQS)的子类,它的newCondition函数返回的Condition实例,是定义在AQS类内部的ConditionObject类,该类可以直接调用AQS相关的函数。

public ArrayBlockingQueue(int capacity, boolean fair) {
if (capacity <= 0)          throw new IllegalArgumentException();      this.items = new Object[capacity];      lock = new ReentrantLock(fair);      notEmpty = lock.newCondition();      notFull = lock.newCondition();  }

put函数会在队列末尾添加元素,如果队列已经满了,无法添加元素的话,就一直阻塞等待到可以加入为止。函数的源码如下所示。我们会发现put函数使用了wait/notify的机制。与一般生产者-消费者的实现方式不同,同步队列使用ReentrantLock和Condition相结合的机制,即先获得锁,再等待,而不是synchronized和wait的机制。

public void put(E e) throws InterruptedException {      checkNotNull(e);      final ReentrantLock lock = this.lock;      lock.lockInterruptibly();      try {          while (count == items.length)              notFull.await();          enqueue(e);      } finally {          lock.unlock();      }  }

再来看一下消费者调用的take函数,take函数在队列为空时会被阻塞,一直到阻塞队列加入了新的元素。

public E take() throws InterruptedException {      final ReentrantLock lock = this.lock;      lock.lockInterruptibly();      try {          while (count == 0)              notEmpty.await();          return dequeue();      } finally {          lock.unlock();      }  }

扩展阅读

await操作:

我们发现ArrayBlockingQueue并没有使用Object.wait,而是使用的Condition.await,这是为什么呢?Condition对象可以提供和Object的wait和notify一样的行为,但是后者必须先获取synchronized这个内置的monitor锁才能调用,而Condition则必须先获取ReentrantLock。这两种方式在阻塞等待时都会将相应的锁释放掉,但是Condition的等待可以中断,这是二者唯一的区别。

我们先来看一下Condition的await函数,await函数的流程大致如下图所示。await函数主要有三个步骤,一是调用addConditionWaiter函数,在condition wait queue队列中添加一个节点,代表当前线程在等待一个消息。然后调用fullyRelease函数,将持有的锁释放掉,调用的是AQS的函数。最后一直调用isOnSyncQueue函数判断节点是否被转移到sync queue队列上,也就是AQS中等待获取锁的队列。如果没有,则进入阻塞状态,如果已经在队列上,则调用acquireQueued函数重新获取锁。

img

signal操作:

signal函数将condition wait queue队列中队首的线程节点转移等待获取锁的sync queue队列中。这样的话,await函数中调用isOnSyncQueue函数就会返回true,导致await函数进入最后一步重新获取锁的状态。

我们这里来详细解析一下condition wait queue和sync queue两个队列的设计原理。condition wait queue是等待消息的队列,因为阻塞队列为空而进入阻塞状态的take函数操作就是在等待阻塞队列不为空的消息。而sync queue队列则是等待获取锁的队列,take函数获得了消息,就可以运行了,但是它还必须等待获取锁之后才能真正进行运行状态。

signal函数其实就做了一件事情,就是不断尝试调用transferForSignal函数,将condition wait queue队首的一个节点转移到sync queue队列中,直到转移成功。因为一次转移成功,就代表这个消息被成功通知到了等待消息的节点。

signal函数的示意图如下所示。

img

2.32 Stream(不是IOStream)有哪些方法?

参考答案

Stream提供了大量的方法进行聚集操作,这些方法既可以是“中间的”,也可以是“末端的”。

  • 中间方法:中间操作允许流保持打开状态,并允许直接调用后续方法。上面程序中的map()方法就是中间方法。中间方法的返回值是另外一个流。
  • 末端方法:末端方法是对流的最终操作。当对某个Stream执行末端方法后,该流将会被“消耗”且不再可用。上面程序中的sum()、count()、average()等方法都是末端方法。

除此之外,关于流的方法还有如下两个特征:

  • 有状态的方法:这种方法会给流增加一些新的属性,比如元素的唯一性、元素的最大数量、保证元素以排序的方式被处理等。有状态的方法往往需要更大的性能开销。
  • 短路方法:短路方法可以尽早结束对流的操作,不必检查所有的元素。

下面简单介绍一下Stream常用的中间方法:

  • filter(Predicate predicate):过滤Stream中所有不符合predicate的元素。
  • mapToXxx(ToXxxFunction mapper):使用ToXxxFunction对流中的元素执行一对一的转换,该方法返回的新流中包含了ToXxxFunction转换生成的所有元素。
  • peek(Consumer action):依次对每个元素执行一些操作,该方法返回的流与原有流包含相同的元素。该方法主要用于调试。
  • distinct():该方法用于排序流中所有重复的元素(判断元素重复的标准是使用equals()比较返回true)。这是一个有状态的方法。
  • sorted():该方法用于保证流中的元素在后续的访问中处于有序状态。这是一个有状态的方法。
  • limit(long maxSize):该方法用于保证对该流的后续访问中最大允许访问的元素个数。这是一个有状态的、短路方法。

下面简单介绍一下Stream常用的末端方法:

  • forEach(Consumer action):遍历流中所有元素,对每个元素执行action。
  • toArray():将流中所有元素转换为一个数组。
  • reduce():该方法有三个重载的版本,都用于通过某种操作来合并流中的元素。
  • min():返回流中所有元素的最小值。
  • max():返回流中所有元素的最大值。
  • count():返回流中所有元素的数量。
  • anyMatch(Predicate predicate):判断流中是否至少包含一个元素符合Predicate条件。
  • noneMatch(Predicate predicate):判断流中是否所有元素都不符合Predicate条件。
  • findFirst():返回流中的第一个元素。
  • findAny():返回流中的任意一个元素。

除此之外,Java 8允许使用流式API来操作集合,Collection接口提供了一个stream()默认方法,该方法可返回该集合对应的流,接下来即可通过流式API来操作集合元素。由于Stream可以对集合元素进行整体的聚集操作,因此Stream极大地丰富了集合的功能。

扩展阅读

Java 8新增了Stream、IntStream、LongStream、DoubleStream等流式API,这些API代表多个支持串行和并行聚集操作的元素。上面4个接口中,Stream是一个通用的流接口,而IntStream、LongStream、DoubleStream则代表元素类型为int、long、double的流。

Java 8还为上面每个流式API提供了对应的Builder,例如Stream.Builder、IntStream.Builder、LongStream.Builder、DoubleStream.Builder,开发者可以通过这些Builder来创建对应的流。

独立使用Stream的步骤如下:

  1. 使用Stream或XxxStream的builder()类方法创建该Stream对应的Builder。
  2. 重复调用Builder的add()方法向该流中添加多个元素。
  3. 调用Builder的build()方法获取对应的Stream。
  4. 调用Stream的聚集方法。

在上面4个步骤中,第4步可以根据具体需求来调用不同的方法,Stream提供了大量的聚集方法供用户调用,具体可参考Stream或XxxStream的API文档。对于大部分聚集方法而言,每个Stream只能执行一次。

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