面试:Java 容器

1. Java Collections 框架是什么?

Java Collections 框架中包含了大量集合接口以及这些接口的实现类和操作它们的算法(例如排序、查找、反转、替换、复制、取最小元素、取最大元素等),具体而言,主要提供了List(列表)、 Queue(队列)、Set(集合)、 Stack(栈)和Map(映射表,用于存放键值对)等数据结构。其中,ListQueueSetStack都继承自 Collection 接口。

Collection 是整个集合框架的基础,它里面储存一组对象,表示不同类型的 Collections它的作用只是提供维护一组对象的基本接口而已

2. 什么是迭代器?

迭代器( Iterator )是一个对象,它的工作是遍历并选择序列中的对象它提供了一种访问一个容器( container )对象中的各个元素,而又不必暴露该对象内部细节的方法。通过迭代器,开发人员不需要了解容器底层的结构,就可以实现对容器的遍历。由于创建迭代器的代价小,因此迭代器通常被称为轻量级的容器

迭代器的使用有 3 个注意事项:

  1. 使用 iterator() 方法返回一个 Iterator,然后通过 Iteratornext() 方法返回第一个元素

  2. 使用 IteratorhasNext() 方法判断容器中是否还有元素,如果又,可以使用 next() 方法获取下一个元素

  3. 可以通过 remove() 方法删除迭代器返回的元素。


import java.util.*;

public class IteratorTest{

public static void main (String[] args) {

List<String> ll = new LinkedList<String>();

ll.add("first");

ll.add("second");

ll.add("third");

ll.add("fourth");

for(Iterator<String> iter = ll.iterator(); iter.hasNext();){

String str = iter.next(); // 调用 next() 会返回下一个元素

System.out.println(str);

}

}

}

// first

// second

// thrid

// fourth

使用 iterator() 方法时经常遇到 ConcurrentModificationException 异常,通常是由于使用 Iterator 遍历容器的同时又对容器做增加或删除操作导致的,或者由于多线程操作导致,当一个线程使用迭代器遍历的同时,另一个线程对这个容器进行增加或删除操作。

下面介绍单线程抛出 ConcurrentModificationException 的情况:


import java.util.*;

public class IteratorTest{

public static void main (String[] args) {

List<String> ll = new LinkedList<String>();

ll.add("first");

ll.add("second");

ll.add("third");

ll.add("fourth");

for(Iterator<String> iter = ll.iterator(); iter.hasNext();){

String str = iter.next();

System.out.println(str);

if(str.equals("second")){

ll.add("five");

}

}

}

}

运行结果:


first

second

Exception in thread "main" java.util.ConcurrentModificationException

at java.base/java.util.LinkedList$List..eckForComodification(LinkedList.java:970)

at java.base/java.util.LinkedList$ListItr.next(LinkedList.java:892)

at IteratorTest.main(IteratorTest.java:10)

抛出上述异常的主要原因是当调用容器的 Iterator() 方法返回 Iterator 对象时,把容器中包含对象的个数赋值给了一个变量 expectedModCount,在调用next()方法时会比较变量 expectedModCount与容器中实际对象的个数 modCount的值是否相等,若二者不相等,则会抛出 ConcurrentModificationException异常,因此在使用 Iterator 遍历容器的过程中,如果对容器进行增加或删除操作,就会改变容器中对象的数量,从而导致抛出异常。

解决方法如下:在遍历的过程中把需要删除的对象保存到一个集合中,等遍历结束后在调用 removeAll() 方法来删除,或者使用iter.remove()方法

那多线程抛出 ConcurrentModificationException 怎么解决?

3. ArrayList、Vector、LinkedList 的区别

ArrayListVectorLinkedlist类均在java.ui包中,均为可伸缩数组,即可以动态改变长度的数组。

ArrayListVector 都是基于存储元素的 Object[] array来实现的,它们会在内存中开辟块连续的空间来存储,由于数据存储是连续的,因此,它们支持用序号(下标)来访问元素,同时索引数据的速度比较快。但是在插入元素时需要移动容器中的元素,所以对数据的插入操作执行得比较慢。 ArrayListVector 都有一个初始化的容量的大小,当里面存储的元素超过这个大小时就需要动态地扩充它们的存储空间。为了提高程序的效率,每次扩充容量,不是简单地扩充一个存储单元,而是一次增加多个存储单元。 Vector 默认扩充为原来的2倍(每次扩充空间的大小是可以设置的),而 ArrayList 默认扩充为原来的1.5倍(没有提供方法来设置空间扩充的方法)

ArrayListVector 最大的区别就是 synchronization(同步)的使用, ArrayList的方法都不是同步的,而 Vector 的绝大多数方法(例如addinsertremovesetequalshashcode等)都是直接或者间接同步的,所以Ⅴector是线程安全的, ArrayList不是线程安全的。正是由于 Vector 提供了线程安全的机制,其性能上也要略逊于 ArrayList

LinkedList 是采用双向列表来实现的,对数据的索引需要从列表头开始遍历,因此用于随机访问则效率比较低,但是插入元素时不需要对数据进行移动,因此插入效率较高。同时,LinkedList非线程安全的容器。

4. HashMap、HashTable、TreeMap、WeakHashMap 的区别

java.util.Map 包括 3 个实现类:HashMapHashTableTreeMap

HashMap 是一个最常用的 Map,它根据键的 HashCode 值存储数据,根据键可以直接获取它的值,具有很快的访问速度。由于 HashMapHashTable都采用了 hash 法进行索引,因此二者具有许多相似之处,它们主要有如下的一些区别:

  1. HashMapHashTable轻量级实现(非线程安全的实现),它们都完成了Map 接口,主要区别在于 HashMap 允许空(null)键值(key)(但需要注意,最多只允许一条记录的键为 null ,不允许多条记录的值为null)HashTable 不允许。

  2. HashMapHashTablecontains()方法去掉了,改成 containsvalue()containsKey(),因为contains方法容易让人引起误解。 HashTable 继承自 Dictionary 类,而 HashMap是 Java1.2 引进的 Map interface的一个实现。

  3. HashTable是线程安全的,而 HashMap 不支持线程同步,所以不是线程安全的。在多线程访问时,对 HashMap 需要额外的同步机制,HashTable不用。效率而言,HashMap 可能更高。

  4. HashTable 使用 EnumerationHashMap 使用 Iterator

  5. HashTableHashMap 采用的 hash/rehash 算法几乎一样,性能不会有太大差异。

  6. HashTable中,hash 数组默认大小是11,增加的方式是old×2+1。在 HashMap中,hash数组的默认大小是16,而且一定是2的指数。

  7. hash 值的使用不同,HashTable直接使用对象的 hashCode

以上3种类型中,使用最多的是 HashMapHashMap里面存入的键值对在取出时没有固定的顺序,是随机的。一般而言,在 Map 中插入、删除和定位元素, HashMap是最好的选择。

由于 TreeMap实现了 SortMap 接口,能够把它保存的记录根据键排序,因此,取出来的是排序后的键值对,如果需要按自然顺序或自定义顺序遍历键,那么 TreeMap会更好。

LinkedHashMapHashMap的一个子类,如果需要输出的顺序和输入的相同,那么用 LinkedHashMap可以实现,它还可以按读取顺序来排列

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

HashTable 上下文中,同步是指什么?

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

如何实现 HashMap 的同步?

HashMap可以通过Map m = Collections.synchronizedMap(new HashMap())来达到同步的效果。具体而言,该方法返回一个同步的 Map,该 Map 封装了底层的 HashMap 的所有方法,使得底层的 HashMap 即使是在多线程的环境中也是安全的。

5. 用自定义作为 HashMap 或 HashTable 的 key 要注意哪些问题?

HashMapHashTable这两个容器都有一个限制:不能用来存储重复的 key。当有重复的键时,不会创建新的映射关系,而会使用先前的 value 值。

下面是往 HashMap 中放重复的字符串 key

下面是往 HashMap 中放重复的自定义的对象 key

我们存放的是自定义的 Person 对象。添加键值对 <key,value> 的时候,调用 key 对象的 hashCode() 生成一个 hash 值 h1,如果 h1 在 HashMap 中不存在,则直接添加 <key,value>;如果已存在,那么找出 HashMap 中所有的 hash 值为 h1 的 key,然后分别调用 keyequals() 方法判断当前添加的 key 是否与已经存在的 key 值相同。如果 equals() 返回 true,说明当前需要添加的 key 已经存在,那么将会覆盖旧的键值对。如果为 false,说明新添加的 key 在 HashMap 中不存在,将会创建新的键值对。当新增加的 key 的 hash 值已经在 HashMap 中存在时,就会产生冲突。一般而言,对于不同的 key 可能会得到相同的 hash 值,因此需要对冲突进行处理。处理冲突的方法有:开放定址法、再 hash 法、链地址法等。HashMap 使用的是链地址法解决冲突。(key 不同但 hash 相同)

说白了,就是先用 hashCode() 找 Hash 地址,然后去对应的链里面依次看每个 key 是否 equals(),相等认为是同一个 key,否则不等。

key equals (相同),hash code 必要相同;key 不同,hash code 必不同;hash code 相同,key 不一定相同;不同的 key,可以有相同的 hash code。

HashMap 中通过 key 查找 value时,首先调用的是keyhashCode() 方法来获取到key对应的hashh,这样就可以确定键为key的所有值存储的首地址。如果h对应的key值有多个,那么程序接着会遍历所有key,通过调用keyequals()方法来判断key的内容是否相等。只有当 equals() 方法的返回值为true时,对应的 value 才是正确的结果。

上面的 Person 类没有重写 hashCode()equals() 方法,默认使用 Object 的这两个方法。Object 类的 equals()方法规则:参数 obj 引用的对象是同一个对象,则返回true,否则返回 false。Object 类的 hashCode()返回对象的内存地址。

不同的对象默认 hash 值是内存地址,所以两个 Person 是 hash 不同的,添加到 HashMap时,调用 equals() 返回 falseHashMap 认为它们两个是不同的对象,就会创建不同的映射关系。我们需要重写 hashCode()equals() 方法。

  1. 如果根据对象的相关属性来自定义对象是否是相等的逻辑,此时必须重写 equals(),一旦重写了 equals(),必须重写 hashCode()

  2. 当自定义类的多项作为 HashMap (HashTable)的 key 时,最好把这个类设为不可变类

  3. 从 HashMap 的工作原理可以看出,如果两个对象相等,那么两个对象有相同的 hashCode,反之则不成立。

6. Collection 和 Collections 的区别

Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。实现该接口的类主要有 ListSet该接口的设计目标是为各种具体的集合提供最大化的统一的操作方式。

Collections针对集合类的一个包装类,它提供一系列静态方法以实现对各种集合的搜索、排序、线程安全化等操作,其中大多数方法都是用来处理线性表。 Collections不能实例化,如同一个工具类,服务于 Collection 框架。若在使用 Collections 类的方法时,对应的 collecion 的对象为 null,则这些方法都会抛出 NullPointerException

使用 Collections 来排序的示例:


import java.util.*;

public class Test{

public static void main(String args){

List<Integer> list = new LinkedList<Integer>();

int array[] = {1,7,3,2};

for(int i = 0; i < array.length; i++){

list.add(new Integer(array[i]));

}

Collections.sort(list);

for(int i = 0; i < array.length; i++){

System.out.println(list.get(i));

}

}

}

// 1

// 2

// 3

// 7