简介

java集合类是java.util 包中的重要内容。java集合框架包含了大量集合接口以及这些接口的实现类和操作他们的算法。

java集合框架图

主要提供的数据结构

• List

  又称有序的Collection。它按照对象的进入顺序保存对象，可以对列表中的每个元素的出入和删除元素位置进行精确的控制。同时，它可以保存重复的对象。
  LinkedList、ArrayList、Vector都实现了List接口。

• Set

  Set 是数学意义上的集合。集合中元素不可重复。因此存入set的每个元素都必须通过equals()方法来确定对象的唯一性。
  Set 接口有两实现类，HashSet和TreeSet其中TreeSet 实现了SrotedSet接口所以TreeSet是有序的。

• Map

  Map 提供一个从键映射到值得数据结构。它用于保存键值对，其中值可以重复，但是键一定唯一，不能重复。Java类库中有多个实现该接口的类：HashMap、LinkedHashMap、TreeMap、WeakHashMap、IdentityHashMap。

Collection和Collections有什么区别

• Collection是一个集合的接口。它提供了对集合对象进行基本操作的通用接口方法。实现该类的主要方法有List和Set。
• Collections是针对集合类的一个包装类，它提供一系列的静态方法以实现对各种集合的搜索、排序、线程安全化等操作。（其中大多数方法都是用来处理线性表）

List

ArrayList，LinkedList和Vector的区别

• ArrayList和Vector都是由Object[]实现的，LinkedList是由双向链表实现的。
• Vector是线程安全的，Vector中绝大多数的方法都是直接或者间接同步的。
• ArrayList每次扩容1.5倍，Vector每次扩容2倍。

Map

HashMap添加的过程

1. 调用Key的hashCode()方法生成一个hash值h1。

   • 如果这个h1在HashMap中不存在，那么直接将添加到HashMap中。
   • 如果这个h1已经存在了那么找出HashMap中所有Hash值为h1的key。

2. 分别调用equals()方法判断当前添加的key是否与已经存在的key值相同

   如果相同，说明当前的Key已经存在。HashMap会使用新的value覆盖原有的value。
   如果没有相同，说明当前的Key不存在。HashMap会创建新的映射关系。

3. Hash冲突的解决。（当新增的key的Hash值在HashMap中存在时，就会产生冲突。一般有开放地址法、再Hash法、链地址法等解决Hash冲突问题。
   HashMap使用的是链地址法来解决冲突的

HashMap的查找过程

1. 调用hashCode()方法获取Key的Hash值h,确定键为Key的所有值存储的首地址。
2. 如果Key的值有多个，程序会遍历所有结果，并通过调用key的equals()方法来判断key的内容是否相等。只有当equals()方法的返回值为true时，对应的value才是正确值。

HashMap和HashTable的区别

• 继承的父类不同：HashTable继承自Dictionary类，而HashMap继承自Abstract Map类但是都两者实现了Map接口
• 线程安全性不同：HashTable 的方法是线程安全的，其中的每个方法都加入了Synchronized同步。
• 提供的方法不同：HashMap和HashTable相似度很高，但是也有区别，在HashMap中将contain方法去掉了，改成了containsValue和containsKey。（contains容易造成误解）
• key和value是否可以为空值（null）：在HashMap中允许且只允许一个key值为null,允许多个value值为null。HashTable中Key和value都不允许为null。

• 遍历方式实现不同：HashTable和HashMap都是用了迭代器Iterator ¹。
  HashTable中还使用了Enumeration方式。

• Hash值不同：HashTable直接将对象的HashCode作为Hash值。HashMap则重新计算key的Hash值。

• 数组的初始化不同：HashTable默认为11，扩容为（old*2+1）,HashMap 默认为16,扩容为（old*2)

WeakHashMap 和 HashMap 的异同

• WeakHashMap 和 HashMap类似。二者不同的地方在于WeakHashMap中的Key采用的是“弱引用”的方式，只要WeakHashMap中的Key不再被外部引用。它就可以被垃圾回收器回收。
  
• 而HashMap采用的是“强引用”的方式。当HashMap中的Key没有被外部引用时，只有在这key从HashMap中被删除之后，才可以被垃圾回收器回收。

HashMap、LinkedHashMap和TreeMap的异同

• HashMap里面存入的键值对在取出时没有固定的顺序，是随机的。
• TreeMap实现了SortMap的接口，能够把保存的记录根据键排序。因此取出来的是排序好的键值对。

• LinkedHashMap 是HashMap的一个子类，如果需要输入和输出顺序相同则使用LinkedHashMap可以实现。（LinkedHashMap还可以按照读取顺序排序）

  HashMap 上下文中，同步指的是什么？

  同步意味着，在同一时刻中只有一个线程可以修改Hash表，任何线程在执行HashTable的更新操作前都要获取对象锁，其他线程则等待线程锁的释放。

如何实现HashMap的同步？

HashMap以使用

Map m = Collections.synchronizedMap(new HashMap());

来达到同步的效果。

Java集合框架 面试问题整理