Java 集合框架常见面试题总结

本贴最后更新于 1971 天前,其中的信息可能已经时移世改

  1. List,Set,Map 三者的区别及总结
  2. Arraylist 与 LinkedList 区别
  3. ArrayList 与 Vector 区别(为什么要用 Arraylist 取代 Vector 呢?)
  4. HashMap 和 Hashtable 的区别
  5. HashSet 和 HashMap 区别
  6. HashMap 和 ConcurrentHashMap 的区别
  7. HashSet 如何检查重复
  8. comparable 和 comparator 的区别
    1. Comparator 定制排序
    2. 重写 compareTo 方法实现按年龄来排序
  9. 如何对 Object 的 list 排序?
  10. 如何实现数组与 List 的相互转换?
  11. 如何求 ArrayList 集合的交集 并集 差集 去重复并集
  12. HashMap 的工作原理及代码实现
  13. ConcurrentHashMap 的工作原理及代码实现
  14. 集合框架底层数据结构总结
    1. - Collection
      1. 1. List
      2. 2. Set
    2. - Map
  15. 集合的选用
  16. 集合的常用方法

List,Set,Map 三者的区别及总结

  • List:对付顺序的好帮手

    List 接口存储一组不唯一(可以有多个元素引用相同的对象),有序的对象

  • Set:注重独一无二的性质

    不允许重复的集合。不会有多个元素引用相同的对象。

  • Map:用 Key 来搜索的专家

    使用键值对存储。Map 会维护与 Key 有关联的值。两个 Key 可以引用相同的对象,但 Key 不能重复,典型的 Key 是 String 类型,但也可以是任何对象。

Arraylist 与 LinkedList 区别

Arraylist 底层使用的是数组(存读数据效率高,插入删除特定位置效率低),LinkedList 底层使用的是双向循环链表数据结构(插入,删除效率特别高)。学过数据结构这门课后我们就知道采用链表存储,插入,删除元素时间复杂度不受元素位置的影响,都是近似 O(1)而数组为近似 O(n),因此当数据特别多,而且经常需要插入删除元素时建议选用 LinkedList.一般程序只用 Arraylist 就够用了,因为一般数据量都不会蛮大,Arraylist 是使用最多的集合类。

ArrayList 与 Vector 区别

Vector 类的所有方法都是同步的。可以由两个线程安全地访问一个 Vector 对象、但是一个线程访问 Vector
,代码要在同步操作上耗费大量的时间。Arraylist 不是同步的,所以在不需要同步时建议使用 Arraylist。

HashMap 和 Hashtable 的区别

  1. HashMap 是非线程安全的,HashTable 是线程安全的;HashTable 内部的方法基本都经过 synchronized 修饰。

  2. 因为线程安全的问题,HashMap 要比 HashTable 效率高一点,HashTable 基本被淘汰。

  3. HashMap 允许有 null 值的存在,而在 HashTable 中 put 进的键值只要有一个 null,直接抛出 NullPointerException。

Hashtable 和 HashMap 有几个主要的不同:线程安全以及速度。仅在你需要完全的线程安全的时候使用 Hashtable,而如果你使用 Java5 或以上的话,请使用 ConcurrentHashMap 吧

HashSet 和 HashMap 区别

HashSet 和 HashMap 区别

HashMap 和 ConcurrentHashMap 的区别

HashMap 与 ConcurrentHashMap 的区别

  1. ConcurrentHashMap 对整个桶数组进行了分割分段(Segment),然后在每一个分段上都用 lock 锁进行保护,相对于 HashTable 的 synchronized 锁的粒度更精细了一些,并发性能更好,而 HashMap 没有锁机制,不是线程安全的。(JDK1.8 之后 ConcurrentHashMap 启用了一种全新的方式实现,利用 CAS 算法。)
  2. HashMap 的键值对允许有 null,但是 ConCurrentHashMap 都不允许。

HashSet 如何检查重复

当你把对象加入 HashSet 时,HashSet 会先计算对象的 hashcode 值来判断对象加入的位置,同时也会与其他加入的对象的 hashcode 值作比较,如果没有相符的 hashcode,HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象,这时会调用 equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同,HashSet 就不会让加入操作成功。(摘自我的 Java 启蒙书《Head fist java》第二版)

hashCode()与 equals()的相关规定:

  1. 如果两个对象相等,则 hashcode 一定也是相同的
  2. 两个对象相等,对两个 equals 方法返回 true
  3. 两个对象有相同的 hashcode 值,它们也不一定是相等的
  4. 综上,equals 方法被覆盖过,则 hashCode 方法也必须被覆盖
  5. hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode(),则该 class 的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)。

==与 equals 的区别

  1. ==是判断两个变量或实例是不是指向同一个内存空间 equals 是判断两个变量或实例所指向的内存空间的值是不是相同
  2. ==是指对内存地址进行比较 equals()是对字符串的内容进行比较 3.==指引用是否相同 equals()指的是值是否相同

comparable 和 comparator 的区别

  • comparable 接口实际上是出自 java.lang 包 它有一个 compareTo(Object obj)方法用来排序
  • comparator 接口实际上是出自 java.util 包它有一个 compare(Object obj1, Object obj2)方法用来排序

一般我们需要对一个集合使用自定义排序时,我们就要重写 compareTo 方法或 compare 方法,当我们需要对某一个集合实现两种排序方式,比如一个 song 对象中的歌名和歌手名分别采用一种排序方法的话,我们可以重写 compareTo 方法和使用自制的 Comparator 方法或者以两个 Comparator 来实现歌名排序和歌星名排序,第二种代表我们只能使用两个参数版的 Collections.sort().

Comparator 定制排序

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

/**
 * TODO Collections类方法测试之排序
 * @author 寇爽
 * @date 2017年11月20日
 * @version 1.8
 */
public class CollectionsSort {

	public static void main(String[] args) {

		ArrayList<Integer> arrayList = new ArrayList<Integer>();
		arrayList.add(-1);
		arrayList.add(3);
		arrayList.add(3);
		arrayList.add(-5);
		arrayList.add(7);
		arrayList.add(4);
		arrayList.add(-9);
		arrayList.add(-7);
		System.out.println("原始数组:");
		System.out.println(arrayList);
		// void reverse(List list):反转
		Collections.reverse(arrayList);
		System.out.println("Collections.reverse(arrayList):");
		System.out.println(arrayList);
/*		
		 * void rotate(List list, int distance),旋转。
		 * 当distance为正数时,将list后distance个元素整体移到前面。当distance为负数时,将
		 * list的前distance个元素整体移到后面。
		 
		Collections.rotate(arrayList, 4);
		System.out.println("Collections.rotate(arrayList, 4):");
		System.out.println(arrayList);*/
		
		// void sort(List list),按自然排序的升序排序
		Collections.sort(arrayList);
		System.out.println("Collections.sort(arrayList):");
		System.out.println(arrayList);

		// void shuffle(List list),随机排序
		Collections.shuffle(arrayList);
		System.out.println("Collections.shuffle(arrayList):");
		System.out.println(arrayList);

		// 定制排序的用法
		Collections.sort(arrayList, new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				return o2.compareTo(o1);
			}
		});
		System.out.println("定制排序后:");
		System.out.println(arrayList);
	}

}

重写 compareTo 方法实现按年龄来排序

package map;

import java.util.Set;
import java.util.TreeMap;

public class TreeMap2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeMap<Person, String> pdata = new TreeMap<Person, String>();
		pdata.put(new Person("张三", 30), "zhangsan");
		pdata.put(new Person("李四", 20), "lisi");
		pdata.put(new Person("王五", 10), "wangwu");
		pdata.put(new Person("小红", 5), "xiaohong");
		// 得到key的值的同时得到key所对应的值
		Set<Person> keys = pdata.keySet();
		for (Person key : keys) {
			System.out.println(key.getAge() + "-" + key.getName());

		}
	}
}

// person对象没有实现Comparable接口,所以必须实现,这样才不会出错,才可以使treemap中的数据按顺序排列
// 前面一个例子的String类已经默认实现了Comparable接口,详细可以查看String类的API文档,另外其他
// 像Integer类等都已经实现了Comparable接口,所以不需要另外实现了

class Person implements Comparable<Person> {
	private String name;
	private int age;

	public Person(String name, int age) {
		super();
		this.name = name;
		this.age = age;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public int getAge() {
		return age;
	}

	public void setAge(int age) {
		this.age = age;
	}

	/**
	 * TODO重写compareTo方法实现按年龄来排序
	 */
	@Override
	public int compareTo(Person o) {
		// TODO Auto-generated method stub
		if (this.age > o.getAge()) {
			return 1;
		} else if (this.age < o.getAge()) {
			return -1;
		}
		return age;
	}
}

如何对 Object 的 list 排序

  • 对 objects 数组进行排序,我们可以用 Arrays.sort()方法
  • 对 objects 的集合进行排序,需要使用 Collections.sort()方法

如何实现数组与 List 的相互转换

List 转数组:toArray(arraylist.size()方法;数组转 List:Arrays 的 asList(a)方法

List<String> arrayList = new ArrayList<String>();
		arrayList.add("s");
		arrayList.add("e");
		arrayList.add("n");
		/**
		 * ArrayList转数组
		 */
		int size=arrayList.size();
		String[] a = arrayList.toArray(new String[size]);
		//输出第二个元素
		System.out.println(a[1]);//结果:e
		//输出整个数组
		System.out.println(Arrays.toString(a));//结果:[s, e, n]
		/**
		 * 数组转list
		 */
		List<String> list=Arrays.asList(a);
		/**
		 * list转Arraylist
		 */
		List<String> arrayList2 = new ArrayList<String>();
		arrayList2.addAll(list);
		System.out.println(list);

如何求 ArrayList 集合的交集 并集 差集 去重复并集

需要用到 List 接口中定义的几个方法:

  • addAll(Collection<? extends E> c) :按指定集合的 Iterator 返回的顺序将指定集合中的所有元素追加到此列表的末尾
    实例代码:
  • retainAll(Collection<?> c): 仅保留此列表中包含在指定集合中的元素。
  • removeAll(Collection<?> c) :从此列表中删除指定集合中包含的所有元素。
package list;

import java.util.ArrayList;
import java.util.List;

/**
 *TODO 两个集合之间求交集 并集 差集 去重复并集
 * @author 寇爽
 * @date 2017年11月21日
 * @version 1.8
 */
public class MethodDemo {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		List<Integer> list1 = new ArrayList<Integer>();
		list1.add(1);
		list1.add(2);
		list1.add(3);
		list1.add(4);

		List<Integer> list2 = new ArrayList<Integer>();
		list2.add(2);
		list2.add(3);
		list2.add(4);
		list2.add(5);
		// 并集
		// list1.addAll(list2);
		// 交集
		//list1.retainAll(list2);
		// 差集
		// list1.removeAll(list2);
		// 无重复并集
		list2.removeAll(list1);
		list1.addAll(list2);
		for (Integer i : list1) {
			System.out.println(i);
		}
	}

}

HashMap 的工作原理及代码实现

集合框架源码学习之 HashMap(JDK1.8)

ConcurrentHashMap 的工作原理及代码实现

ConcurrentHashMap 实现原理及源码分析

集合框架底层数据结构总结

- Collection

1. List

  • Arraylist:数组(查询快,增删慢 线程不安全,效率高 )
  • Vector:数组(查询快,增删慢 线程安全,效率低 )
  • LinkedList:链表(查询慢,增删快 线程不安全,效率高 )

2. Set

  • HashSet(无序,唯一):哈希表或者叫散列集(hash table)
  • LinkedHashSet:链表和哈希表组成 。 由链表保证元素的排序 , 由哈希表证元素的唯一性
  • TreeSet(有序,唯一):红黑树(自平衡的排序二叉树。)

- Map

  • HashMap:基于哈希表的 Map 接口实现(哈希表对键进行散列,Map 结构即映射表存放键值对)
  • LinkedHashMap:HashMap 的基础上加上了链表数据结构
  • HashTable:哈希表
  • TreeMap:红黑树(自平衡的排序二叉树)

集合的选用

主要根据集合的特点来选用,比如我们需要根据键值获取到元素值时就选用 Map 接口下的集合,需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap.当我们只需要存放元素值时,就选择实现 Collection 接口的集合,需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet,不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList,然后再根据实现这些接口的集合的特点来选用。

2018/3/11 更新

集合的常用方法

今天下午无意看见一道某大厂的面试题,面试题的内容就是问你某一个集合常见的方法有哪些。虽然平时也经常见到这些集合,但是猛一下让我想某一个集合的常用的方法难免会有遗漏或者与其他集合搞混,所以建议大家还是照着 API 文档把常见的那几个集合的常用方法看一看。

会持续更新。。。

参考书籍:

《Head first java 》第二版 推荐阅读真心不错 (适合基础较差的)

《Java 核心技术卷 1》推荐阅读真心不错 (适合基础较好的)

《算法》第四版 (适合想对数据结构的 Java 实现感兴趣的)

  • B3log

    B3log 是一个开源组织,名字来源于“Bulletin Board Blog”缩写,目标是将独立博客与论坛结合,形成一种新的网络社区体验,详细请看 B3log 构思。目前 B3log 已经开源了多款产品:SymSoloVditor思源笔记

    1090 引用 • 3467 回帖 • 296 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3165 引用 • 8206 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...