java面试题-Java集合相关

时间:2022-08-04 04:18:02

1. ArrayList 和 Vector 的区别

  ArrayList和Vector底层实现原理都是一样得,都是使用数组方式存储数据

  Vector是线程安全的,但是性能比ArrayList要低。

  ArrayList,Vector主要区别为以下几点:

   (1):Vector是线程安全的,源码中有很多的synchronized可以看出,而ArrayList不是。导致Vector效率无法和ArrayList相比;

     (2):ArrayList和Vector都采用线性连续存储空间,当存储空间不足的时候,ArrayList默认增加为原来的50%,Vector默认增加为原来的一倍;

   (3):Vector可以设置capacityIncrement,而ArrayList不可以,从字面理解就是capacity容量,Increment增加,容量增长的参数。

2.说说 ArrayList,Vector, LinkedList 的存储性能和特性

  ArrayList采用的数组形式来保存对象,这种方法将对象放在连续的位置中,所以最大的缺点就是插入和删除的时候比较麻烦,查找比较快;

  Vector使用了sychronized方法(线程安全),所以在性能上比ArrayList要差些.

  LinkedList采用的链表将对象存放在独立的空间中,而且在每个空间中还保存下一个链表的索引。使用双向链表方式存储数据,按序号索引数据需要前向或后向遍历数据,所以索引数据慢,是插入数据时只需要记录前后项即可,所以插入的速度快。

3.快速失败 (fail-fast) 和安全失败 (fail-safe) 的区别是什么?

  1.快速失败

  原理是:

迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个modCount变量。集合在被遍历期间如果内容发生变化,就会改变modCount的值。每当迭代器使用hasNext()或next()遍历下一个元素之前,都会先检查modCount变量是否为expectmodCount值。如果是的话就返回遍历;否则抛出异常,终止遍历。

  查看ArrayList源码,在next方法执行的时候,会执行checkForComodification()方法。

        @SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
        final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}

  这里异常的抛出条件是modCount != expectedModCount这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedModCount值,则异常不会抛出。因此,不能依赖于这个异常是否抛出而进行并发操作,这个异常只建议用于检测并发修改的bug。

  2.安全失败

    采用安全失败机制的集合容器,在遍历时不是直接在集合*问的,而是先复制原有集合内容,在拷贝的集合上进行遍历。

  原理:

  由于迭代时是对原集合的拷贝进行遍历,所以在遍历过程中对原集合所做的修改并不能被迭代器检测到,所以不会触发ConcurrentModificationException,例如CopyOnWriteArrayList。

  缺点:

  基于拷贝内容的优点是避免了ConcurrentModificationException,但同样地,迭代器并不能访问到修改后的内容。即:迭代器遍历的是开始遍历那一刻拿到的集合拷贝,在遍历期间原集合发生的修改迭代器是不知道的。

  场景:

  Java.util.concurrent包下的容器都是安全失败的,可以在多线程下并发使用,并发修改。

快速失败和安全失败都是对迭代器而言的。快速失败:当在迭代一个集合时,如果有另外一个线程在修改这个集合,就会跑出ConcurrentModificationException,java.util下都是快速失败。安全失败:在迭代时候会在集合二层做一个拷贝,所以在修改集合上层元素不会影响下层。在java.util.concurrent包下都是安全失败。

 

4.HashMap 的数据结构

  HashMap的主干类是一个Entry数组(jdk1.7) ,每个Entry都包含有一个键值队(key-value).

  我们可以看一下源码:

static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存储指向下一个Entry的引用,单链表结构
int hash;//对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算 /**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}

  所以,HashMap的整体结果如下

  java面试题-Java集合相关

  简单来说,HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。

5.HashMap 的工作原理

  HashMap基于hashing原理,我们通过put()和get()方法存储和获取对象,当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来存储值对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回对象。

  我们看一下put()源码:

public V put(K key, V value) {
//当key为null,调用putForNullKey方法,保存null与table第一个位置中,这是HashMap允许为null的原因
if (key == null)
return putForNullKey(value);
//计算key的hash值
int hash = hash(key.hashCode()); //计算key hash 值在 table 数组中的位置
int i = indexFor(hash, table.length); //从i出开始迭代 e,找到 key 保存的位置
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
//判断该条链上是否有hash值相同的(key相同)
//若存在相同,则直接覆盖value,返回旧value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value; //旧值 = 新值
e.value = value;
e.recordAccess(this);
return oldValue; //返回旧值
}
}
//修改次数增加1
modCount++;
//将key、value添加至i位置处
addEntry(hash, key, value, i);
return null;
}

  通过源码我们可以清晰看到HashMap保存数据的过程为:首先判断key是否为null,若为null,则直接调用putForNullKey方法。若不为空则先计算key的hash值,然后根据hash值搜索在table数组中的索引位置,如果table数组在该位置处有元素,则通过比较是否存在相同的key,若存在则覆盖原来key的value,否则将该元素保存在链头(最先保存的元素放在链尾)。若table在该处没有元素,则直接保存。

  get()源码: 

public V get(Object key) {
// 若为null,调用getForNullKey方法返回相对应的value
if (key == null)
return getForNullKey();
// 根据该 key 的 hashCode 值计算它的 hash 码
int hash = hash(key.hashCode());
// 取出 table 数组中指定索引处的值
for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
//若搜索的key与查找的key相同,则返回相对应的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

  在这里能够根据key快速的取到value除了和HashMap的数据结构密不可分外,还和Entry有莫大的关系,在前面就提到过,HashMap在存储过程中并没有将key,value分开来存储,而是当做一个整体key-value来处理的,这个整体就是Entry对象。同时value也只相当于key的附属而已。在存储的过程中,系统根据key的hashcode来决定Entry在table数组中的存储位置,在取的过程中同样根据key的hashcode取出相对应的Entry对象。

6.Hashmap 什么时候进行扩容呢?

  这里我们再来复习put的流程:当我们想一个HashMap中添加一对key-value时,系统首先会计算key的hash值,然后根据hash值确认在table中存储的位置。若该位置没有元素,则直接插入。否则迭代该处元素链表并依此比较其key的hash值。如果两个hash值相等且key值相等(e.hash == hash && ((k = e.key) == key || key.equals(k))),则用新的Entry的value覆盖原来节点的value。如果两个hash值相等但key值不等 ,则将该节点插入该链表的链头。具体的实现过程见addEntry方法,如下:

void addEntry(int hash, K key, V value, int bucketIndex) {
//获取bucketIndex处的Entry
Entry<K, V> e = table[bucketIndex];
//将新创建的 Entry 放入 bucketIndex 索引处,并让新的 Entry 指向原来的 Entry
table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
//若HashMap中元素的个数超过极限了,则容量扩大两倍
if (size++ >= threshold)
resize(2 * table.length);
}

  这个方法中有两点需要注意:

      一是链的产生。这是一个非常优雅的设计。系统总是将新的Entry对象添加到bucketIndex处。如果bucketIndex处已经有了对象,那么新添加的Entry对象将指向原有的Entry对象,形成一条Entry链,但是若bucketIndex处没有Entry对象,也就是e==null,那么新添加的Entry对象指向null,也就不会产生Entry链了。

      二、扩容问题。

随着HashMap中元素的数量越来越多,发生碰撞的概率就越来越大,所产生的链表长度就会越来越长,这样势必会影响HashMap的速度,为了保证HashMap的效率,系统必须要在某个临界点进行扩容处理。该临界点在当HashMap中元素的数量等于table数组长度*加载因子。但是扩容是一个非常耗时的过程,因为它需要重新计算这些数据在新table数组中的位置并进行复制处理。所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。

 7.HashSet怎样保证元素不重复

  都知道HashSet中不能存放重复的元素,有时候可以用来做去重操作。但是其内部是怎么保证元素不重复的呢?

  打开HashSet源码,发现其内部维护一个HashMap:

public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L; private transient HashMap<E,Object> map; private static final Object PRESENT = new Object(); public HashSet() {
map = new HashMap<>();
}
  ...
}

  HashSet的构造方法其实就是在内部实例化了一个HashMap对象,其中还会看到一个static final的PRESENT变量;

  想知道为什么HashSet不能存放重复对象,那么第一步看看它的add方法进行的判重,代码如下

    public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

  其实看add()方法,这时候答案已经出来了:HashMap的key是不能重复的,而这里HashSet的元素又是作为了map的key,当然也不能重复了

  顺便看一下HashMap里面又是怎么保证key不重复的,代码如下:

public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
} modCount++;
addEntry(hash, key, value, i);
return null;
}

  其中最关键的一句: 

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 

  调用了对象的hashCode和equals方法进行判断,所以又得到一个结论:若要将对象存放到HashSet中并保证对象不重复,应根据实际情况将对象的hashCode方法和equals方法进行重写