面试专题|Java容器篇

01.两大主要接口

Java容器类中两大主要接口是collection和map，其中list，set，queue均扩展了collection接口，而map则没有。

02.collection和collections的区别

collection是一个接口，用来存储一组对象（元素），有些collection允许有重复的元素，有的则不允许；有些collection是有序的，有的则是无序。它是set、list等常用接口的父接口。

collections是一个工具类，它提供了一些静态方法来操作collection，如对集合排序、返回最大值最小值等，主要用来服务collection接口。

03.set，list，map的特性以及主要实现类

map：存储键值对（key-value），即将键映射到值，键不允许重复，每个键只能映射一个值。主要实现类有hashmap，hashtable。

set：不允许有重复元素，无序，类似于数学上的集合，可用于去重。主要实现类有hashset，treeset，linkedhashset。

list：允许有重复元素，有序。主要实现类有arraylist，linkedlist，vector。

04.hashmap的实现原理

实现了map接口，使用put(key,value)存储键值对对象，使用get(key)获取对象。其底层数据结构是哈希表，即数组加链表，简单理解就是数组中的每个单元（桶）存储的是一张链表。

当调用put(key,value)存储元素时，会对键调用hashcode()来返回键的hashcode，再进行相应运算找到该元素的存储位置，如果存储位置已经被占，那么说明这两个元素的键的hashcode值相同，即发生了“哈希碰撞”。

解决哈希碰撞的方法之一是拉链法：此时两个键的hashcode相同，于是调用equals()来比较这两个键是否相同（两个对象相同，则它们的hashcode一定相同，hashcode相同，这两个对象不一定相同），若结果是false，即键不相同，则新元素会存放在旧元素的后面，形成链表，如上图的obj1，obj2；若结果为true，那么旧元素被新元素替换（新元素的value会覆盖旧元素的value，但key不覆盖）。

由于hashmap允许值为null，所以不能使用get(key)来判断hashmap中是否存在某个键，因为get(key)返回值为null，不能判定是对应的value为null，还是集合本身就没有这个键值对。

hashmap中如果key是自定义的类时，则必须重写hashcode()和equals()，避免出现equals()返回true而hashcode不相同的情况。

在使用hashmap时还会有两个参数：初始容量和加载因子。初始容量在创建hashmap时生成，默认是16，加载因子默认是0.75，当hashmap中元素数量达到当前容量的0.75时，hashmap会进行扩容（rehash），容量大约扩大一倍。

另外，当链表长度过长（>=8）时，哈希表会转换成红黑树，以此来降低查找时间（红黑树平均查找时间为O(logn)，对链表查找时，只能从头结点开始遍历，时间为O(n)），当长度较小（<=6）时，红黑树又会转换成链表，不使用7是避免红黑树和链表不停地相互转换，增加开销。

05.hashmap与hashtable的区别

hashmap非线程安全，hashtable线程安全。这意味着多个线程可以对hashtable并发，而如果没有正确的同步的话，hashmap不可以进行线程并发。也因为这个原因，hashmap一般比hashtable快。

hashmap可以接受为null的键和值，hashtable不行。

hashmap的迭代器是快速失败的，而hashtable不是。通常情况下，如果有其它线程改变了hashmap的结构（增加、删除元素等），会抛出异常，但是使用迭代器本身的remove()则不会抛出异常。

在没有特殊理由的情况下，建议使用hashmap。

06.set的主要实现类及区别

hashset：基于哈希表，无序，性能最好。

treeset：基于红黑树，按照元素值大小顺序排序，比hashset慢。

linkedhashset：通过链表以哈希表的形式实现，以元素插入集合的顺序排序。

以hashset为例简单解释一下为什么set不允许元素重复：查看源码发现，hashset的构造方法中调用了hashmap的构造方法，且将对象存储在hashmap的key中，由于hashmap的key不允许重复，故hashset元素不允许重复。

07.list的主要实现类及区别

arraylist：基于数组，大小可动态变化，能利用get()，set()直接进行访问。

linkedlist：基于双向链表，因此在插入删除元素时性能比arraylist好，但在查询方面表现较差。

vector：与数组一样，可以通过索引访问元素，且容量大小可动态变化，线程安全。

08.线程安全的集合有哪些

vector：是list的实现类，与数组一样，可以通过索引访问元素，且容量大小可动态变化。

stack：是vector的子类，先进后出。

hashtable：已逐渐被hashmap替代。

09.遍历集合的方式有哪些

for循环遍历；

迭代器iterator遍历；

foreach增强for循环遍历；

enumeration迭代器遍历（基本已被iterator取代）

file

本文由博客一文多发平台 OpenWrite 发布！