（备战春招，每天进步亿点点）常见面试题总结——Java集合

备战春招，每天进步亿点点，大家好，我是杜晓帅~😁，今天总结的是Java集合篇

文章目录

• • 常见的集合有哪些？
  • Arraylist与 LinkedList 异同点？
  • 说一下ArrayList的扩容机制？
  • HashMap的底层数据结构是什么？
  • 解决hash冲突的办法有哪些？HashMap用的哪种？
  • HashMap 的put方法流程？
  • HashMap 的扩容方式？
  • HashMap为什么线程不安全？
  • ConcurrentHashMap 的实现原理是什么？
  • ConcurrentHashMap 和Hashtable的效率哪个更高？为什么？
  • 说一下Hashtable的锁机制 ?
  • JDK1.7与JDK1.8 中ConcurrentHashMap 的区别？

常见的集合有哪些？

Java集合类主要由两个根接口Collection和Map派生出来的，Collection派生出了三个子接口：List、Set、Queue（Java5新增的队列），因此Java集合大致也可分成List、Set、Queue、Map四种接口体系。
如下图所示：

List： 代表了有序可重复集合，可直接根据元素的索引来访问。
Set： 代表无序不可重复集合，只能根据元素本身来访问。
Queue： 队列集合。
Map： 代表的是存储key-value对的集合，可根据元素的key来访问value。

Arraylist与 LinkedList 异同点？

• 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
• 底层数据结构： Arraylist 底层使用的是Object数组；LinkedList 底层使用的是双向循环链表数据结构；
• 插入和删除是否受元素位置的影响： ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。
• 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而ArrayList 实现了RandmoAccess 接口，所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
• 内存空间占用： ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

说一下ArrayList的扩容机制？

ArrayList扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。默认情况下，新的容量会是原容量的1.5倍。
以JDK1.8为例说明，执行add方法之前会调用ensureCapacityInternal方法（调用ensureCapacityInternal方法：1.如果没初始化则进行初始化；2.校验添加元素后是否需要扩容。），如果需要扩容则调用grow方法进行扩容

public boolean add(E e) {    //判断是否可以容纳e，若能，则直接添加在末尾；若不能，则进行扩容，然后再把e添加在末尾    ensureCapacityInternal(size + 1);  // Increments modCount!!    //将e添加到数组末尾    elementData[size++] = e;    return true;    }// 每次在add()一个元素时，arraylist都需要对这个list的容量进行一个判断。通过ensureCapacityInternal()方法确保当前ArrayList维护的数组具有存储新元素的能力，经过处理之后将元素存储在数组elementData的尾部private void ensureCapacityInternal(int minCapacity) {      ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) { //如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {     return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity;    }      private void ensureExplicitCapacity(int minCapacity) { modCount++; // 若ArrayList已有的存储能力满足最低存储要求，则返回add直接添加元素；如果最低要求的存储能力>ArrayList已有的存储能力，这就表示ArrayList的存储能力不足，因此需要调用 grow();方法进行扩容 if (minCapacity - elementData.length > 0)     grow(minCapacity);    }private void grow(int minCapacity) { // 获取elementData数组的内存空间长度 int oldCapacity = elementData.length; // 扩容至原来的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); //校验容量是否够 if (newCapacity - minCapacity < 0)     newCapacity = minCapacity; //若预设值大于默认的最大值，检查是否溢出 if (newCapacity - MAX_ARRAY_SIZE > 0)     newCapacity = hugeCapacity(minCapacity); // 调用Arrays.copyOf方法将elementData数组指向新的内存空间  //并将elementData的数据复制到新的内存空间 elementData = Arrays.copyOf(elementData, newCapacity);    }

grow（）的过程如下图所示：

HashMap的底层数据结构是什么？

在JDK1.7中，由“数组+链表”组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。
在JDK1.8中，由“数组+链表+红黑树”组成。当链表过长，则会严重影响 HashMap 的性能，红黑树搜索时间复杂度是 O(logn)，而链表是糟糕的 O(n)。因此，JDK1.8 对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：

• 当链表超过 8 且数据总量超过 64 才会转红黑树。
• 将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。
  

解决hash冲突的办法有哪些？HashMap用的哪种？

解决Hash冲突方法有:开放定址法、再哈希法、链地址法（拉链法）、建立公共溢出区。HashMap中采用的是 链地址法 。

• 开放定址法也称为再散列法，基本思想就是，如果p=H(key)出现冲突时，则以p为基础，再次hash，p1=H§,如果p1再次出现冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地址pi。 因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次hash，所以只能在删除的节点上做标记，而不能真正删除节点。
• 再哈希法(双重散列，多重散列)，提供多个不同的hash函数，当R1=H1(key1)发生冲突时，再计算R2=H2(key1)，直到没有冲突为止。 这样做虽然不易产生堆集，但增加了计算的时间。
• 链地址法(拉链法)，将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。
• 建立公共溢出区，将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

HashMap 的put方法流程？

简要流程如下：

1. 首先根据 key 的值计算 hash 值，找到该元素在数组中存储的下标；
2. 如果数组是空的，则调用 resize 进行初始化；
3. 如果没有哈希冲突直接放在对应的数组下标里；
4. 如果冲突了，且 key 已经存在，就覆盖掉 value；
5. 如果冲突后，发现该节点是红黑树，就将这个节点挂在树上；
6. 如果冲突后是链表，判断该链表是否大于 8 ，如果大于 8 并且数组容量小于 64，就进行扩容；如果链表节点大于 8 并且数组的容量大于 64，则将这个结构转换为红黑树；否则，链表插入键值对，若 key 存在，就覆盖掉 value。

HashMap 的扩容方式？

HashMap 在容量超过负载因子所定义的容量之后，就会扩容。Java 里的数组是无法自动扩容的，方法是将 HashMap 的大小扩大为原来数组的两倍，并将原来的对象放入新的数组中。

那扩容的具体步骤是什么？让我们看看源码。

JDK1.7 的代码：

void resize(int newCapacity) {   //传入新的容量 Entry[] oldTable = table;    //引用扩容前的Entry数组 int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了     threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了     return; } Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组 transfer(newTable);    //！！将数据转移到新的Entry数组里 table = newTable;      //HashMap的table属性引用新的Entry数组 threshold = (int)(newCapacity * loadFactor);//修改阈值    }

这里就是使用一个容量更大的数组来代替已有的容量小的数组，transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

void transfer(Entry[] newTable) { Entry[] src = table;     //src引用了旧的Entry数组 int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组     Entry<K,V> e = src[j];      //取得旧Entry数组的每个元素     if (e != null) {  src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）  do {      Entry<K,V> next = e.next;      int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置      e.next = newTable[i]; //标记[1]      newTable[i] = e;      //将元素放在数组上      e = next;      //访问下一个Entry链上的元素  } while (e != null);     } }    }

newTable[i] 的引用赋给了 e.next ，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到 Entry 链的尾部(如果发生了 hash 冲突的话）。

HashMap为什么线程不安全？

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

详细分析可参考这篇文章：HashMap为什么线程不安全？

ConcurrentHashMap 的实现原理是什么？

ConcurrentHashMap 在 JDK1.7 和 JDK1.8 的实现方式是不同的。
JDK1.7：

JDK1.7中的ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成，即ConcurrentHashMap 把哈希桶切分成小数组（Segment ），每个小数组有 n 个 HashEntry 组成。

其中，Segment 继承了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色；HashEntry 用于存储键值对数据。

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问，能够实现真正的并发访问。

JDK1.8：
在数据结构上， JDK1.8 中的ConcurrentHashMap 选择了与 HashMap 相同的数组+链表+红黑树结构；在锁的实现上，抛弃了原有的 Segment 分段锁，采用CAS + synchronized实现更加低粒度的锁。

将锁的级别控制在了更细粒度的哈希桶元素级别，也就是说只需要锁住这个链表头结点（红黑树的根节点），就不会影响其他的哈希桶元素的读写，大大提高了并发度。

如需深入了解ConcurrentHashMap，请参考文章：https://mp.weixin.qq.com/s?__biz=MzkyMTI3Mjc2MQ==&mid=2247485909&idx=1&sn=d9c672eebb090866a72f99f3d8032e76&source=41#wechat_redirect

ConcurrentHashMap 和Hashtable的效率哪个更高？为什么？

ConcurrentHashMap 的效率要高于Hashtable，因为Hashtable给整个哈希表加了一把大锁从而实现线程安全。而ConcurrentHashMap 的锁粒度更低，在JDK1.7中采用分段锁实现线程安全，在JDK1.8 中采用CAS + synchronized实现线程安全。

说一下Hashtable的锁机制 ?

Hashtable是使用Synchronized来实现线程安全的，给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞等待需要的锁被释放，在竞争激烈的多线程场景中性能就会非常差！

JDK1.7与JDK1.8 中ConcurrentHashMap 的区别？

• 数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
• 保证线程安全机制：JDK1.7采用Segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8 采用CAS+Synchronized保证线程安全。
• 锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。
• 链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。
• 查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。

素彩网