Java中的集合（面试题）

思维导图

1. HashMap排序题， 上机题

已知一个HashMap<Integer, User> 集合，User 有name (String) 和age (int)属性。请写一个方法实现对HashMap的排序功能，该方法接收HashMap <Integer, User>为形参，返回类型为HashMap
<Integer, User>,要求对HashMap中的User的age倒序进行排序。排序时key=value键值对不得拆散。.

注意: 要做出这道题必须对集合的体系结构非常的熟悉HashMap 本身就是不可排序的，但是该道题偏偏让给HashMap排序,那我们就得想在API中有没有这样的Map结构是有序的，
LinkedHashMap, 对的，就是它，它是Map结构,也是链表结构,有序的，更可喜的是他是HashMap的子类,我们返回LinkedHashMap <Integer,User>即可，还符合面向接口(父类编程的思想)。但凡是对集合的操作,我们应该保持一个原则就是能用JDK中的API就有JDK中的API,比如排序算法我们不应该去用冒泡或者选择，而是首先想到用Collections集合工具类。

public class HashMapTest {
public static void main(String[] args) {
HashMap<Integer, User> users = new HashMap<>() ;
users.put(1, new User ("张三"，25) ) ;
users.put(3, new User ("李四"，22) );
users.put(2, new User ("王五"，28) ) ;
System.out.println(users) ;
HashMap<Integer, User> sortHashMap = sortHas hMap (users) ;
System. out . print ln (sortHashMap) ;
/**
*控制台输出内容
* {1=User [name=张三， age=25]，2=User [name=王五， age=28]， 3=User [name=李四， age=22] }
  {2=User [name=王五， age=28]， 1=User [name=张三， age=25]， 3-User [name=李四， age=22]}
*/
}
public static HashMap<Integer, User> sortHashMap (HashMap<Integer, User> map) {
//首先拿到map的键值对集合
Set<Entry<Integer, User>> entrySet = map.entrySet() ;
// 将set 集合转为List集合，为什么，为了使用工具类的排序方法
List<Entry<Integer, User>> list = new ArrayList<Entry<Integer, User>> (entrySet);
//使用Collections集合工具类对list进行排序，排序规则使用匿名内部类来实现
Collections.sort (list, new Comparator<Entry<Integer, User>>() {
@Override
public int compare (Entry<Integer, User> o1, Entry<Integer, User> o2) {
//按照要求根据User的age的倒序进行排
return o2.getValue().getAge()-o1.getValue().getAge() ;
}) ;
//创建-一个新的有序的HashMap子类的集合
Linke dHashMap<Integer, User> linkedHashMap = new LinkedHashMap<Integer, User> () ;
//将List中的数据存储在LinkedHashMap中
for (Entry<Integer, User> entry : list) {
linkedHashMap.put (entry.getKey(), entry.getValue()) ;
}
//返回结果
return linkedHashMap;
}
}

2.集合的安全性问题

请问ArrayList、HashSet、 HashMap 是线程安全的吗?如果不是我想要线程安全的集合怎么办?
　
　我们都看过上面那些集合的源码(如果没有那就看看吧) ,每个方法都没有加锁，显然都是线程不安全的。话又说过来如果他们安全了也就没第二问了。在集合中Vector和HashTable 倒是线程安全的。你打开源码会发现其实就是把各自核心方法添加上了synchronized关键字。Collections工具类提供了相关的API,可以让上面那3个不安全的集合变为安全的。

//Collections. synch ronizedCollection (c )
//Collections. synch ronizedList (list)
//Collec tions. synch roni ze dMap (m)
//Collections. synchronizedSet (s)

上面几个函数都有对应的返回值类型，传入什么类型返回什么类型。打开源码其实实现原理非常简单，就是将集合的核心方法添加了synchronized关键字。

3. ArrayList 内部用什么实现的?

(回答这样的问题，不要只回答个皮毛，可以再介绍一下 ArrayList内部是如何实现数组的增加和删除的,因为数组在创建的时候长度是固定的，那么就有个问题我们往ArrayList 中不断的添加对象，它是如何管理这些数组呢? )
　ArrayList内部是用Object[]实现的。接下来我们分别分析ArrayList的构造、add、remove、 clear 方法的实现原理。
　
一、构造函数
1)空参构造

/**
* Constructs a new {@code ArrayList} instance with zero initial capacity.
* /
public ArrayList() {
array = EmptyArray.OBJECT;

array是一个Object[]类型。当我们new -个空参构造时系统调用了EmptyArray.OBJECT 属性, EmptyArray仅
仅是一个系统的类库,该类源码如下:

public final class EmptyArray {
private EmptyArray() {}
public static final boolean[] BOOLEAN = new boolean[0] ;
public static final byte[] BYTE = new byte[0] ;
public static final char[] CHAR = new char[0] ;
public static final double[] DOUBLE = new double[0] ;
public static final int[] INT = new int[0] ;
public static final Class<?>[] CLASS = new Class[0] ;
public static final Object[] OBJECT = new Object[0] ;
public static final String[] STRING = new String[0] ;
public static final Throwable[] THROWABLE = new Throwable[0] ;
public static final StackTraceElement[] STACK_TRACE_ELEMENT = new StackTraceElement[0];
}

也就是说当我们new -个空参ArrayList 的时候，系统内部使用了-个new Object[0]数组。

2)带参构造1

/**
* Constructs a new instance of {@code ArrayList} with the specified
* initial capacity.
* @param capacity
* the initial capacity of this {@code ArrayList} .
*/
public ArrayList(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException ("capacity < 0: " + capacity) ;
}
array = (capacity == 0 ? EmptyArray.OBJECT:new object [capacity]);
}

该构造函数传入一个int值,该值作为数组的长度值。如果该值小于0,则抛出一个运行时异常。如果等于0,则使用一个空数组，如果大于0,则创建一个长度为该值的新数组。

3)带参构造2

/**
* Constructs a new instance of {@code ArrayList} containing the elements of
* the specified collection.
* @param collection
* the collection of elements to add.
*/
public ArrayList (Collection<? extends E> collection) {
if (collection == null) {
throw new Nul1PointerException("collection == null");
}
object[] a = collection.toArray() ;
if(a.getClass()!= object[].class) {
object[] newArray = new object[a.length];
System.arraycopy(a,0,newArray,0, a.length) ;
a = newArray;
}
array = a;
size = a.length;
}

如果调用构造函数的时候传入了一个Collection的子类,那么先判断该集合是否为null,为null则抛出空指针异常。如果不是则将该集合转换为数组a,然后将该数组赋值为成员变量array,将该数组的长度作为成员变量size.这里面它先判断a.getClass是否等于Object[].class,toArray方法是Collection接口义的因此其所有的子类都有这样的方法，list集合的toArray和Set集合的toArray
返回的都是Object[]数组。
　　其实在看Java源码的时候，作者的很多意图都很费人心思，我能知道他的目标是啥，但是不知道他为何这样写。比如对于ArrayList，array 是他的成员变量,但是每次在方法中使用该成员变量的时候作者都会重新在方法中开辟一个局部变量,然后给局部变量赋值为array,然后再使用，有人可能说这是为了防止并发修改array,毕竟array是成员变量,大家都可以使用因此需要将array变为局部变量,然后再使用,这样的说法并不是都成立的,也许有时候就是老外们写代码的一个习惯而已。
　　
二、add方法
add方法有两个重载,这里只研究最简单的那个。

/*
* Adds the specified object at the end of this {@code ArrayList}.
* @param obj ect
* the object to add.
* @return always true
*/
@Override public boolean add(E object) {
object[] a = array;
int s = size;
if (s == a.length){
object[] newArray = new object[s +
(s < (MIN CAPACITY_ INCREMENT / 2) ?
MIN CAPACITY INCREMENT : s >> 1)];
System. arraycopy(a, 0, newArray, 0, s);
array= a= newArray;
}
a[s] = object;
size = s+1;
modCount++;
return true;
}

1、首先将成员变量array赋值给局部变量a,将成员变量size赋值给局部变量s。
2、判断集合的长度s是否等于数组的长度(如果集合的长度已经等于数组的长度了,说明数组已经满了，该重新分配新数组了)，重新分配数组的时候需要计算新分配内存的空间大小，如果当前的长度小于MIN_CAPACITY INCREMENT/2 (这个常量值是12,除以2就是6,也就是如果当前集合长度小于6)则分配12个长度，如果集合长度大于6则分配当前长度s的一半长度。这里面用到了三元运算符和位运算，s >> 1,意思就是将s往右移1位,相当于s=s/2,只不过位运算是效率最高的运算。
3、将新添加的object对象作为数组的a[s]个元素。
4、修改集合长度size为s+1。
5、modCotun+ +,该变量是父类中声明的，用于记录集合修改的次数,记录集合修改的次数是为了防止在用迭代器迭代集合时避免并发修改异常，或者说用于判断是否出现并发修改异常的。
6、return true,这个返回值意义不大，因为一直返回true,除非报了一个运行时异常。
三、remove方法
remove方法有两个重载，我们只研究remove (int index)方法。

/*Removes the object at the specified location from this list.
* @param index
* the index of the object to remove 。
* areturn the removed object. 
* @throws IndexOu tofBounds Exception
* when {@code location < 0 || location >= size() }
*/
@Override public E remove (int index) {
object[] a = array;
int s = size;
if (index >= s) {
throwIndexOu tOfBounds Exception (index, s);
}
@SuppressWarnings ("unchecked")
E result = (E) a [index] ;
System.arraycopy(a, index + 1, a, index, --s -index) ;
a[s] = null; // Prevent memory leak
size = s
modCount++;
return result;
}

1、先将成员变量array和size赋值给局部变量a和s。
2、判断形参index是否大于等于集合的长度，如果成了则抛出运行时异常
3、获取数组中脚标为index的对象result,该对象作为方法的返回值
4、调用System的arraycopy函数，拷贝原理如下图所示。

System.arraycopy(a, index + 1，a, index, --s - index);

假设index=2，那么要删除的对象如图打叉部分，我们只需要将该数组后面蓝色区域整体往前移动一位位置即可。上面的代码完成就是这个工作。
5.接下来就是很重要的一个工作,因为删除了一个元素，而且集合整体向前移动了一位,因此需要将集合最后一个元索设置为null,否则就可能内存泄露。
6、重新给成员变量array 和size赋值。
7.记录修改次数。
8、返回删除的元素(让用户再看最后一眼)。

四、dear方法

/**
* Removes all elements from this {@code ArrayList. leaving it * * ewpty.
* @see #isEmpty
* @see #size
*/
Override public void clear() {
if (size != 0){
Arrays.fil(array.0, size,null);
size = 0;
modCount++;
}
}

4. List 的三个子类的特点

ArrayList底层结构是数组底层查询快,增删慢。
LinkedList底层结构是链表型的,增删快,查询慢。
voctor底层结构是数组 线程安全的,增删慢查询慢。

5. List 和Map、Set 的区别

5.1结构特点
List和Set是存储单列数据的集合，
Map是存储键和值这样的双列数据的集合;

List 中存储的数据是有顺序,并且允许重复; Map中存储的数据是没有顺序的，其键是不能重复的，它的值是可以有重复的，Set 中存储的数据是无序的，且不允许有重复,但元素在集合中的位置由元素的hashcode决定,位置是固定的(Set集合根据hashcode来
进行数据的存储,所以位置是固定的,但是位置不是用户可以控制的,所以对于用户来说set中的元素还是无序的) ;

5.2实现类
List接口有三个实现类(LinkedList:基于链表实现,链表内存是散乱的,每一个元素存储本身内存地址的同时还存储下一个元素的地址。链表增删快,查找慢; ArrayList: 基于数组实现，非线程安全的,效率高，便于索引，但不便于插入删除; Vector:基于数组实现，线程安全的，效率低)。
Map接口有三个实现类(HashMap: 基于hash表的Map接口实现,非线程安全,高效，支持null值和null键; HashTable: 线程安全，低效,不支持null值和null键; LinkedHashMap: 是HashMap的一个子类,保存了记录的插入顺序; SortMap 接口: TreeMap, 能够把它保存的记录根据键排序,默认是键值的升序排序)。
Set接口有两个实现类(HashSet: 底层是由HashMap实现，不允许集合中有重复的值，使用该方式时需要重写equals0和hashCode0方法; LinkedHashSet: 继承与HashSet,同时又基于LinkedHashMap来进行实现，底层使用的是LinkedHashMp)。

5.3区别
List集合中对象按照索引位置排序，可以有重复对象，允许按照对象在集合中的索引位置检索对象，例如通过list.get()方法来获取集合中的元素; Map中的每一个元素包含一个键和一个值，成对出现，键对象不可以重复,值对象可以重复; Set集合中的对象不按照特定的方式排序,并且没有重复对象,但它的实现类能对集合中的对象按照特定的方式排序,例如TreeSet类,可以按照默认顺序,也可以通过实现Java.util.Comparator 接口来自定义排序方式。

6 HashMap 和HashTable有什么区别?

HashMap是线程不安全的,HashMap是一个接口,是Map的一个子接口,是将键映射到值得对象不允许键值重复，允许空键和空值；由于非线程安全,HashMap的效率要较HashTable的效率高一些.
HashTable是线程安全的一个集合,不允许null值作为一个key值或者Value值;
HashTable是sychronize,多个线程访问时不需要自己为它的方法实现同步，而HashMap在被多个线程访问的时候需要自己为它的方法实现同步;

7. Java 中ArrayList和Linkedlist区别?

ArrayList和Vector使用了数组的实现，可以认为ArrayList或者Vector封装了对内部数组的操作,比如向数组中添加，删除，插入新的元素或者数据的扩展和重定向。LinkedList使用了循环双向链表数据结构。与基于数组的ArrayList相比,这是两种截然不同的实现技术，这也决定了它们将适用于完全不同的工作场景。
LinkedList链表由一系列表项连接而成。一个表项总是包含3个部分:元素内容,前驱表和后驱表,如图所示:

在下图展示了一个包含3个元素的LinkedList的各个表项间的连接关系。在JDK的实现中，无论LikedList是否为空,链表内部都有一个header表项,它既表示链表的开始,也表示链表的结尾。表项header的后驱表项便是链表中第一个元素，表项header的前驱表项便是链表中最后一个元素。

8. Map中的key和value可以为null么?

HashMap对象的key. value 值均可为null.
HahTable对象的key. value 值均不可为null,
且两者的的key值均不能重复,若添加key相同的键值对,后面的value会自动覆盖前面的value,但不会报错。
测试代码如下:

public class Test {
public static void main (String[] args) {
Map<String, String> map = new HashMap<String,String>();// HashMap对象
Map<String, String> tableMap = new Hashtable<String, String>(); //HashTable对象
map.put(null, null) ;
System.out.println ("hashMap的[key]和[value ]均可以为null:"+map.get(null));
try {
tableMap.put(null,"3");
System.out.println(tableMap.get(null));
} catch (Exception e) {
System.out.println(" [ERROR] : hashTable的[key]不能为null") ;
}
try {
tableMap.put ("3",null);
System.out.println(tableMap.get ("3"));
} catch(Exception e) {
System.out.println(" [ERROR] : hashTable的[value]不能为null");
}
}
}

运行结果: