Java常用集合List、Map、Set介绍以及一些面试问题

2022-08-09 10:38:46 浏览数 (1)

目录

  • 集合框架图
  • 常用接口介绍以及区别
  • 常用接口类介绍
    • ArrayList
    • LinkedList
    • HashMap
    • ConcurrentHashMap
    • TreeMap
    • LinkedHashMap
    • HashSet
    • TreeSet
  • 其他问题

集合框架图

集合和数组的区别：

  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中，在多线程环境下，会发生数据覆盖的情况。

如果没有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是一个接口。

hashmap http java 编程算法 存储

0 人点赞