王京 的个人博客

记录精彩的程序人生

  menu
44 文章
0 浏览
0 当前访客
ღゝ◡╹)ノ❤️
/    

Java 常见的面试题（java容器）

一、java 容器都有哪些？

数组, String, java.util 下的集合容器

数组： 长度限制：Integer.Integer.MAX_VALUE;

String： 长度限制：底层是char 数组，长度 Integer.MAX_VALUE 线程安全的

List集合 ：是有序的，可以按照插入顺序访问元素。

Set集合 ：通常是无序的，但LinkedHashSet和TreeSet具有一定的顺序性。

Map集合 ：中的键值对通常是无序的，但LinkedHashMap和TreeMap具有一定的顺序性。

我们可以将上述容器做个分类，这样更方便识别：

按照存放要求分类

无序：Set，不能重复；

有序：List，允许重复；

键-值：Map；

按照读写效率

Hash：两者都高；

Array：读快，改慢；

Linked：读慢，改快；

Tree：加入元素可排序使用；

我们在选择容器时，需要根据容器的特性进行选择数组去实现对象存放，java容器有一种保护机制，能够防止多个进程同时修改同一个容器的内容，如果在迭代遍历某个容器的时候，另外一个进程介入其中，并且插入、删除或者修改容器中某个对象，就会报错。

二、Collection 和 Collections 有什么区别？

  • **Collcetion ** 是一个集合接口，它提供了对集合对象进行基本操作的通用接口方法。实现该接口的类主要有List和Set，该接口的设计目标是为各种具体的集合提供最大化的统一操作方式。
  • **Collections ** 是针对集合类的一个包装类，它提供了一系列的静态方法以实现对各种集合的搜索、排序、线程安全化等操作，其中大多数方法都是用来处理线性表。 Collections类不能实例化，如同一个工具类，服务于Collection。若是在使用Collections类的方法时候，对应的collection的对象为null，则这些方法都会抛出 NullPointerException 。之前我们见到的包装类还有Arrays，它是为数组提供服务的。

三、List、Set、Map的特点及区别详解(Java基础)

结构特点

**List、Set 是存储单列的数据集合，都继承与Collection接口。

Map 是存储键值对这样的双列数据的集合，是个独立接口。

List 中存储的数据是有序的，可以是重复的。

Set 中存储的数据是无序的，且不允许重复。

Map 中存储的数据是无序的，他的键是不允许重复的，值是可以重复的。**

相关的实现类

  1. List的接口有三个实现类。
    1. ArrayList
      1. 优点： 底层数据结构是数组，查询快，增删慢。
      2. 缺点： 线程不安全（一般不考虑到线程的安全因素，用Arraylist效率比较高）
    2. LinkedList
      1. 优点： 底层数据结构是链表，增删快，查询慢。
      2. 缺点： 线程不安全。
    3. Vector
      1. 优点： 底层数据结构是数组，查询快，增删慢。线程安全。
      2. 缺点： 效率低。
  2. Set接口有三个实现类
    1. HashSet 为快速查找而设计的Set,依赖hashCode()和equals()方法保证元素的唯一性。如果没有其他限制，这就是我们的默认选择，因为他对速度进行了优化。
    2. TreeSet 保证元素处于排序状态，底层为树结构，元素必须实现Comparable接口。
    3. LinkedHashSet 具有HsahSet的查询速度，内部使用链表维护元素的顺序（插入的次序）在使用迭代器遍历Set时，结果会按元素插入的次序显示。元素也必须定义hashCode（）方法。
  3. Map接口有6个实现类。
    1. HashMap Map基于散列表的实现(取代了Hashtable)。插入和查询"键值对"的开销是固定的。可以通过构造器设置容量和负载因子，以调整容器性能。
    2. LinkedHashMap 类似于HashMap，但是迭代遍历他时，取得的"键值对"的顺序是其插入次序，或是最近最少使用的（LRU）的次序。只比HashMap慢一点；而在迭代访问时反而更快，因为他使用链表维护内部次序。
    3. TreeMap 是SortedMap现阶段的唯一实现。基于红黑树实现。查看"键"或者"键值对"时，他们会被排序（次序由Comparable或Comparator j决定）。TreeMap的特点在于，所得到的结果是经过排序的。
    4. WeakHashMap 弱键（weak key）映射，允许释放映射所指的对象；这是为解决某类特殊问题而设计的。如果映射之外没有引用指向某个"键"，则此"键"可以被垃圾回收器回收。
    5. ConcurrentHashMap 一种线程安全的Map。
    6. IdentityHashMap 使用"=="代替"equals()"对键进行比较的散列映射，专门解决特殊问题而设计出的。

四、List、Set、Map 之间的区别是什么？

比较ListSetMap
继承接口CollectionCollection
常见实现类AbstractList(其常用子类有ArrayList、LinkedList、Vector)AbstractSet(其常用子类有HashSet、LinkedHashSet、TreeSet)HashMap、HashTable
常见方法add( )、remove( )、clear( )、get( )、contains( )、size( )add( )、remove( )、clear( )、contains( )、size( )put( )、get( )、remove( )、clear( )、containsKey( )、containsValue( )、keySet( )、values( )、size( )
元素可重复不可重复(用equals()判断)KEY不可重复
顺序顺序有序无序(实际上由HashCode决定)
线程安全Vector线程安全 Hashtable线程安全

五、HashMap、Hashtable、ConcurrentHashMap的原理与区别

HashTable

  • 底层数组+链表实现，无论key还是value都不能为null ，线程安全 ，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低，ConcurrentHashMap做了相关优化
  • 初始size为11 ，扩容：newsize = olesize*2+1
  • 计算index的方法：index = (hash & 0x7FFFFFFF) % tab.length

HashMap

  • 底层数组+链表实现，可以存储null键和null值 ，线程不安全
  • 初始size为16 ，扩容：newsize = oldsize*2，size一定为2的n次幂
  • 扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
  • 插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）
  • 当Map中元素总数超过Entry数组的75%，触发扩容操作，为了减少链表长度，元素分配更均匀
  • 计算index方法：index = hash & (tab.length – 1)

HashMap的初始值还要考虑加载因子:

  • 哈希冲突 ：若干Key的哈希值按数组大小取模后，如果落在同一个数组下标上，将组成一条Entry链，对Key的查找需要遍历Entry链上的每个元素执行equals()比较。
  • 加载因子 ：为了降低哈希冲突的概率，默认当HashMap中的键值对达到数组大小的75%时，即会触发扩容。因此，如果预估容量是100，即需要设定100/0.75＝134的数组大小。
  • 空间换时间 ：如果希望加快Key查找的时间，还可以进一步降低加载因子，加大初始大小，以降低哈希冲突的概率。

HashMap和Hashtable都是用hash算法来决定其元素的存储，因此HashMap和Hashtable的hash表包含如下属性：

  • 容量（capacity）：hash表中桶的数量
  • 初始化容量（initial capacity）：创建hash表时桶的数量，HashMap允许在构造器中指定初始化容量
  • 尺寸（size）：当前hash表中记录的数量
  • 负载因子（load factor）：负载因子等于“size/capacity”。负载因子为0，表示空的hash表，0.5表示半满的散列表，依此类推。轻负载的散列表具有冲突少、适宜插入与查询的特点（但是使用Iterator迭代元素时比较慢）

除此之外，hash表里还有一个“负载极限”，“负载极限”是一个0～1的数值，“负载极限”决定了hash表的最大填满程度。当hash表中的负载因子达到指定的“负载极限”时，hash表会自动成倍地增加容量（桶的数量），并将原有的对象重新分配，放入新的桶内，这称为rehashing。

HashMap和Hashtable的构造器允许指定一个负载极限，HashMap和Hashtable默认的“负载极限”为0.75，这表明当该hash表的3/4已经被填满时，hash表会发生rehashing。

“负载极限”的默认值（0.75）是时间和空间成本上的一种折中：

  • 较高的“负载极限”可以降低hash表所占用的内存空间，但会增加查询数据的时间开销，而查询是最频繁的操作（HashMap的get()与put()方法都要用到查询）
  • 较低的“负载极限”会提高查询数据的性能，但会增加hash表所占用的内存开销

程序猿可以根据实际情况来调整“负载极限”值。

ConcurrentHashMap

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

Hashtable和HashMap都实现了Map接口，但是Hashtable的实现是基于Dictionary抽象类的。Java5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。

HashMap基于哈希思想，实现对数据的读写。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，然后找到bucket位置来存储值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞时，对象将会储存在链表的下一个节点中。HashMap在每个链表节点中储存键值对对象。当两个不同的键对象的hashcode相同时，它们会储存在同一个bucket位置的链表中，可通过键对象的equals()方法来找到键值对。如果链表大小超过阈值（TREEIFY_THRESHOLD,8），链表就会被改造为树形结构。

在HashMap中，null可以作为键，这样的键只有一个，但可以有一个或多个键所对应的值为null。当get()方法返回null值时，即可以表示HashMap中没有该key，也可以表示该key所对应的value为null 。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个key，应该用containsKey() 方法来判断。而在Hashtable中，无论是key还是value都不能为null。

Hashtable是线程安全的，它的方法是同步的，可以直接用在多线程环境中。而HashMap则不是线程安全的，在多线程环境中，需要手动实现同步机制。

Hashtable与HashMap另一个区别是HashMap的迭代器（Iterator）是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。

先看一下简单的类图：

****编辑

从类图中可以看出来在存储结构中ConcurrentHashMap比HashMap多出了一个类Segment，而Segment是一个可重入锁。

ConcurrentHashMap是使用了锁分段技术来保证线程安全的。

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

ConcurrentHashMap提供了与Hashtable和SynchronizedMap不同的锁机制。Hashtable中采用的锁机制是一次锁住整个hash表，从而在同一时刻只能由一个线程对其进行操作；而ConcurrentHashMap中则是一次锁住一个桶。

ConcurrentHashMap默认将hash表分为16个桶，诸如get、put、remove等常用操作只锁住当前需要用到的桶。这样，原来只能一个线程进入，现在却能同时有16个写线程执行，并发性能的提升是显而易见的。

六、如何决定使用 HashMap 还是 TreeMap？

<strong>TreeMap<K,V></strong> 的Key值是要求实现java.lang.Comparable，所以迭代的时候TreeMap默认是按照Key值升序排序的；TreeMap的实现是基于红黑树结构。适用于按自然顺序或自定义顺序遍历键（key）。

<strong>HashMap<K,V></strong> 的Key值实现散列hashCode()，分布是散列的、均匀的，不支持排序；数据结构主要是桶(数组)，链表或红黑树。适用于在Map中插入、删除和定位元素。

如果你需要得到一个有序的结果时就应该使用TreeMap（因为HashMap中元素的排列顺序是不固定的）。除此之外，由于HashMap有更好的性能，所以大多不需要排序的时候我们会使用HashMap。

七、说一下 HashMap 的实现原理？

HashMap的特点

HashMap底层是一个哈希表，以数组加链表的形式存储值。HashMap具有以下特点：

  1. HashMap允许key和value为空
  2. HashMap是线程不安全的
  3. HashMap的初始容量为16，负载因子大小为0.75
  4. 在jdk7.0中，底层是数组加链表；在jdk8.0中，底层是数组加链表加红黑树

HasnMap的put操作

HashMap中维护了Node类型的数组table，当HashMap创建对象时，设置负载因子为0.75，table还是null。当第一次添加元素时，将table的容量设置为16，临界值设置为12

每次添加元素调用putVal方法：

  1. 将key的hash值和table容量-1进行与运算，得到索引值
  2. 判断该存放位置上是否有元素，如若没有元素则直接放上去；如果该索引位置已存在元素，则继续判断
  3. 如果该位置的元素和添加元素相等，则直接覆盖，如果不相等，则继续判断是链表结构还是树状结构，按照相对应的方式添加。如果添加的数量大于临界值，执行resize方法对容量双倍扩容。并打乱顺序重新排列。

八、说一下 HashSet 的实现原理？

HashSet 是基于HashMap 实现的,HashSet 底层使用HashMap来保存所有元素,因此HashSet的实现比较简单, 相关HashSet 的操作, 基本上都是直接调用底层HashMap的相关方法来完成, HashSet不允许重复的值。

九、ArrayList 和 LinkedList 的区别是什么？

  • 数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。
  • 随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。
  • 增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标。
  • 综合来说：在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。

十、如何实现数组和 List 之间的转换？

数组转 List ：

public static void testArray2List() {
	String[] strs = new String[] {"aaa", "bbb", "ccc"};
	List<String> list = Arrays.asList(strs);
	for (String s : list) {
		System.out.println(s);
	}
}

List 转数组：

public static void testList2Array() {
	List<String> list = Arrays.asList("aaa", "bbb", "ccc");
	String[] array = list.toArray(new String[list.size()]);
	for (String s : array) {
		System.out.println(s);
	}
}

十一、ArrayList 和 Vector 的区别是什么？

主要区别：

  • 同步性：Vector是线程安全的，用synchronized实现线程安全，而ArrayList是线程不安全的。（实现同步需要很高的花费，所以访问Vector比访问ArrayList慢）
  • 数据容量增长：二者都有一个初始容量大小，采用线性连续存储空间，当存储的元素的个数超过了容量时，就需要增加二者的存储空间，Vector增长原来的一倍，ArrayList增加原来的0.5倍。

总结：

  • LinkedList：增删改快
  • ArrayList：查询快（有索引的存在）
  • 如果只有一个线程会访问到集合，那最好使用ArrayList，因为它不考虑线程安全，效率会高些；如果有多个线程会访问到集合，那最好是使用Vector，因为不需要我们再去考虑和编写线程安全的代码。

拓展：

  • LinkedList和ArrayList都是通过数组实现。缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要将已经有数组的数据复制到新的存储空间中。
  • LinkedList是用链表结构存储数据的，很适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，他还提供了List接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。

十二、Array 和 ArrayList 有何区别？

  • Array可以包含基本类型和对象类型，ArrayList只能包含对象类型。
  • Array大小是固定的，ArrayList的大小是动态变化的。
  • ArrayList提供了更多的方法和特性，比如：addAll()，removeAll()，iterator()等等。
  • 对于基本类型数据，ArrayList 使用自动装箱来减少编码工作量；而当处理固定大小的基本数据类型的时候，这种方式相对比较慢，这时候应该使用Array。

十三、在 Queue 中 poll()和 remove()有什么区别？

队列是一个典型的先进先出（FIFO）的容器。即从容器的一端放入事物，从另一端取出，并且事物放入容器的顺序与取出的顺序是相同的。

队列的两种实现方式：

  1. offer()和add()的区别： add()和offer()都是向队列中添加一个元素。但是如果想在一个满的队列中加入一个新元素，调用 add() 方法就会抛出一个 unchecked 异常，而调用 offer() 方法会返回 false。可以据此在程序中进行有效的判断！
  2. peek()和element()的区别： peek()和element()都将在不移除的情况下返回队头，但是peek()方法在队列为空时返回null，调用element()方法会抛出NoSuchElementException异常。
  3. poll()和remove()的区别： poll()和remove()都将移除并且返回对头，但是在poll()在队列为空时返回null，而remove()会抛出NoSuchElementException异常。

十四、哪些集合类是线程安全的？

  • Vector： 就比Arraylist多了个同步化机制（线程安全）。
  • Hashtable： 就比Hashmap多了个线程安全。
  • ConcurrentHashMap： 是一种高效但是线程安全的集合。
  • Stack： 栈，也是线程安全的，继承于Vector。

十五、迭代器 Iterator 是什么？

首先说一下迭代器模式，它是 Java 中常用的设计模式之一。用于顺序访问集合对象的元素，无需知道集合对象的底层实现。

Iterator 是可以遍历集合的对象，为各种容器提供了公共的操作接口，隔离对容器的遍历操作和底层实现，从而解耦。

缺点是增加新的集合类需要对应增加新的迭代器类，迭代器类与集合类成对增加。

十六、Iterator 怎么使用？有什么特点？

  • java.lang.Iterable 接口被 java.util.Collection 接口继承，java.util.Collection 接口的 iterator() 方法返回一个 Iterator 对象
  • next() 方法获得集合中的下一个元素
  • hasNext() 检查集合中是否还有元素
  • remove() 方法将迭代器新返回的元素删除
  • forEachRemaining(Consumer<? super E> action) 方法，遍历所有元素
public class TestIterator {

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

	static {
		list.add("111");
		list.add("222");
		list.add("333");
	}

 
	public static void main(String[] args) {
		testIteratorNext();
		System.out.println();
	
		testForEachRemaining();
		System.out.println();
	
		testIteratorRemove();
	}

	//使用 hasNext 和 next遍历 
	public static void testIteratorNext() {
		Iterator<String> iterator = list.iterator();
		while (iterator.hasNext()) {
			String str = iterator.next();
			System.out.println(str);
		}
	}

	//使用 Iterator 删除元素 
	public static void testIteratorRemove() {
		Iterator<String> iterator = list.iterator();
		while (iterator.hasNext()) {
			String str = iterator.next();
			if ("222".equals(str)) {
				iterator.remove();
			}
		}
		System.out.println(list);
	}

	//使用 forEachRemaining 遍历
	public static void testForEachRemaining() {
		final Iterator<String> iterator = list.iterator();
		iterator.forEachRemaining(new Consumer<String>() {
 
			public void accept(String t) {
				System.out.println(t);
			}
		
		});
	}
}

十七、Iterator 和 ListIterator 有什么区别？

  • ListIterator 继承 Iterator
  • ListIterator 比 Iterator多方法
    • add(E e) 将指定的元素插入列表，插入位置为迭代器当前位置之前
    • set(E e) 迭代器返回的最后一个元素替换参数e
    • hasPrevious() 迭代器当前位置，反向遍历集合是否含有元素
    • previous() 迭代器当前位置，反向遍历集合，下一个元素
    • previousIndex() 迭代器当前位置，反向遍历集合，返回下一个元素的下标
    • nextIndex() 迭代器当前位置，返回下一个元素的下标
  • 使用范围不同，Iterator可以迭代所有集合；ListIterator 只能用于List及其子类
  • ListIterator 有 add 方法，可以向 List 中添加对象；Iterator 不能
  • ListIterator 有 hasPrevious() 和 previous() 方法，可以实现逆向遍历；Iterator不可以
  • ListIterator 有 nextIndex() 和previousIndex() 方法，可定位当前索引的位置；Iterator不可以
  • ListIterator 有 set()方法，可以实现对 List 的修改；Iterator 仅能遍历，不能修改

十八、怎么确保一个集合不能被修改？

  • 通过 Collections. unmodifiableCollection(Collection c)
    • Collections.unmodifiableMap
    • Collections.unmodifiableList(List)
    • Collections.unmodifiableSet(Set)
  • 通过Arrays.asList创建的集合

注：以上内容仅提供参考和交流，请勿用于商业用途，如有侵权联系本人删除！

注：此博客只是为了记忆相关知识点，大部分为网络上的文章，在此向各个文章的作者表示感谢！

标题：Java 常见的面试题（java容器）
作者：wangjing
地址：https://www.codedblogs.cn/articles/2024/04/12/1712888811246.html