请说说你对Java集合的了解

Java中的集合类分为4大类,分别由4个接口来代表,它们是Set、List、Queue、Map。其中,Set、List、Queue、都继承自Collection接口。

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

Java提供了众多集合的实现类,它们都是这些接口的直接或间接的实现类,其中比较常用的有：HashSet、TreeSet、ArrayList、LinkedList、HashMap、TreeMap等。
上面所说的集合类的接口或实现,都位于java.util包下,这些实现大多数都是非线程安全的。虽然非线程安全,但是这些类的性能较好。如果需要使用线程安全的集合类,则可以利用Collections工具类,该工具类提供的synchronizedXxx()方法,可以将这些集合类包装成线程安全的集合类。
java.util包下的集合类中,也有少数的线程安全的集合类,例如Vector、Hashtable,它们都是非常古老的API。虽然它们是线程安全的,但是性能很差,已经不推荐使用了。 从JDK 1.5开始,并发包下新增了大量高效的并发的容器,这些容器按照实现机制可以分为三类。

  • 第一类是以降低锁粒度来提高并发性能的容器,它们的类名以Concurrent开头,如ConcurrentHashMap。
  • 第二类是采用写时复制技术实现的并发容器,它们的类名以CopyOnWrite开头,如CopyOnWriteArrayList。

  • 第三类是采用Lock实现的阻塞队列,内部创建两个Condition分别用于生产者和消费者的等待,这些类都实现了BlockingQueue接口,如ArrayBlockingQueue。

    你知道哪些线程安全的集合？

    java.util包下的集合类中,大部分都是非线程安全的,但也有少数的线程安全的集合类,例如Vector、Hashtable,它们都是非常古老的API。虽然它们是线程安全的,但是性能很差,已经不推荐使用了。
    对于这个包下非线程安全的集合,可以利用Collections工具类,该工具类提供的synchronizedXxx()方法,可以将这些集合类包装成线程安全的集合类。
    从JDK 1.5开始,并发包下新增了大量高效的并发的容器,这些容器按照实现机制可以分为三类。

  • 第一类是以降低锁粒度来提高并发性能的容器,它们的类名以Concurrent开头,如ConcurrentHashMap。

  • 第二类是采用写时复制技术实现的并发容器,它们的类名以CopyOnWrite开头,如CopyOnWriteArrayList。
  • 第三类是采用Lock实现的阻塞队列,内部创建两个Condition分别用于生产者和消费者的等待,这些类都实现了BlockingQueue接口,如ArrayBlockingQueue。

Collections还提供了如下三类方法来返回一个不可变的集合,这三类方法的参数是原有的集合对象,返回值是该集合的“只读”版本。通过Collections提供的三类方法,可以生成“只读”的Collection或Map。

  • emptyXxx()：返回一个空的不可变的集合对象
  • singletonXxx()：返回一个只包含指定对象的不可变的集合对象
  • unmodifiableXxx()：返回指定集合对象的不可变视图

    请你说说HashMap底层原理

    在JDK8中,HashMap底层是采用“数组+链表+红黑树”来实现的。
    HashMap是基于哈希算法来确定元素的位置（槽）的,当我们向集合中存入数据时,它会计算传入的Key的哈希值,并利用哈希值取余来确定槽的位置。如果元素发生碰撞,也就是这个槽已经存在其他的元素了,则HashMap会通过链表将这些元素组织起来。如果碰撞进一步加剧,某个链表的长度达到了8,则HashMap会创建红黑树来代替这个链表,从而提高对这个槽中数据的查找的速度。
    HashMap中,数组的默认初始容量为16,这个容量会以2的指数进行扩容。具体来说,当数组中的元素达到一定比例的时候HashMap就会扩容,这个比例叫做负载因子,默认为0.75。
    自动扩容机制,是为了保证HashMap初始时不必占据太大的内存,而在使用期间又可以实时保证有足够大的空间。采用2的指数进行扩容,是为了利用位运算,提高扩容运算的效率。
    put()流程
    put()方法的执行过程中,主要包含四个步骤：
  1. 判断数组,若发现数组为空,则进行首次扩容。
  2. 判断头节点,若发现头节点为空,则新建链表节点,存入数组。
  3. 判断头节点,若发现头节点非空,则将元素插入槽内。
  4. 插入元素后,判断元素的个数,若发现超过阈值则再次扩容。

其中,第3步又可以细分为如下三个小步骤：

  1. 若元素的key与头节点一致,则直接覆盖头节点。
  2. 若元素为树型节点,则将元素追加到树中。
  3. 若元素为链表节点,则将元素追加到链表中。追加后,需要判断链表长度以决定是否转为红黑树。若链表长度达到8、数组容量未达到64,则扩容。若链表长度达到8、数组容量达到64,则转为红黑树。

扩容机制 向HashMap中添加数据时,有三个条件会触发它的扩容行为：

  1. 如果数组为空,则进行首次扩容。
  2. 将元素接入链表后,如果链表长度达到8,并且数组长度小于64,则扩容。
  3. 添加后,如果数组中元素超过阈值,即比例超出限制（默认为0.75）,则扩容。 并且,每次扩容时都是将容量翻倍,即创建一个2倍大的新数组,然后再将旧数组中的数组迁移到新数组里。由于HashMap中数组的容量为2^N,所以可以用位移运算计算新容量,效率很高。

HashMap是非线程安全的,在多线程环境下,多个线程同时触发HashMap的改变时,有可能会发生冲突。所以,在多线程环境下不建议使用HashMap,可以考虑使用Collections将HashMap转为线程安全的HashMap,更为推荐的方式则是使用ConcurrentHashMap。

请你说说HashMap和Hashtable的区别

HashMap和Hashtable都是典型的Map实现,它们的区别在于是否线程安全,是否可以存入null值。
1. Hashtable在实现Map接口时保证了线程安全性,而HashMap则是非线程安全的。所以,Hashtable的性能不如HashMap,因为为了保证线程安全它牺牲了一些性能。
2. Hashtable不允许存入null,无论是以null作为key或value,都会引发异常。而HashMap是允许存入null的,无论是以null作为key或value,都是可以的。
虽然Hashtable是线程安全的,但仍然不建议在多线程环境下使用Hashtable。因为它是一个古老的API,从Java 1.0开始就出现了,它的同步方案还不成熟,性能不好。如果要在多线程环下使用HashMap,建议使用ConcurrentHashMap。它不但保证了线程安全,也通过降低锁的粒度提高了并发访问时的性能。

HashMap是线程安全的吗？如果不是该如何解决？

HashMap是非线程安全的,在多线程环境下,多个线程同时触发HashMap的改变时,有可能会发生冲突。所以,在多线程环境下不建议使用HashMap。
想要使用线程安全的HashMap,一共有三种办法：使用Hashtable、使用Collections将HashMap包装成线程安全的HashMap、使用ConcurrentHashMap,其中第三种方式最为高效,是我们最推荐的方式。

  • Hashtable

HashMap和Hashtable都是典型的Map实现,而Hashtable是线程安全的。虽然这算是一个可选方案,但却是不推荐的方案。因为Hashtable是一个古老的API,从Java 1.0开始就出现了,它的同步方案还不成熟、性能不好,甚至官方都给出了不推荐使用的建议。

  • Collections

Collections类中提供了synchronizedMap()方法,可以将我们传入的Map包装成线程同步的Map。除此以外,Collections还提供了如下三类方法来返回一个不可变的集合,这三类方法的参数是原有的集合对象,返回值是该集合的“只读”版本。通过Collections提供的三类方法,可以生成“只读”Map。

  • emptyMap()：返回一个空的不可变的Map对象。
  • singletonMap()：返回一个只包含指定键值对的不可变的Map对象。
  • unmodifiableMap() ：返回指定Map对象的不可变视图。
    • ConcurrentHashMap

ConcurrentHashMap是线程安全且高效的HashMap,并且在JDK 8中进行了升级,使其在JDK 7的基础上进一步降低了锁的粒度,从而提高了并发的能力。 在JDK 7中ConcurrentHashMap的底层数据结构为“数组+链表”,但是为了降低锁的粒度,JDK7将一个Map拆分为若干子Map,每一个子Map称为一个段。多个段之间是相互独立的,而每个段都包含若干个槽,段中数据发生碰撞时采用链表结构解决。在并发插入数据时,ConcurrentHashMap锁定的是段,而不是整个Map。因为锁的粒度是段,所以这种模式也叫“分段锁”。
另外,段在容器初始化的时候就被确定下来了,之后不能更改。而每个段是可以独立扩容的,各个段之间互不影响,所以并不存在并发扩容的问题。 在JDK8中ConcurrentHashMap的底层数据结构为“数组+链表+红黑树”,但是为了进一步降低锁的粒度,JDK8取消了段的设定,而是直接在Map的槽内存储链表或红黑树。并发插入时它锁定的是头节点,相比于段头节点的个数是可以随着扩容而增加的,所以粒度更小。引入红黑树,则是为了在冲突剧烈时,提高查找槽内元素的效率。

说说你对ArrayList的理解

ArrayList是基于数组实现的,它的内部封装了一个Object[]数组。 通过默认构造器创建容器时,该数组先被初始化为空数组,之后在首次添加数据时再将其初始化成长度为10的数组。
我们也可以使用有参构造器来创建容器,并通过参数来显式指定数组的容量,届时该数组被初始化为指定容量的数组。
如果向ArrayList中添加数据会造成超出数组长度限制,则会触发自动扩容,然后再添加数据。扩容就是数组拷贝,将旧数组中的数据拷贝到新数组里,而新数组的长度为原来长度的1.5倍。
ArrayList支持缩容,但不会自动缩容,即便是ArrayList中只剩下少量数据时也不会主动缩容。
如果我们希望缩减ArrayList的容量,则需要自己调用它的trimToSize()方法,届时数组将按照元素的实际个数进行缩减。
Set、List、Queue都是Collection的子接口,它们都继承了父接口的iterator()方法,从而具备了迭代的能力。但是,相比于另外两个接口,List还单独提供了listIterator()方法,增强了迭代能力。iterator()方法返回Iterator迭代器,listIterator()方法返回ListIterator迭代器,并且ListIterator是Iterator的子接口。ListIterator在Iterator的基础上,增加了向前遍历的支持,增加了在迭代过程中修改数据的支持。

请你说说ArrayList和LinkedList的区别

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

    请你说说List与Set的区别

    List和Set都是Collection接口的子接口,它们的主要区别在于元素的有序性和重复性：
  • List代表有序的元素可以重复的集合,集合中每个元素都有对应的顺序索引,它默认按元素的添加顺序设置元素的索引,并且可以通过索引来访问指定位置的集合元素。另外,List允许使用重复元素。 Set代表无序的元素不可重复的集合,它通常不能记住元素的添加顺序。
  • Set集合不允许包含相同的元素,如果试图把两个相同的元素加入同一个Set,则会引发失败,添加方法将会返回false。

虽然Set代表无序的集合,但是它有支持排序的实现类,即TreeSet。TreeSet可以确保集合元素处于排序状态,并支持自然排序和定制排序两种排序方式,它的底层是由TreeMap实现的。TreeSet也是非线程安全的,但是它内部元素的值不能为null。