java集合面试题

1. 什么是集合

1. 集合就是一个放数据的容器，准确的说是放数据对象引用的容器
2. 集合类存放的都是对象的引用，而不是对象的本身
3. 集合类型主要有3种：set(集）、list(列表）和map(映射)。

2 常用的集合类有哪些？

• Map接口和Collection接口是所有集合框架的父接口：
• Collection接口的子接口包括：Set接口和List接口

1. Map接口的实现类主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等
2. Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等
3. List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等

3.集合框架底层数据结构

List
* Arraylist： Object数组
* Vector： Object数组
* LinkedList： 双向循环链表
Set
* HashSet（无序，唯一）：基于 HashMap 实现的，底层采用 HashMap 来保存元素
* LinkedHashSet： LinkedHashSet 继承与 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的。
* TreeSet（有序，唯一）： 红黑树(自平衡的排序二叉树。)
Map
HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是
主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8以后在解决哈希冲突时有了较
大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散
列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加
了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的
操作，实现了访问顺序相关逻辑。
HashTable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突
而存在的
TreeMap： 红黑树（自平衡的排序二叉树）

 4.哪些集合类是线程安全的？

　　Vector：就比Arraylist多了个 synchronized （线程安全），因为效率较低，现在已经不太建议使用。
　　hashTable：就比hashMap多了个synchronized (线程安全)，不建议使用。
　　ConcurrentHashMap：是Java5中支持高并发、高吞吐量的线程安全HashMap实现。它由Segment数组结构和HashEntry数组结构组成。

5. 快速失败机制 “fail-fast”？

　　是java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生
fail-fast 机制。
例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时
候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这
个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。
原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集
合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()
遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍
历；否则抛出异常，终止遍历。

 6.遍历一个 List 有哪些不同的方式？每种方法的实现原理是什么？Java 中 List遍历的最佳实践是什么？

遍历方式有以下几种：

1. for 循环遍历，基于计数器。在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读取到最后一个元素后停止。
2. 迭代器遍历，Iterator。Iterator 是面向对象的一个设计模式，目的是屏蔽不同数据集合的特点，统一遍历集合的接口。Java 在 Collections 中支持了 Iterator 模式。
3. foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现，使用时不需要显式声明Iterator 或计数器。优点是代码简洁，不易出错；缺点是只能做简单的遍历，不能在遍历过程中操作数据集合，例如删除、替换。

最佳实践：Java Collections 框架中提供了一个 RandomAccess 接口，用来标记 List 实现是否支持 Random Access。

如果一个数据集合实现了该接口，就意味着它支持 Random Access，按位置读取元素的平均时间复杂度为 O(1)，如ArrayList。

如果没有实现该接口，表示不支持 Random Access，如LinkedList。
推荐的做法就是，支持 Random Access 的列表可用 for 循环遍历，否则建议用 Iterator 或foreach 遍历。

7.说一下 ArrayList 的优缺点

ArrayList的优点如下：

• ArrayList 底层以数组实现，是一种随机访问模式。ArrayList 实现了 RandomAccess 接口，因此查找的时候非常快。
• ArrayList 在顺序添加一个元素的时候非常方便。

ArrayList 的缺点如下：

• 删除元素的时候，需要做一次元素复制操作。如果要复制的元素很多，那么就会比较耗费性能。
• 插入元素的时候，也需要做一次元素复制操作，缺点同上。

8.ArrayList 和 LinkedList 的区别是什么？

1. 数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。
2. 随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。
3. 增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为ArrayList 增删操作要影响数组内的其他数据的下标。
4. 内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。
5. 线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；

综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。

9.ArrayList 和 Vector 的区别是什么？

1. 线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而 ArrayList 是非线程安全的。
2. 性能：ArrayList 在性能方面要优于 Vector。
3. 扩容：ArrayList 和 Vector 都会根据实际的需要动态的调整容量，只不过在 Vector 扩容每次会增加 1 倍，而 ArrayList 只会增加 50%。

10.List 和 Set 的区别

• List 特点：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个null元素，元素都有索引。
• Set 特点：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。
• 另外 List 支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。

Set和List对比

• Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
• List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变

 11.说一下 HashSet 的实现原理？

　　HashSet 是基于 HashMap 实现的，HashSet的值存放于HashMap的key上，HashMap的value统一为present，因此 HashSet 的实现比较简单，

相关 HashSet 的操作，基本上都是直接调用底层HashMap 的相关方法来完成，HashSet 不允许重复的值。

12.HashSet如何检查重复？HashSet是如何保证数据不可重复的？

1. 向HashSet 中add ()元素时，判断元素是否存在的依据，不仅要比较hash值，同时还要结合equles 方法比较。
2. HashSet 中的add ()方法会使用HashMap 的put()方法。
3. HashMap 的 key 是唯一的，由源码可以看出 HashSet 添加进去的值就是作为HashMap 的key，并且在HashMap中如果K/V相同时，会用新的V覆盖掉旧的V，然后返回旧的V。所以不会重复（HashMap 比较key是否相等是先比较hashcode 再比较equals ）。

　　hashCode（）与equals（）的相关规定:

1. 如果两个对象相等，则hashcode一定也是相同的
2. 两个对象相等,对两个equals方法返回true
3. 两个对象有相同的hashcode值，它们也不一定是相等的

　　综上，equals方法被覆盖过，则hashCode方法也必须被覆盖hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个

对象无论如何都不会相等（即使这两个对象指向相同的数据）。

 13.说一下HashMap的实现原理？

• HashMap概述： HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
• HashMap的数据结构： 在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
• HashMap 基于 Hash 算法实现:,当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标存储时，如果出现hash值相同的key，此时有两种情况。

　　　　(1)如果key相同，则覆盖原始值；
　　　　(2)如果key不同（出现冲突），则将当前的key-value放入链表中获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。

14.HashMap在JDK1.7和JDK1.8中有哪些不同？HashMap的底层实现

JDK1.8主要解决或优化了一下问题：

1. resize 扩容优化
2. 引入了红黑树，目的是避免单条链表过长而影响查询效率，红黑树算法请参考
3. 解决了多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题。
• 存储结构上：1.7是数组+链表，1.8是数组+链表+红黑树
• 初始化方式：1.7有单独的初始化函数inflateTable()，而1.8则集成到扩容函数中
• hash值的计算方式：1.7是9次扰动，4次位运算+5次异或运算，而1.8是两次扰动，1次位运算+1次异或运算
• 插入数据的方式：1.7是头插法，而1.8是尾插法

15.什么是红黑树

什么是二叉树

1. 二叉树简单来说就是 每一个节上可以关联俩个子节点

红黑树是一种特殊的二叉查找树。有一些特性

1. 红黑树的每个结点上都有存储位表示结点的颜色，可以是红(Red)或黑(Black)。
2. 根结点一定是黑色。
3. 每个叶子结点（叶子结点代表终结、结尾的节点）也是黑色
4. 如果一个结点是红色的，则它的子结点必须是黑色的。

红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的结点之后，红黑树的结构就发生了变化，可能不满足上面三条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转和变色，可以使这颗树重新成为红黑树。简单点说，旋转和变色的目的是让树保持红黑树的特性。

16.（HashMap）为什么不用二叉树？

　　红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的O(n)时间复杂度。

17.HashMap的put方法的具体流程？

　　1、判断键值对数组table[i]是否为空（null）或者length=0，是的话就执行resize()方法进行扩容。

　　2、不是就根据键值key计算hash值得到插入的数组索引i。

　　3、判断table[i]==null，如果是true，直接新建节点进行添加，如果是false，判断table[i]的首个元素是否和key一样，一样就直接覆盖。

　　4、判断table[i]是否为treenode，即判断是否是红黑树，如果是红黑树，直接在树中插入键值对。

　　5、如果不是treenode，开始遍历链表，判断链表长度是否大于8，如果大于8就转成红黑树，在树中执行插入操作，如果不是大于8，就在链表中执行插入；在遍历过程中判断key是否存在，存在就直接覆盖对应的value值。

　　6、插入成功后，就需要判断实际存在的键值对数量size是否超过了最大容量threshold，如果超过了，执行resize方法进行扩容。

18.HashMap的put方法的具体流程？

　　1. 通过 hash & (table.length - 1)获取该key对应的数据节点的hash槽;
　　2. 判断首节点是否为空, 为空则直接返回空;
　　3. 再判断首节点.key 是否和目标值相同, 相同则直接返回(首节点不用区分链表还是红黑树);
　　4. 首节点.next为空, 则直接返回空;
　　5. 首节点是树形节点, 则进入红黑树数的取值流程, 并返回结果;
　　6. 进入链表的取值流程, 并返回结果;

　　当我们put的时候，首先计算 key 的 hash 值，这里调用了 hash 方法， hash 方法实际是让key.hashCode() 与 key.hashCode()>>>16 进行异或操作，高16bit补0，一个数和0异或不变，所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。按照函数注释，因为bucket数组大小是2的幂，计算下标 index = (table.length - 1) & hash ，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中用了复杂度 O（logn）的树结构来提升碰撞下的性能。

 19.HashMap的扩容操作是怎么实现的？

1. 在jdk1.8中，resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize方法进行扩容；
2. 每次扩展的时候，都是扩展2倍；
3. 扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。

20.HashMap是怎么解决哈希冲突的？

什么是哈希？

　　Hash，一般翻译为“散列”，也有直接音译为“哈希”的， Hash就是指使用哈希算法是指把任意长度
的二进制映射为固定长度的较小的二进制值，这个较小的二进制值叫做哈希值。

什么是哈希冲突？

当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做碰撞（哈希碰撞）。

HashMap的数据结构

　　在Java中，保存数据有两种比较简单的数据结构：数组和链表。

• 数组的特点是：寻址容易，插入和删除困难；
• 链表的特点是：寻址困难，但插入和删除容易；

所以我们将数组和链表结合在一起，发挥两者各自的优势，就可以使用俩种方式：链地址法和开放地址法可以解决哈希冲突：

但相比于hashCode返回的int类型，我们HashMap初始的容量大小
DEFAULT_INITIAL_CAPACITY = 1 << 4 （即2的四次方16）要远小于int类型的范围，所以我们
如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率，并且最
坏情况下还会将HashMap变成一个单链表，所以我们还需要对hashCode作一定的优化

hash()函数

上面提到的问题，主要是因为如果使用hashCode取余，那么相当于参与运算的只有hashCode的
低位，高位是没有起到任何作用的，所以我们的思路就是让hashCode取值出的高位也参与运算，
进一步降低hash碰撞的概率，使得数据分布更平均，我们把这样的操作称为扰动，在JDK 1.8中的
hash()函数如下：

21.能否使用任何类作为 Map 的 key？

可以使用任何类作为 Map 的 key，然而在使用之前，需要考虑以下几点：

• 如果类重写了 equals() 方法，也应该重写 hashCode() 方法。
• 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。
• 如果一个类没有使用 equals()，不应该在 hashCode() 中使用它。

用户自定义 Key 类最佳实践是使之为不可变的，这样 hashCode() 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变，这样就会解决与可变相关的问题了。

22.为什么HashMap中String、Integer这样的包装类适合作为K？

1. String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性，能够有效的减少Hash碰撞的几率
2. 都是final类型，即不可变性，保证key的不可更改性，不会存在获取hash值不同的情况
3. 内部已重写了 equals() 、 hashCode() 等方法，遵守了HashMap内部的规范（不清楚可以去上面看看putValue的过程），不容易出现Hash值计算错误的情况；

23.如果使用Object作为HashMap的Key，应该怎么办呢？

　　重写 hashCode() 和 equals() 方法

24.HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标？

　　hashCode() 方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 - 1)，约有40亿个映射空
间，而HashMap的容量范围是在16（初始化默认值）~2 ^ 30，HashMap通常情况下是取不到最
大值的，并且设备上也难以提供这么多的存储空间，从而导致通过 hashCode() 计算出的哈希值可
能不在数组大小范围内，进而无法匹配存储位置；

25.HashMap 的长度为什么是2的幂次方?

　　为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树
长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。
这个算法应该如何设计呢？
　　我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是
2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的
前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效
率，这就解释了 HashMap 的长度为什么是2的幂次方。
那为什么是两次扰动呢？
　　答：这样就是加大哈希值低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置
的随机性&均匀性，最终减少Hash冲突，两次就够了，已经达到了高位低位同时参与运算的目的；

26.HashMap 与 HashTable 有什么区别？

1. 线程安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过 synchronized 修饰。
2. 效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
3. 对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛NullPointerException。
4. 初始容量大小和每次扩充容量大小的不同 ：创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。
5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

27.什么是TreeMap 

1. TreeMap 是一个有序的key-value集合，它是通过红黑树实现的。
2. TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
3. TreeMap是线程非同步的。

28.ConcurrentHashMap 底层具体实现知道吗？实现原理是什么？

JDK1.7

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

• 在JDK1.7中，ConcurrentHashMap采用Segment + HashEntry的方式进行实现，结构如下：一个 ConcurrentHashMap 里包含一个 Segment 数组。

Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，
每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。

• 该类包含两个静态内部类 HashEntry 和 Segment ；前者用来封装映射表的键值对，后者用来充当锁的角色；

• Segment 是一种可重入的锁 ReentrantLock，每个 Segment 守护一个HashEntry 数组里得元
  素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 锁。
  

JDK1.8

• 在JDK1.8中，放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现，synchronized只锁定当前链表或红黑二叉树的首节点，
  这样只要hash不冲突，就不会产生并发，效率又提升N倍。
  
  
• 如果相应位置的Node还没有初始化，则调用CAS插入相应的数据；
• 如果相应位置的Node不为空，且当前该节点不处于移动状态，则对该节点加synchronized锁，如果该节点的hash不小于0，则遍历链表更新节点或插入新节点；

• 如果该节点是TreeBin类型的节点，说明是红黑树结构，则通过putTreeVal方法往红黑树中插入节
  点；如果binCount不为0，说明put操作对数据产生了影响，如果当前链表的个数达到8个，则通
  过treeifyBin方法转化为红黑树，如果oldVal不为空，说明是一次更新操作，没有对元素个数产生
  影响，则直接返回旧值；

• 如果插入的是一个新节点，则执行addCount()方法尝试更新元素个数baseCount；

29.TreeMap 和 TreeSet 在排序时如何比较元素？Collections 工具类中的 sort()方法如何比较元素？

• TreeSet 要求存放的对象所属的类必须实现 Comparable 接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。
• TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进 行排 序。

Collections 工具类的 sort 方法有两种重载的形式，
第一种要求传入的待排序容器中存放的对象比较实现 Comparable 接口以实现元素的比较；
comparable接口实际上是出自java.lang包，它有一个 compareTo(Object obj)方法用来排序
comparator接口实际上是出自 java.util 包，它有一个compare(Object obj1, Object obj2)方法用来排序
一般我们需要对一个集合使用自定义排序时，我们就要重写compareTo方法或compare方法，当我们需要对某一个集合实现两种排序方式，比如一个song对象中的歌名和歌手名分别采用一种排序方法的话，我们可以重写compareTo方法和使用自制的Comparator方法或者以两个Comparator来实现歌名排序和歌星名排序，第二种代表我们只能使用两个参数版的Collections.sort().

30.Java集合1-集合与数组的区别

数组时一种容器，既然有了数组为什么还需要集合呢？？是因为数组有些固有的缺陷到时无法满足我们的需求，就有了集合。

区别1：长度

数组：数组的长度固定。不论是静态定义数组还是动态定义数组，在我们定义好数组时就会确定数组的长度。

集合：集合的长度是不固定的，是可以扩容的。（类型StringBuffer/StringBuilder是可变长度的）

却别2：元素唯一性

数组：元素类型只有一种。我们定义数组时就会定义好数组的数据类型即元素的数据类型只能是这一种

集合：可以有多重数据类型。

却别3：元素的数据类型

数组：可以存放对象、基本数据类型

集合：只能存放对象，如果想要存在基本数据类型需要存放其对应的包装类