柒夭日志：Java集合框架

图文详解了 40 多道 Java 集合框架面试高频题，目标是成功上岸，从现在开始努力，加油！！！（手动狗头），本文转载链接，并且在原文的基础上增加了一些自己的理解和思考且在最后加上了一个 Queue 部分的内容，希望能对各位读者有所帮助！！！

引言

1. 说说有哪些常见集合，并且之间有什么区别？

集合相关类和接口都在 java.util 中，主要分为 3 种，分别是：List（列表）、Map（映射）、Set（集合） 。

Java集合主要关系

其中 Collection 是集合 List、 Set、Queue 的父接口，它主要有三个子接口：

• List： 存储的元素有序，可以重复，有索引
• Set： 存储的元素无序，不可以重复，没有索引
• Queue： 队列集合，其存储的元素先入先出，后入后出

Map 是另外的接口，其是键值对映射结构的集合，这个是面试的重点内容，这里会着重讲这一部分的内容。

List

一般来说，List 可以问的东西可能不多，但是不排除面试官剑走偏锋，所以这里还是讲一讲大概内容。

2. ArrayList和LinkedList有什么区别？

• ArrayList 是基于数组实现的
• LinkedList 是基于双链表实现的

• ArrayList基于数组实现，get(int index)可以直接通过数组下标获取，时间复杂度是O(1)；LinkedList基于链表实现，get(int index)需要遍历链表，时间复杂度是O(n)；当然，get(E element)这种查找，两种集合都需要遍历，时间复杂度都是O(n)。

• ArrayList增删如果是数组末尾的位置，直接插入或者删除就可以了，但是如果插入中间的位置，就需要把插入位置后的元素都向前或者向后移动，甚至还有可能触发扩容；双向链表的插入和删除只需要改变前驱节点、后继节点和插入节点的指向就行了，不需要移动元素。

注意，这个地方可能会出陷阱，LinkedList更利于增删更多是体现在平均步长上，不是体现在时间复杂度上，二者增删的时间复杂度都是O(n)

• ArrayList基于数组，所以它可以根据下标查找，支持随机访问，当然，它也实现了RandmoAccess 接口，这个接口只是用来标识是否支持随机访问。

• 因为 ArrayList 是预先定义好数组的，所以其有一些内存空间可能没有使用到，所以存在着一定程度上的空间浪费
• LinkedList 的每个节点都需要存储前驱以及后继，所以每个节点可能占用更多的内容和空间，以下是关于这个链表的一个简单示例：

public Class Node{
    private Node pre;
    private T data;
    private Node next;
}

3.ArrayList的扩容机制了解吗？

ArrayList是基于数组的集合，数组的容量是在定义的时候确定的，如果数组满了，再插入，就会数组溢出。所以在插入时候，会先检查是否需要扩容，如果当前容量+1超过数组长度，就会进行扩容。

ArrayList的扩容是先创建一个原先容量 1.5倍 的新数组，然后再将原数组的值遍历拷贝过去。

4.ArrayList怎么序列化的知道吗？为什么用transient修饰数组？

ArrayList的序列化不太一样，它使用 transient 修饰存储元素的 elementData 的数组，transient 关键字的作用是为了让被修饰的成员属性不被序列化。

这里可能有几个疑问哈，看我详细道来：

（1）为什么 ArrayList 不直接序列化元素呢？

出于效率考虑，数组可能长度为 100，但是实际却用了 50，剩下的 50 不用其实不用进行序列化，这样的的可以提高序列化和反序列化的效率，还可以节省内存空间。

（2）那 ArrayList 怎么序列化呢？

ArrayList 通过两个方法 readObject、writeObject自定义序列化和反序列化策略。实际上直接使用 ObjectOutputStream 和 ObjectInputStream 来进行序列化和反序列化。

5.快速失败(fail-fast)和安全失败(fail-safe)了解吗？

快速失败（fail-fast） ：快速失败是 Java 集合的一种错误检测机制

• 在用迭代器遍历一个集合对象时，如果线程A遍历过程中，线程B对集合对象的内容进行了修改（增加、删除、修改），则会抛出 Concurrent Modification Exception。
• 原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount ****变量。集合在被遍历期间如果内容发生变化，就会改变 modCount 的值。每当迭代器使用 hashNext()/next() 遍历下一个元素之前，都会检测 modCount 变量是否为 expectedmodCount 值，是的话就返回遍历；否则抛出异常，终止遍历。
• 注意：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改 modCount 值刚好又设置为了expectedmodCount 值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的 bug。
• 场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），比如 ArrayList 类。

安全失败（fail-safe） : 其是 Java 集合的另一种错误检测机制

• 采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。
• 原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发 Concurrent Modification Exception。
• 缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。
• 场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改，比如CopyOnWriteArrayList类。

6.有哪几种实现ArrayList线程安全的方法？

fail-fast是一种可能触发的机制，实际上，ArrayList的线程安全仍然没有保证，一般，保证ArrayList的线程安全可以通过这些方案：

• 使用 Vector 代替 ArrayList，虽然可以，但是不推荐，不推荐的原因如下：

Vector 是一个历史遗留类，它与 ArrayList 一样，都是基于数组实现的，不同的是 Vector 支持线程同步，即同一时刻只允许一个线程对于 Vector 进行写操作（增删改） ，以保证多线程环境下的数据一致性，但是需要频繁对 Vector 示例进行加锁和释放锁的操作，因此导致 Vector 的读写效率从整体上来说，远远比不是 ArrayList，所以不推荐使用。

• 使用 Collections.synchronizedList 包装 ArrayList，然后操作包装后的 list。
• 使用 CopyOnWriteArrayList 代替 ArrayList。
• 在使用 ArrayList 时，应用程序通过同步机制去控制 ArrayList 的读写。

7.CopyOnWriteArrayList了解多少？

CopyOnWriteArrayList就是线程安全版本的ArrayList。

它的名字叫 CopyOnWrite ——写时复制，已经明示了它的原理。

CopyOnWriteArrayList 采用了一种读写分离的并发策略。CopyOnWriteArrayList 容器允许并发读，读操作是无锁的，性能较高。至于写操作，比如向容器中添加一个元素，则首先将当前容器复制一份，然后在新副本上执行写操作，结束之后再将原容器的引用指向新容器。

8.Arraylist 和 Vector 的区别

9.怎么在遍历 ArrayList 时移除一个元素？

foreach删除会导致快速失败问题，可以使用迭代器的 remove() 方法。

Iterator itr = list.iterator();
while(itr.hasNext()) {
    if(itr.next().equals("jay") {
        itr.remove();
    }
}

Map

在Map中，毫无疑问最重要的就是HashMap，这个基本是面试中的必考点，所以需要重点准备 ！！！！

10.能说一下HashMap的数据结构吗？

这个问题需要分成两个阶段来进行回答，分别是 JDK 1.8 以前和 JDK 1.8 之后。

JDK 1.8 以前，采用的数据结构是 数组 + 链表 ， 但是 JDK1.8 及以前的版本还有人在用？应该没有吧 .........

接下来来盘一下 JDK 1.8 中 HashMap 的数据结构：

其采用的数据结构是 数组 + 链表 + 红黑树 。

数据结构如下图所示：

其中，桶数组是用来存储数据元素，链表是用来解决冲突，红黑树是为了提高查询的效率。

• 数据元素通过映射关系，也就是散列函数，映射到桶数组对应索引的位置
• 如果发生冲突，从冲突的位置拉一个链表，插入冲突的元素
• 如果链表长度>8&数组大小>=64，链表转为红黑树
• 如果红黑树节点个数>> 16))
• 判断tab是否位空或者长度为0，如果返回的是 true ，则进行扩容操作。

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

• 根据哈希值计算下标，如果对应小标正好没有存放数据，则直接插入即可否则需要覆盖。

tab[i = (n - 1) & hash])

• 判断tab[i]是否为树节点，如果不是树节点的话，将向链表中插入数据，如果是树节点，则向树中插入节点。
• 如果链表中插入节点的时候，链表长度大于等于8，则需要把链表转换为红黑树。

treeifyBin(tab, hash);

• 最后所有元素处理完成后，判断其是否超过阈值：threshold， 如果超过则扩容。

14.HashMap怎么查找元素的呢？

首先来看一下流程图：



HashMap的查找就简单很多：

• 使用扰动函数，获取新的哈希值
• 计算数组下标，获取节点
• 当前节点和key匹配，直接返回
• 否则，当前节点是否为树节点，查找红黑树
• 否则，遍历链表查找

15.HashMap的哈希/扰动函数是怎么设计的?

HashMap的哈希函数是先拿到 key 的 hashcode，是一个32位的int类型的数值，然后让hashcode的高16位和低16位进行异或操作。

static final int hash(Object key) {
    int h;
    // key的hashCode和key的hashCode右移16位做异或运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这种设计方式其目标就是为了降低哈希碰撞的概率。

16.为什么哈希/扰动函数能降hash碰撞？

因为 key.hashCode() 函数调用的是 key 键值类型自带的哈希函数，返回 int 型散列值。int 值范围为

-2147483648~2147483647， 这样加起来就大概有 40 亿个映射空间。

这里提一我看到的腾讯的面试题，用1kb的空间，如何对 40 亿个 QQ 号怎么实现去重，这里用到的是位运算加上哈希的知识点，感兴趣的同学可以自行百度了解一下

只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。

假如 HashMap 数组的初始大小才 16，就需要用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。

源码中模运算就是将散列值和数组长度 - 1 作一个与运算（&） 的操作，位运算比 （取余 %） 运算更快 。

bucketIndex = indexFor(hash, table.length);

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

顺便说一下，这也正好解释了为什么 HashMap 的数组长度要取 2 的整数幂。因为这样（数组长度 - 1）正好相当于一个 “低位掩码” 。与 ****操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度 16 为例，16-1=15。2 进制表示是0000 0000 0000 0000 0000 0000 0000 1111。和某个散列值做 与 操作如下，结果就是截取了最低的四位值。



这样会更加快捷一些，但是新的问题来了，就算散列值的分布再松散，如果要是只取最后几位的值，其产生的碰撞也会很严重。如果散列本身处理的不是很好，在分布上面就会产生一个等差数列的漏洞，如果正好让最后几个低位呈现规律性重复的话，那就更加难以处理了。

这个时候 扰动函数 的价值就体现出来了，我们来看一下扰动函数的示意图：



这里采用了向右移动 16 位的方法，正好是 32 bit 的一半，然后让自己的高半区和低半区进行异或，就是为了混合原始哈希码的高位以及低位，借此来加大低位的随机性，从而降低哈希冲突。而且混合后的低位并不是完全舍弃了高位的东西，其掺杂了高位的部分特征，这样高位本身的信息变相地也保留了一些下来。

17.为什么HashMap的容量是2的幂次方呢？

这里主要有两个原因：

• 方便进行哈希取余

将元素放到 table 数组的上面，然后利用 hash 值 取余（%） 数组的大小来确定位置，然而 HashMap 采用了另一种位运算方法，即 hash 值 与（&） 数组大小 - 1 的方法，这两种方法最终实现的效果是一致的，其原因就在于 HashMap 的容量，HashMap 的大小是 2 的倍数，2的倍数就意味着该数的二进制位数只有一位是 1，而该数-1就可以得到二进制位上1变成0，后面的0变成1，再通过&运算，就可以得到和 取余（%） 一样的效果，并且效率要高得多。

当 HashMap 的容量是 2 的 n 次幂的时候，（n - 1）的 2 进制就是 1111111 xxx 111 的形式，这样与添加的元素的 hash 值进行位运算的时候，就可以得到充分的散列，使得添加的元素均匀地分布在 HashMap 的每一个位置上，从而减少 Hash 碰撞。

• 扩容机制

第二原因就在于扩容机制上面了，HashMap 的扩容机制是扩容后的大小是原来的 2 倍，即其扩容后的大小是 2 的倍数，然后将已经产生哈希碰撞的元素转移到新的 table 中去。

这个时候我们可以看一下 HashMap 的扩容方法 putVal 的源码：

if （++size > threadshold）{
	resize()
}
afterNodeInsertion(evict)
return null;

这里我们可以看到，当你的添加进来后的 HashMap 的大小大于 负载因子 * HashMap （这里指threadshold ）的时候就会产生扩容。

18.如果初始化HashMap，传一个17的值new HashMap，它会怎么处理？

简单来说，就是初始化时，传的不是2的倍数时，HashMap会向上寻找离得最近的2的倍数，所以如果传入17的话，HashMap的实际容量就是32。

我们来看看一下 HashMap 的初始化的源码：

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity  MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor >> Integer.numberOfLeadingZeros(cap - 1);
    return (n = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

• 同时，tableSizeFor 这个方法也要寻找比初始值大的，且最小的二进制数值，比如我传入了 33 ,其大于 32，所以我往上继续寻找，找到了 64，其就是 HashMap 的初始化容量了。

static final int tableSizeFor(int cap) {
 int n = cap - 1;
 n |= n >>> 1;
 n |= n >>> 2;
 n |= n >>> 4;
 n |= n >>> 8;
 n |= n >>> 16;
 return (n = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

• MAXIMUM_CAPACITY = 1 = buckets.length * LOAD_FACTOR) {
  resize();
  }
  // 将元素插入对应的桶数组
  putVal(key, value, buckets);
  }

  /**
  * 扩容方法
  */
  private void resize() {
  //创建一个原本容量两倍的桶数组
  Node[] newBuckets = new Node[buckets.length * 2];
  //将当前元素重新散列到新的桶数组
  rehash(newBuckets);
  //将数组进行拷贝
  buckets = newBuckets;
  }

  /**
  * 重新散列当前元素
  *
  * @param newBuckets 扩容后的桶数组，这里获取原本桶数组的大小，进行再哈希取余
  */
  private void rehash(Node[] newBuckets) {
  //map大小重新计算
  size = 0;
  //将旧的桶数组的元素全部刷到新的桶数组里
  for (int i = 0; i < buckets.length; i++) {
  //数组元素为空，直接跳过
  if (buckets[i] == null) {
  continue;
  }
  Node node = buckets[i];
  while (node != null) {
  //将元素放入新数组
  putVal(node.key, node.value, newBuckets);
  node = node.next;
  }
  }
  }

  /**
  * 将元素存入指定的node数组
  *
  * @param key 存储的 key
  * @param value 存储的 value
  * @param table 存储的桶数组
  */
  private void putVal(K key, V value, Node[] table) {
  //获取位置
  int index = getIndex(key, table.length);
  Node node = table[index];
  //插入的位置为空
  if (node == null) {
  table[index] = new Node(key, value);
  size++;
  return;
  }
  //插入位置不为空，说明发生冲突，使用链地址法,遍历链表
  while (node != null) {
  //如果key相同，就覆盖掉
  if ((node.key.hashCode() == key.hashCode()) && ((node.key == key) || node.key.equals(key))) {
  node.value = value;
  return;
  }
  node = node.next;
  }
  //当前key不在链表中，插入链表头部
  Node newNode = new Node(key, value, table[index]);
  table[index] = newNode;
  size++;
  }

  /**
  * 获取元素
  *
  * @param key
  * @return
  */
  public V get(K key) {
  //获取key对应的地址
  int index = getIndex(key, buckets.length);
  if (buckets[index] == null) {
  return null;
  }
  Node node = buckets[index];
  //查找链表，当链表节点不为空的时候，继续查找
  while (node != null) {
  if ((node.key.hashCode() == key.hashCode()) && (node.key == key || node.key.equals(key))) {
  return node.value;
  }
  node = node.next;
  }
  return null;
  }
  }
  

  26.HashMap 是线程安全的吗？多线程下会有什么问题？

  HashMap 并不是线程安全的，其在多线程的环境下可能会产生下列问题：

  • put 和 get 并发时，可能导致 get 为 null。线程 1 执⾏ put 时，因为元素个数超出 threshold⽽导致rehash，线程 2 此时执⾏ get，有可能导致这个问题，这个问题在 JDK 1.7 和 JDK 1.8 中都存在。
  • 多线程的 put 可能导致元素的丢失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK 1.7 和 JDK 1.8 中都存在。
  • 多线程下扩容死循环。JDK1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8 使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。

  27.有什么办法能解决HashMap线程不安全的问题呢？

  Java 中有Collections.synchronizedMap、ConcurrentHashMap以及 HashTable 可以实现线程安全的 Map。

  • Collections.synchronizedMap 是使用 Collections 集合工具的内部类，通过传入 Map 封装出一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现；
  • ConcurrentHashMap 在jdk1.7中使用分段锁，在jdk1.8中使用CAS+synchronized（双重锁机制）。
  • HashTable 是直接在操作方法上加 synchronized 关键字，锁住整个table数组，粒度比较大；

  28.HashMap和HashTable的区别？

  HashMap和Hashtable都实现了Map接口。

• HashMap可以接受为null的key和value，key为null的键值对放在下标为0的头结点的链表中，而Hashtable则不行。
• HashMap是非线程安全的，HashTable是线程安全的。Jdk1.5提供了ConcurrentHashMap，它是HashTable的替代。
• Hashtable很多方法是同步方法，在单线程环境下它比HashMap要慢。
• 哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。

29.能具体说一下ConcurrentHashmap的实现吗？

ConcurrentHashmap线程安全在jdk1.7版本是基于分段锁实现，在jdk1.8是基于CAS+synchronized 实现。

JDK 1.7 ：分段锁实现

从结构上说，1.7版本的ConcurrentHashMap采用分段锁机制，里面包含一个Segment数组，Segment继承于ReentrantLock，Segment则包含HashEntry的数组，HashEntry本身就是一个链表的结构，具有保存key、value的能力能指向下一个节点的指针。

实际上就是相当于每个Segment都是一个HashMap，默认的Segment长度是16，也就是支持16个线程的并发写，Segment之间相互不会受到影响。



JDK1.7 ConcurrentHashMap示意图

put流程

整个流程和HashMap非常类似，只不过是先定位到具体的Segment，然后通过ReentrantLock去操作而已，后面的流程，就和HashMap基本上是一样的。

• 计算hash，定位到segment，segment如果是空就先初始化
• 使用ReentrantLock加锁，如果获取锁失败则尝试自旋，自旋超过次数就阻塞获取，保证一定获取锁成功
• 遍历HashEntry，就是和HashMap一样，数组中key和hash一样就直接替换，不存在就再插入链表，链表同样操作



****get流程

get也很简单，key通过hash定位到segment，再遍历链表定位到具体的元素上，需要注意的是value是volatile的，所以get是不需要加锁的。

JDK 1.8：CAS + Synchronized 双重自检锁

jdk1.8实现线程安全不是在数据结构上下功夫，它的数据结构和HashMap是一样的，数组+链表+红黑树。它实现线程安全的关键点在于put流程。

put流程

• 首先计算hash，遍历node数组，如果node是空的话，就通过CAS+自旋的方式初始化

tab = initTable();

node数组初始化：

private final Node[] initTable() {
    Node[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        //如果正在初始化或者扩容
        if ((sc = sizeCtl)  0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node[] nt = (Node[])new Node[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

• 如果当前数组位置是空则直接通过CAS自旋写入数据

static final  boolean casTabAt(Node[] tab, int i,

                                    Node c, Node v) {

    return U.compareAndSwapObject(tab, ((long)i >> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||

                sc == rs + MAX_RESIZERS || transferIndex