java面试/笔试题目之Java常见集合(持续更新中)

boolean add(Object o)  ：向集合中加入一个对象的引用   
void clear()：删除集合中所有的对象，即不再持有这些对象的引用  
boolean isEmpty()    ：判断集合是否为空   
boolean contains(Object o) ： 判断集合中是否持有特定对象的引用   
Iterartor iterator()  ：返回一个Iterator对象，可以用来遍历集合中的元素   
boolean remove(Object o) ：从集合中删除一个对象的引用   
int size()       ：返回集合中元素的数目   
Object[] toArray()    ： 返回一个数组，该数组中包括集合中的所有元素
boolean equals(Object o)：判断值是否相等
int hashCode()： 返回当前集合的hash值，可以作为判断地址是否想相等

Collection接口继承 Iterable<T> 接口，这个接口可以返回一个迭代器，主要有一下三个方法：

List和Set都是继承Collection接口。

List 和 Set 区别

1.Set：集合中的对象不按特定方式排序(针对内存地址来说，即非线性)，并且没有重复对象。它的有些实现类能对集合中的对象按特定方式排序。

不允许重复对象,只允许一个 null 元素，根据equals和hashcode判断，一个对象要存储在set中，必须重写equals和hashcode方法；
无序容器，你无法保证每个元素的存储顺序，TreeSet通过 Comparator 或者 Comparable 维护了一个排序顺序。
Set 接口最流行的几个实现类是 HashSet、LinkedHashSet 以及 TreeSet。最流行的是基于 HashMap 实现的 HashSet；TreeSet 还实现了 SortedSet 接口，因此 TreeSet 是一个根据其 compare() 和 compareTo() 的定义进行排序的有序容器。

2.List：集合中的对象线性方式储存，可以有重复对象，允许按照对象在集合中的索引位置检索对象。有序可重复。

可以允许重复的对象，可以插入多个null元素。
是一个有序容器，保持了每个元素的插入顺序，输出的顺序就是插入的顺序。
常用的实现类有 ArrayList、LinkedList 和 Vector。ArrayList 最为流行，它提供了使用索引的随意访问，而 LinkedList 则对于经常需要从 List 中添加或删除元素的场合更为合适。

Set和hashCode以及equals方法的联系

因为set接口中是不允许存在重复的对象或者值的，所以需要对存入set中的对象或者值进行判断，而hashCode和equals就是用来对这些对象和值进行判断的。

List 和 Map 区别

1.Map：通过键值对进行取值，key-value一一对应的，其中key不可以重复，而value可以重复

区别：

Map用 put(k,v) / get(k)，还可以使用containsKey()/containsValue()来检查其中是否含有某个key/value。
List通过get()方法来一次取出一个元素。使用数字来选择一堆对象中的一个，get(0)...。(add/get)
Collection没有get()方法来取得某个元素。只能通过iterator()遍历元素。

Arraylist 与 LinkedList 区别

1.Arraylist(线程不安全)：

底层是数组(数组在内存中是一块连续的内存，如果插入或删除元素需要移动内存)，可以插入空数据
```
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
```
实现了 RandomAccess 接口，所以支持随机访问
```
private static final int DEFAULT_CAPACITY = 10;
```
数组的默认大小为 10。
插入数据的时候，会先进行扩容校验，添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，也就是旧容量的 1.5 倍。
```
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
```
- 首先进行扩容校验。
- 将插入的值放到尾部，并将 size + 1 。

如果是调用 add(index,e) 在指定位置添加的话：

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //复制，向后移动
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

也是首先扩容校验。

接着对数据进行复制，目的是把 index 位置空出来放本次插入的数据，并将后面的数据向后移动一个位置。

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

扩容最终调用的代码，也是一个数组复制的过程。由此可见 ArrayList 的主要消耗是数组扩容以及在指定位置添加数据，在日常使用时最好是指定大小，尽量减少扩容。更要减少在指定位置插入数据的操作。

删除元素

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)，可以看出 ArrayList 删除元素的代价是非常高的。

由于 ArrayList 是基于动态数组实现的，所以并不是所有的空间都被使用。因此使用了 transient 修饰，可以防止被自动序列化。

transient Object[] elementData;

保存元素的数组 elementData 使用 transient 修饰，该关键字声明数组默认不会被序列化。

 private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        //只序列化了被使用的数据
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

当对象中自定义了 writeObject 和 readObject 方法时，JVM 会调用这两个自定义方法来实现序列化与反序列化。序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理类似。

2.LinkedList(线程不安全)：

底层是基于双向链表实现的，(JDK1.7/8 之后取消了循环，修改为双向链表)，不要求内存是连续的，在当前元素存放下一个或上一个元素的地址。
每次插入都是移动指针，改变引用指向即可，效率较高；

查询的时候使用二分法，利用了双向链表的特性，如果index离链表头比较近，就从节点头部遍历。否则就从节点尾部开始遍历。使用空间（双向链表）来换取时间。node()会以O(n/2)的性能去获取一个结点；如果索引值大于链表大小的一半，那么将从尾结点开始遍历。

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

这样的效率是非常低的，特别是当 index 越接近 size 的中间值时。

区别：

LinkedList 插入，删除都是移动指针效率很高；查找需要进行遍历查询，效率较低。
LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。
ArrayList是可改变大小的数组，而LinkedList是双向链接串列
在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的
ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

ArrayList 与 Vector 区别

1.Vector(线程安全)：

底层也是基于数组实现的，但是add方法的时候使用了synchronized进行同步

public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

这样的话，开销比较大，所以 Vector 是一个同步容器并不是一个并发容器。

区别：

ArrayList和Vector都采用线性连续存储空间，当存储空间不足的时候，Vector 每次扩容请求其大小的 2 倍空间，而 ArrayList 是 1.5 倍。
ArrayList线程不安全，Vector线程安全
Vector可以设置capacityIncrement，而ArrayList不可以，从字面理解就是capacity容量，Increment增加，容量增长的参数。

HashMap 的工作原理及代码实现，什么时候用到红黑树

参考：https://blog.csdn.net/striveb/article/details/84657326

2.Hashtable(线程安全)：

也是实现了Map接口，底层是链表和数组；
继承了Dictionary<K,V>
Hashtable的synchronized是对整张hash表进行锁定即让线程独享整张hash表，在安全同时造成了浪费。当一个线程使用put方法添加元素的时候，其他线程不但不能进行put方法添加，也不能进行get方法获取元素，因为得不到锁。

HashMap 和 Hashtable 的区别：

HashMap线程不安全，Hashtable因为很多地方加了synchronized，所以它是线程安全的；
HashTable使用Enumeration，HashMap 使用Iterator。
HashMap不能保证元素的顺序,HashMap能够将键设为null，也可以将值设为null，但是只有一个键为null，值可以多个为null，当get()方法返回null值时，可能是 HashMap中没有该键，也可能使该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键，而应该用containsKey()方法来判断。Hashtable不能将键和值设为null，否则运行时会报空指针异常错误；
hash值的使用方式不同，Hashtable直接使用对象的hashCode，对table数组的长度直接进行取模；而HashMap计算hash对key的hashcode进行了二次hash，以获得更好的散列值，然后对table数组长度取模；

Hashtable

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

HashMap

static int hash(int h) {
     h ^= (h >>> 20) ^ (h >>> 12);
     return h ^ (h >>> 7) ^ (h >>> 4);
 }

static int indexFor(int h, int length) {
     return h & (length-1);
 }

HashMap没有contains方法，而Hashtabl有contains方法。

//以下是Hashtable的方法
public synchronized boolean contains(Object value)
public synchronized boolean containsKey(Object key)
public boolean containsValue(Object value)

//以下是HashMap中的方法，注意，没有contains方法
public boolean containsKey(Object key)
public boolean containsValue(Object value)

Hashtable中hash默认数组大小是11，增加的方式是old*2+1;HashMap中hash数组大小默认是16，而且一定是2的倍数，HashMap会将其扩充为2的幂次方大小；
Hashtable、HashMap都使用了 Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式。
两者存储规则不一样：
- HashMap的存储规则:优先使用数组存储, 如果出现Hash冲突, 将在数组的该位置拉伸出链表进行存储(在链表的尾部进行添加), 如果链表的长度大于设定值后, 将链表转为红黑树.
- HashTable的存储规则:优先使用数组存储, 存储元素时, 先取出下标上的元素(可能为null), 然后添加到数组元素Entry对象的next属性中(在链表的头部进行添加).出现Hash冲突时, 新元素next属性会指向冲突的元素. 如果没有Hash冲突, 则新元素的next属性就是null。
```
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
```
  参照：https://blog.csdn.net/wangxing233/article/details/79452946

HashSet 和 HashMap 区别：

1.HashSet(线程不安全)：

不允许存储重复元素的集合
基于哈希表实现，支持快速查找，但不支持有序性操作。
使用 Iterator 遍历 HashSet 得到的结果是不确定的。

成员变量：

private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

两个变量：

map ：用于存放最终数据的。
PRESENT ：是所有写入 map 的 value 值。

构造函数：利用了 HashMap 初始化了 map

public HashSet() {
        map = new HashMap<>();
    }
    
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

add方法：
```
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
```
Hashtable将存放的对象当做了 HashMap 的健，value 都是相同的 PRESENT 。由于 HashMap 的 key 是不能重复的，所以每当有重复的值写入到 HashSet 时，value 会被覆盖，但 key 不会受到影响，这样就保证了 HashSet 中只能存放不重复的元素。

HashSet 的原理比较简单，几乎全部借助于 HashMap 来实现的。所以 HashMap 会出现的问题 HashSet 依然不能避免。

区别：

HashMap实现了Map接口，而Hashtable实现Set接口；
HashMap存储键值对,Hashtable仅存储对象;
HashMap调用put（）向map中添加元素;Hashtable调用add（）方法向Set中添加元素;
HashMap比较快，因为是使用唯一的键来获取对象

ConcurrentHashMap 的工作原理及代码实现，如何统计所有的元素个数

参见：https://blog.csdn.net/striveb/article/details/84106768

HashMap 和 ConcurrentHashMap 的区别

HashMap线程不安全，而ConcurrentHashMap线程安全；
https://crossoverjie.top/2018/07/23/java-senior/ConcurrentHashMap/

多线程情况下HashMap死循环的问题

容量大于 总量*负载因子 发生扩容时会出现环形链表从而导致死循环。
并发场景发生扩容，调用 resize() 方法里的 rehash() 时，容易出现环形链表。这样当获取一个不存在的 key 时，计算出的 index 正好是环形链表的下标时就会出现死循环。
这个过程为，先将 A 复制到新的 hash 表中，然后接着复制 B 到链头（A 的前边：B.next=A），本来 B.next=null，到此也就结束了（跟线程二一样的过程），但是，由于线程二扩容的原因，将 B.next=A，所以，这里继续复制A，让 A.next=B，由此，环形链表出现：B.next=A; A.next=B

https://www.cnblogs.com/dongguacai/p/5599100.html

https://blog.csdn.net/linsongbin1/article/details/54708694

介绍一下LinkedHashMap

https://blog.csdn.net/striveb/article/details/84660709

HashMap出现Hash DOS攻击的问题

手写简单的HashMap

看过那些Java集合类的源码

什么是快速失败的故障安全迭代器？

快速失败的Java迭代器可能会引发ConcurrentModifcationException在底层集合迭代过程中被修改。故障安全作为发生在实例中的一个副本迭代是不会抛出任何异常的。快速失败的故障安全范例定义了当遭遇故障时系统是如何反应的。例如，用于失败的快速迭代器ArrayList和用于故障安全的迭代器ConcurrentHashMap。

Iterator和ListIterator的区别

●ListIterator有add()方法，可以向List中添加对象，而Iterator不能。

●ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator就不可以。

●ListIterator可以定位当前的索引位置，nextIndex()和previousIndex()可以实现。Iterator没有此功能。

●都可实现删除对象，但是ListIterator可以实现对象的修改，set()方法可以实现。Iierator仅能遍历，不能修改

什么是CopyOnWriteArrayList，它与ArrayList有何不同？

https://blog.csdn.net/striveb/article/details/86744846

迭代器和枚举之间的区别

如果面试官问这个问题，那么他的意图一定是让你区分Iterator不同于Enumeration的两个方面：

●Iterator允许移除从底层集合的元素。

●Iterator的方法名是标准化的。

https://blog.csdn.net/helongzhong/article/details/52869981

总结:

1. 如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。
2. 如果程序在单线程环境中，或者访问仅仅在一个线程中进行，考虑非同步的类，其效率较高，如果多个线程可能同时操作一个类，应该使用同步的类。
3. 在除需要排序时使用TreeSet,TreeMap外,都应使用HashSet,HashMap,因为他们的效率更高。
4. 要特别注意对哈希表的操作，作为key的对象要正确复写equals和hashCode方法。
5. 容器类仅能持有对象引用（指向对象的指针），而不是将对象信息copy一份至数列某位置。一旦将对象置入容器内，便损失了该对象的型别信息。
6. 尽量返回接口而非实际的类型，如返回List而非ArrayList，这样如果以后需要将ArrayList换成LinkedList时，客户端代码不用改变。这就是针对抽象编程。