Java常用集合List、Map、Set介绍以及一些面试问题 - Java技术债务


集合框架图

Java常用集合List、Map、Set介绍以及一些面试问题 - Java技术债务 集合和数组的区别

  1. 数组是固定长度的;集合可变长度的。
  2. 数组可以存储基本数据类型,也可以存储引用数据类型;集合只能存储引用数据类型。
  3. 数组存储的元素必须是同一个数据类型;集合存储的对象可以是不同数据类型。

常用接口介绍以及区别

  1. List(有序、可重复) List里存放的对象是有序的,同时也是可以重复的,List关注的是索引,拥有一系列和索引相关的方法,查询速度快。因为往list集合里插入或删除数据时,会伴随着后面数据的移动,所有插入删除数据速度慢。
  2. Set(无序、不能重复) Set里存放的对象是无序,不能重复的,集合中的对象不按特定的方式排序,只是简单地把对象加入集合中。
  3. Map(键值对、键唯一、值不唯一) Map集合中存储的是键值对,键不能重复,值可以重复。根据键得到值,对map集合遍历时先得到键的set集合,对set集合进行遍历,得到相应的值。
  4. 一些其它的接口有Queue、Dequeue、SortedSet、SortedMap和ListIterator。

常用接口类介绍

ArrayList

List接口实现类。ArrayList底层是由数组实现的,随机访问速度极快。

  1. Array可以包含基本数据类型和对象类型,ArrayList只能包含对象类型;
  2. Array的大小是固定的,ArrayList大小是动态改变的;
  3. ArrayList提供了许多方法,比如addAll(),removeAll(),iterator()等;

对于基本数据类型,集合使用自动装箱减少代码量,但是如果处理固定大小的基本数据类型时,相对比较慢。

ArrayList扩容机制,使用copyOf浅拷贝进行创建一个新的数组。

优点:数组长度可动态改变

缺点:不适合在中间频繁进行插入和删除操作。因为每次插入和删除都需要移动数组中的元素。

  1. ArrayList没有指定初始化长度时,默认长度为10
  2. ArrayList在增加元素的时候超过了原始容量,会采用扩容ensureCapacity方案:原始容量*3/2+1(1.5倍扩容)
  3. ArrayList是线程不安全的,在多线程的情况下不要使用。
  4. Vector是线程安全的,被同步关键字修饰。扩容方案是:原来的2倍。
  5. Vector是ArrayList的多线程的一个替代品

注意: ArrayList会在并发时出现数组越界

问题:ArrayList 内部用什么实现的? ArrayList 内部是用 Object[]实现的。是线性表(数组) 分析 ArrayList 的构造、add、remove、clear 方法的实现原理得:

  • get() 直接读取第几个下标,复杂度 O(1)
  • add(E) 添加元素,直接在后面添加,复杂度O(1)
  • add(index, E) 添加元素,在第几个元素后面插入,后面的元素需要向后移动,复杂度O(n)
  • remove()删除元素,后面的元素需要逐个移动,复杂度O(n)

LinkedList

双向循环链表的链式表,存储结构使用链式表 LinkedList 是链表的操作

  • get() 获取第几个元素,依次遍历,复杂度O(n)
  • add(E) 添加到末尾,复杂度O(1)
  • add(index, E) 添加第几个元素后,需要先查找到第几个元素,直接指针指向操作,复杂度O(n)
  • remove()删除元素,直接指针指向操作,复杂度O(1)

特点:适合于在链表中间需要频繁的插入和删除操作。

缺点:随机访问速度较慢,查找一个元素需要从头开始一个一个的找。也不是线程安全的

问题:LinkedList和ArrayList、vector的区别

  • LinkedList比ArrayList更占内存,因为LinkedList为每一个节点存储了两个引用,一个指向前一个元素,一个指向下一个元素。
  • ArrayList 底层结构是数组,底层查询快,增删慢。
  • LinkedList 底层结构是链表型的,增删快,查询慢。
  • vector 底层结构是数组 线程安全的,增删慢,查询慢。

HashMap

HashMap可以接受null键值和值,而Hashtable则不能;HashMap是非synchronized;HashMap很快;以及HashMap储存的是键值对

HashMap的工作原理

基于hasing的原理,使用put(key,value)存储对象,使用get(key)获取对象,调用put()方法传递键和值的时候,先对键使用hashCode()方法计算hashCode,返回的hashCode用于找到bucket位置来储存Entry对象。当get()获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。

重要特性为容量、负载因子、扩容极限。

问题:HashMap是线程不安全的,其主要体现:

在jdk1.7中,在多线程环境下,扩容时会造成环形链或数据丢失。 在jdk1.8中,在多线程环境下,会发生数据覆盖的情况。 Java常用集合List、Map、Set介绍以及一些面试问题 - Java技术债务 如果没有hash碰撞则会直接插入元素。如果线程A和线程B同时进行put操作,刚好这两条不同的数据hash值一样,并且该位置数据为null,所以这线程A、B都会进入

线程A进入后还未进行数据插入时挂起,而线程B正常执行,从而正常插入数据,然后线程A获取CPU时间片,此时线程A不用再进行hash判断了,问题出现:线程A会把线程B插入的数据给覆盖,发生线程不安全。

问题:如果两个对象hashCode相同会发生什么?

hashCode相同,bucket位置相同,发生碰撞。HashMap使用链表存储对象,Entry会存储在链表中。

问题:如果两个键的hashCode相同怎么获取值对象?

调用get()方法时,获取hashCode方法找到bucket的位置,然后调用equals()方法找到链表中正确的节点。

问题:如果HashMap大小超过负载因子定义的容量怎么办?

会进行rehasing。

默认负载因子为0.75也就是说当一个map填满了75%的bucket的时候,将大小扩大原来的两倍,重新调整map的大小,将原来的对象放入新的bucket上。

问题:重新调整HashMap大小存在什么问题

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

ConcurrentHashMap

详情请看之前文章ConcurrentHashMap的原理分析 或者关注公众号查看详情

TreeMap

实现SortMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator 遍历TreeMap时,得到的记录是排过序的。

LinkedHashMap

是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的.也可以在构造时用带参数,按照应用次数排序。在遍历的时候会比HashMap慢,不过有种情况例外,当HashMap容量很大,实际数据较少时,遍历起来可能会比 LinkedHashMap慢,因为LinkedHashMap的遍历速度只和实际数据有关,和容量无关,而HashMap的遍历速度和他的容量有关。

HashMap、HashTable、ConcurrentHashMap、TreeMap的区别 HashMap

1、底层数组+链表实现

2、key与value可以为null

3、线程不安全

4、初始size为16,扩容方式:newSize = oldSize * 2 ;size是2的n次幂

Hashtable

1、底层数组+链表实现

2、key与value 不能为null

3、线程安全:实现线程安全的方式是修改数据时锁住整个HashTable,因此也导致了 Hashtable在写入时会比较慢。

4、初始size为11,扩容方式:newSize = oldSize * 2 + 1

5、扩容针对整个Map,每次扩容时,原来数组中的元素依次重新计算存放位置,并重新插入

6、插入元素后判断是否扩容,如果扩容后没有插入新的元素,判定为无效扩容

7、当Map中元素总数超过Entry数组的75%,触发扩容操作,为了减少链表长度,元素分配更均匀

TreeMap

TreeMap实现SortMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序(自然顺序),也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。不允许key值为空,非同步的;

ConcurrentHashMap(jdk1.7)

  • 底层采用分段的数组+链表实现,线程**安全.**使用了锁分段技术来保证线程安全的
  • 通过把整个Map分为N个Segment,可以提供相同的线程安全,但是效率提升N倍,默认提升16倍。(读操作不加锁,由于HashEntry的value变量是 volatile的,也能保证读取到最新的值。)
  • Hashtable的synchronized是针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术
  • 有些方法需要跨段,比如size()和containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁
  • 扩容:段内扩容(段内元素超过该段对应Entry数组长度的75%触发扩容,不会对整个Map进行扩容),插入前检测需不需要扩容,有效避免无效扩容

锁分段技术:首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。

ConcurrentHashMap 是线程安全的 HashMap 的实现

put 操作:并没有在此方法上加上 synchronized,首先对 key.hashcode 进行 hash 操作,得到 key 的 hash 值。 hash操作的算法和 map也不同,根据此 hash 值计算并获取其对应的数组中的 Segment对象(继承自ReentrantLock), 接着调用此 Segment 对象的 put 方法来完成当前操作。ConcurrentHashMap 基于 concurrencyLevel 划分出了多个 Segment 来对 key-value 进行存储,从而避免每 次 put 操作都得锁住整个数组。在默认的情况下,最佳情况下可允许 16 个线程并发无阻塞的操作集合对象,

get(key)首先对 key.hashCode 进行 hash 操作,基于其值找到对应的 Segment 对象,调用其 get 方法完成当前操 作。而 Segment 的 get 操作首先通过 hash 值和对象数组大小减 1 的值进行按位与操作来获取数组上对应位置的 HashEntry。

HashSet

HashSet:底层数据结构是哈希表。

特点

  • 不能保证元素的排列顺序。
  • 非线程安全
  • 集合元素可以使null

哈希表的原理

  1. 对对象元素中的关键字(对象中的特有数据),进行哈希算法的运算,并得出一个具体的算法值,这个值 称为哈希值。
  2. 哈希值就是这个元素的位置。
  3. 如果哈希值出现冲突,再次判断这个关键字对应的对象是否相同。如果对象相同,就不存储,因为元素重复。如果对象不同,就存储,在原来对象的哈希值基础 +1顺延。
  4. 存储哈希值的结构,我们称为哈希表。
  5. 既然哈希表是根据哈希值存储的,为了提高效率,最好保证对象的关键字是唯一的。

这样可以尽量少的判断关键字对应的对象是否相同,提高了哈希表的操作效率。

问题:如何保证元素的唯一性:

通过hashCode和equals两个方法进行确定元素的唯一性,如果两个元素的hashCode值一样,调用equals方法进行判断值是否相等。如果hashCode值不一样,则不会调用equals方法。

hashCode() 方法

  • HashSet 集合判断两个元素相等的标准:两个对象通过 equals() 方法比较相等,并且两个对象的 hashCode () 方法返回值也相等。
  • 如果两个对象通过 equals() 方法返回 true ,这两个对象的 hashCode 值也应该相同。
  • 重写 hashCode () 方法的基本原则 1、 在程序运行时,同一个对象多次调用 hashCode () 方法应该返回相同的值 2、当两个对象的 equals() 方法比较返回 true 时,这两个对象的 hashCode () 方法的返回值也应相等 3、对象中用作 equals() 方法比较的 Field ,都应该用来计算 hashCode 值

TreeSet

对Set集合中的元素的进行指定顺序的排序,不同步。TreeSet底层的数据结构就是二叉树。

保证元素唯一性 根据compareTo的return返回值。后存入的元素调用compareTo方法并传入前面的元素进行比较,如果compareTo方法return返回正数就表示比前面元素大,就存到了二叉树的右边,取出时是后取出该元素的。如果return返回0,则两个元素一样,则不会存入。如果return返回负数表示比前面元素小,就存在二叉树的左边,取出时会先取出该元素。

排序方式

  • TreeSet排序的第一种方式:让元素自身具备比较性。元素需要实现Comparable接口,重写compareTo方法。这种方式也称为元素的自然顺序,也叫元素的默认顺序。
  • TreeSet集合第二种排序方式:当元素自身不具备比较性或者具备的比较性不是所需要的,这时需要让集合自身具备比较性。让集合一初始化就有了比较方式。定义比较器类,实现Comparator接口,重写compare()方法。

set集合转List集合

List< String> list= new ArrayList<>(HashSet);

其他问题

问题:fail-fast与fail-safe有什么区别?

Iterator的fail-fast属性与当前的集合共同起作用,因此它不会受到集合中任何改动的影响。Java.util包中的所有集合类都被设计为fail-fast的,而java.util.concurrent中的集合类都为fail-safe的。Fail-fast迭代器抛出ConcurrentModificationException,而fail-safe迭代器从不抛出ConcurrentModificationException。

问题:哪些集合类是线程安全的?

Vector、HashTable、Properties和Stack是同步类,所以它们是线程安全的,可以在多线程环境下使用。Java1.5并发API包括一些集合类,允许迭代时修改,因为它们都工作在集合的克隆上,所以它们在多线程环境中是安全的。

问题:并发集合类是什么?

Java1.5并发包(java.util.concurrent)包含线程安全集合类,允许在迭代时修改集合。迭代器被设计为fail-fast的,会抛出ConcurrentModificationException。一部分类为:CopyOnWriteArrayList、 ConcurrentHashMap、CopyOnWriteArraySet。

问题:队列和栈是什么,列出它们的区别?

栈和队列两者都被用来预存储数据。java.util.Queue是一个接口,它的实现类在Java并发包中。队列允许先进先出(FIFO)检索元素,但并非总是这样。Deque接口允许从两端检索元素。

栈与队列很相似,但它允许对元素进行后进先出(LIFO)进行检索。

Stack是一个扩展自Vector的类,而Queue是一个接口。

   登录后才可以发表评论呦...

专注分享Java技术干货,包括
但不仅限于多线程、JVM、Spring Boot
Spring Cloud、 Redis、微服务、
消息队列、Git、面试题 最新动态等。

想交个朋友吗
那就快扫下面吧


微信

Java技术债务

你还可以关注我的公众号

会分享一些干货或者好文章

Java技术债务