2020-11-15 20:55 已编辑 Java

关注

秋招结束，回馈牛客系列2

本人渣硕，继上篇帖子整理JVM资料之后，得到牛友们较高的关注，最近整理了java集合相关资料（主要是根据公众号JavaGuide一篇文章总结（特此表示感谢，下面会附上文章链接）及个人面经总结），第二次发帖，希望各位大佬指正，最近刚刚签了三方，预祝各位牛友收获满意的offer。

一.整体架构

框架：Collection是单列集合的根接口，Map是双列集合的根接口；

1.List接口与Set接口及Map接口的区别

List集合：存储有顺序；可以重复存储；有索引

Set集合：存储无顺序；不可以重复存储，无索引

Map集合：使键值对进行存储（类似于函数，键是x,值是y）,键Key是无序的，不可以重复；值Value是无序的，值可以重复，每个键最多映射到一个值

2.如何选用集合

①如果我们需要根据键来存储值时，我们需要使用实现Map接口的结合来进行存储，需要排序时，选择TreeMap;不需要排序时，选择HashMap，如果需要保证线程安全的话，就采用ConcurrentHashMap;

②如果我们只是对元素值进行存储，我们可以采用实现Collection接口的集合；如果需要保证元素唯一的话，采用实现Set接口的集合如HashSet或者TreeSet；如果不需要保证元素唯一，采用实现List接口的集合，如ArrayList或者LinkedList集合，然后根据各自集合的特点进行选取；

3.为什么要使用集合

当我们进行存储元素时，我们需要用一个容器来进行接收，可以使用数组，但是数组有很多局限性，对存储的数据类型，数组的大小等有要求，因此采用需要各种各样的集合进行存储。

4.Iterator迭代器的定义和作用

定义：提供一种方法来访问集合中的各个元素，而不需要暴露更多细节。

作用：主要是用来遍历集合用的，他的主要特点是更加安全，在遍历集合的同时，如果集合被更改，则会报并发修改异常信息

5.有哪些集合是线程不安全的？如何解决？

不安全的线程有：List:ArrayList、LinkedList;Set：HashSet和TreeSet;Map:HashMap和TreeMap等都是线程不安全的；

解决：Java.util.Concurrent包下提供了线程安全的集合类来代替不安全的集合：

如：ConcurrentHashMap代替HashMap

CopyOnWriteArrayList可以看成是线程安全的ArrayList；

ConcurrentLinkedQueue可以看成是线程安全的LinkedList；

copyOnWriteArraySet：可以看成是线程安全的HashSet。

二、Collection子接口List

1.ArrayList与Vector的区别：

①：线程安全性：ArrayList底层数据结构是数组,线程不安全；Vector底层也是数组，是线程安全的。

②：扩容机制：ArrayList初始化容量为10，然后在添加元素超过10后，会以1.5倍的容量进行扩容；而Vector的扩容倍数为2倍；

2.ArrayList与LinkedList的区别（重点）

①：底层的数据结构：ArrayList的底层数据结构的数组；LinkedList的底层数据结构是双向链表；

②：插入和删除元素是否受元素位置影响：ArrayList因为底层是数组，插入和删除元素的时间复杂度受到元素位置影响；

LinkedList底层依赖的是双向链表，如果采用add(E e)方法时，几乎不受影响，但是调用add(int index,E e)时，插入或删除指定位置时元素时，会受到影响；

③：是否支持快速访问，ArrayList底层依赖的是数组，可以根据索引快速访问指定元素；LinkedList不可以；

④：内存空间的占用情况：ArrayList空间消耗主要是结尾预留出一定空间；LinkedList空间消耗主要是体现在每一个元素都比ArrayList多（需要存储直接后继和前驱以及数据）

3.ArrayList扩容机制

①当通过add方法向ArrayList中添加元素时，ArrayList会初始化一个容量为10的数组，然后当添加的元素数量超过10之后，会以1.5倍的容量进行扩容。

4.LinkedList和ArrayList各自的优势是什么？

ArrayList的优势：修改与查询的速度较快，因为底层是数组实现；

LinkedList的优势：增加和删除元素较快，因为底层是链表实现。

三、Collection子接口Set

1.HashSet保证元素唯一性原理

①当向HashSet集合中添加元素时，先调用对象的hashCode()方法获取对象的哈希值，然后与集合中其他对象的哈希值进行比较；如果不存在哈希值相等的对象，则加入集合中；

②如果存在哈希值相等的对象，此时会调用equals()进行判断，如果结果返回false,则进行存储；如果返回ture,则不会进行存储

补充：==和equals()的区别：

对于基本数据类型：==和equals()没有区别

对于引用数据类型而言：==比较的两者引用是否指向同一个地址；如果对象的equals()方法没有被重写，则比较的是两者的地址值是否相等；如果被重写的话，比较的是两者的属性值是否相等。

2.TreeSet保证元素唯一性原理

①按照一定的顺序对元素进行排序，保证元素的唯一性

TreeSet中的两种排序方式

TreeSet底层依赖的是二叉树

①自然排序：TreeSet默认构造器的排序方式，主要是实现了comparable接口，接口中有唯一的方法为compareTo(Object o)方法用于比较，当方法返回负数时，存放在二叉树的左子树中，当方法返回正数时，存放在右子树中，返回为0,则不存。

②自定义排序：TreeSet构造器中传入指定的比较器，存储的对象类实现Comparator接口，然后重写其compare（Object o1,Object o2）方法，实现存储对象的比较，进行唯一性存储。

3.HashSet、LinkedHashSet和TreeSet的区别

①：底层的数据结构：HashSet底层依赖的是HashMap；LinkedHashMap底层依赖的是LinkedList和HashMap;TreeSet底层依赖的是红黑树；

②：线程的安全性：都是线程不安全的；

③：保证顺序的问题：LinkedHashSet能够保证怎么存怎么取，因为底层有链表；

HashSet和TreeSet能够保证元素按升序排列输出；

四、Collection子接口Queue和Deque

1.PriorityQueue

底层实现原理：通过二叉小顶堆实现，可以用一棵完全二叉树表示，PriorityQueue的底层可以通过数组来实现。

图片来源于网络博主，详细原理可参考：https://blog.csdn.net/u010623927/article/details/87179364

五、Map接口

1.HashMap的底层实现（必问）

jdk1.8之前：

①数据结构：数组+链表形式（链表散列）

②hash值计算：通过获取key的hashCode(),然后经过4次扰动＋5次异或计算得到

static int hash(int h) {
	// This function ensures that hashCodes that differ only by
	// constant multiples at each bit position have a bounded
	// number of collisions (approximately 8 at default load factor).
	h ^= (h >>>20) ^ (h >>>12);
	return h ^ (h >>> 7) ^ (h >>>4);
}

③链表结构的插入：头插法

jdk1.8之后：

①数据结构：数组+链表+红黑树

②hash值的计算：采用一次异或，一次扰动（无符号右移一定位数）

static final int hash(Object key) {
    int h;
    // key.hashCode()：返回散列值也就是hashcode
    // ^ ：按位异或
    // e>>>Å无符号右移，忽略符号位，空位都以0补齐
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

③链表插入的形式：尾插法

2.HashMap和HashTable的区别（重点）

①：线程安全：HashMap是线程不安全的，HashTable是线程安全的（内部的方法被Synchronized修饰）；

②：效率：HashMap效率要高于HashTable，HashTable基本已经不再使用

③：Null值：HashMap的Key和value可以为null,HashTable的key和value不允许为null值。

④：初始容量大小和扩容方式：

1，如果没有给定初始容量，则HashMap的默认容量为16，达到原容量的0.75倍时，之后的扩容每次会扩充原来的2倍，HashTable的默认容量为11，扩容因子也是0.75，之后的每次扩容将会变为2n+1(其中n为数组的长度)。

2.如果一开始给定了初始值，则HashMap会扩容到2的幂次方；而HashTable则会使用给定的大小；

⑤：底层的数据结构：HashMap在jdk1.8之后在解决哈希冲突时，当链表的长度超过默认阈值（默认为8）时（在数组长度小于64时，不会转为红黑树，而是先对数组进行扩容），会转为红黑树进行存储。

hashTable底层数据结构为：数组+链表的形式；

3.HashMap和HashSet的区别

底层数据结构：HashSet底层是依靠HashMap实现的，HashSet依靠HashMap获取HashCode值，然后如果两元素的HashCode值相等，则调用equals进行比较。

实现接口：HashMap实现了Map接口，而HashSet实现了Set接口。

存储数据形式：HashMap存储键值对，而HashSet存储对象。

4.HashMap和TreeMap的区别

TreeMap实现了SortedMap接口，实现了按照Key值进行排序的功能，默认按照Key值升序方式。

5.HashMap、TreeMap和LinkedHashMap的区别

1.底层数据结构：

①HashMap：数组+链表；数组+链表/红黑树；

②TreeMap：红黑树

③LinkedHashMap：链表+HashMap

2.是否有序：

①LinkedHashMap能够保证怎么存怎么取；

②HashMap和TreeMap能够实现按照key进行排序输出；

6.hashmap怎么计算hash值？

jdk1.7中，经过四次扰动，五次异或操作（尽可能避免哈希冲突）

jdk1.8及以后，经过一次扰动，一次异或操作

7.可以直接传入一个对象作为key吗？

不可以；

如果需要传入的话，需要重写对象的hashcode()和equals()方法；并且需要尽量保证对象不为null;

8.为什么hashMap重写了equals()方法，必须重写hashcode()方法？

1.首先解释一下hashcode()方法

a.Object的hashcode()方法是本地方法，也就是用c或者c++实现的，该方法直接返回对象的内存地址，如果没有重写hashcode()，则任何对象的hashcode()值都不相等。

2.该问题

HashMap中的put()方法是这样的，首先求出key的hashcode(),比较其值是否相等，如果相等再比较equals(),如返回true,则认为是相等的，如果返回false,则认为不相等。

如果只重写了equals()方法，没有重写hashcode()方***导致相同的key值也被hashcode认为是不同的key值，就会在hashmap中存储相同的key值；即本来相等的key,应该直接覆盖，这样就没法覆盖了。

9.为什么jdk1.8更改HashMap数据进行更改

jdk1.8之前，在查找元素的时候，我们能够根据hash值快速定位到数组的下标，后面需要在链表中一个一个比较的找，时间复杂度为O(n)。在1.8之后，当链表的长度超过8以后，则采用红黑树的结构，这样这部分时间复杂度就变为了O（logn）。特殊情况：如果所有的对象的hash值相等，则会退化为一个链表结构（线性结构）。

10.HashMap数据存储过程

首先根据存储数据的key值，获取其对应的hashcode,然后经过hash函数，获取到hash值，根据此hash值找到数组的索引位置，如果数组的该位置为空，则将该键值对直接进行存储，如果不同key值的最终获取到的hash值相同，即出现哈希冲突时，在jdk1.8之前，采用数组+链表的形式，即首先比较key是否相等，如果相等的话，则直接覆盖；如果不是同一个key,则按照顺序存储在链表中；在jdk1.8之后采用数组+链表/红黑树的结构，出现哈希冲突时，当判断不是同一个key之后，存入到链表中，然后当链表的长度超过8后，将链表转化为红黑树进行存储。

11.HashMap如何解决哈希冲突

jdk1.8之前采用拉链法解决哈希冲突，即采用数组+链表的方式，将出现冲突的值加到链表中即可。

jdk1.8之后，解决哈希冲突的方法是：当链表的长度大于阈值（默认为8）时，首先判断当前数组是否小于64，如果小于64，则首先进行扩容。如果长度>64,则将链表转为红黑树进行存储。

12.HashMap扩容机制

1.不设置初始大小：默认大小为16，扩容系数为0.75，当达到阈值时，会扩容为原来大小的两倍；

2.设置初始大小：当达到阈值时，在原来你大小的基础上会扩充为2的幂次方的大小。

13.hash值如何获取？

jdk1.7中，经过四次扰动，五次异或操作（尽可能避免哈希冲突）

jdk1.8及以后，经过一次扰动，一次异或操作

14.HashMap底层实现

jdk1.8之前，hashMap的底层是数组+链表的结构，HashMap通过key的hashcode经过hash()函数后获得hash值，然后通过（n-1）d&hash值判断当前元素在数组中的位置，如果当前位置不存在元素，则直接存储，如果存在元素，则比较k和hash值是否相等，相等则直接覆盖，如果不相等则通过拉链法解决哈希冲突；

所谓的拉链法指的是，采用数组+链表的形式，遇到哈希冲突，将其存储到链表中。

jdk1.8之后，采用了数组+链表/红黑树的结构，当链表的长度大于默认的阈值8时，在转化为红黑树之前会先判断当前的数组的长度是否大于64，如果不大于64，则首先会进行扩容，如果大于64，则会将链表转化为红黑树，以减少搜索时间（从时间复杂度方面分析）。

15.concurrentHashMap的底层实现

jdk1.7采用分段的数据+链表实现；jdk1.8采用的数据结构跟hashMap1.8结构一样；

实现线程安全的原因？

jdk1.7之前是采用分段锁的方式，对数组进行分割，然后对每一段加锁，多线程访问不同数据段的数据，就不会出现锁竞争；

jdk1.8时，jdk1.6以后，对synchronized锁进行了很多优化，并发控制sychronized和CAS来操作。

16.HashMap为什么是线程不安全的？

问题一：HashMap不是线程安全的，其并没有加锁机制，当多个线程操作时，可能会出现线程安全问题，即put的时候导致多个线程数据不一致；有两个线程A和线程B，线程A得到插入数组中的位置时，此时线程B得到执行权，然后得到数组中的位置相同，则进行插入，此时线程A执行，然后他依然按照之前的方式进行插入，会造成直接写覆盖。

问题二：jdk1.8之前，采用头插法，可能存在死循环问题；

原因：HashMap在进行扩容的时候，对每个元素进行迁移，采用头插***将元素顺序倒置，导致两个线程中出现元素的相互指向而形成循环链表。

问题三：为什么jdk1.8之后，解决了这个问题

原因：jdk1.8之后，采用尾插法，能够保证每个元素的顺序与迁移前一致。

17.Map里面有没有有序的Map？

如果是按照元素怎么存怎么取顺序，则LinkedHashMap和LinkedHashSet是有序的；

如果是按照Key的大小输出是否是有序的话,TreeMap默认是升序的，如果我们要改变排序方式的话，需要使用比较器comparator,然后冲写其compare方法。

18.HashMap为什么每次扩容都扩大2倍？

主要是因为hashmap的key值经过hashcode()然后再经过hash函数之后，得到hash值，然后采用hash%n的形式，能够确定其在数组中的位置，但是这样计算速度比较慢，影响整体性能，于是采用(n-1)&hash的方式能够加快计算，但是其两者等价的前提为数组的长度为2的n次幂。

19.HashMap的相关方法

①put()方法

1.执行过程

a.首先通过key,计算出在数组中的位置，然后判断当前位置是否为空，如果为空，则直接插入；

b,当前位置如果不为空，则通过equals()方法比较，两key是否相等，如果相等，则直接覆盖；如果不相等;

c.则当前是否是红黑树，如果是则遍历红黑树，如果存在相等的key,则直接覆盖，如果不存在，则插入键值对；如果不是红黑树，

d.则遍历链表，如果存在相等的key，则直接覆盖，如果不存在，则插入；

f.然后判断链表的长度是否>8，如果>8,则将链表转化为红黑树。

②get()方法

1.执行过程

a.对key的hashcode()做hash运算，获取在数组中的index;

b.如果为空的话，则直接返回null;如果不为空，则进行下一步判断；

c.如果此时第一个就命中的话，则直接返回value值；否则，

d.如果存在冲突，则通过key的equals方法去进一步查找；

e.如果是树，则查找的时间复杂度为：O（logn）;

f.如果是链表，则遍历链表，时间复杂度：O(n);

g.如果都不存在，则返回null;

20.Hashmap的解决依赖循环问题？

1.问题：HashMap在进行扩容的时候，对每个元素进行迁移，采用头插***将元素顺序倒置，导致两个线程中出现元素的相互指向而形成循环链表，因此采用头插法，可能存在死循环问题；

2.解决：jdk1.8之后，采用尾插法，能够保证每个元素的顺序与迁移前一致。

21.HashMap中hash函数的作用及实现

①作用：让元素尽可能均匀分配在数组中相应索引处，进可能减少哈希冲突；

②实现：jdk1.8之前，通过对key的hashcode进行四次扰动，五次异或操作；

jdk1.8之后，通过对key的hashcode进行一次扰动，一次异或操作；

22.散列表解决哈希冲突的方法

①开放地址法

核心思想：如果出现散列冲突，则重新探测一个新的空闲位置，将其插入；

实现：

1.线性探测：当我们往散列表中插入数据时，如果某个数据经过hash后，发现存储位置已经被占用，我们就从当前位置开始，依次往后查找，直到找到空闲位置；

2.二次探测：线性探测每次探测步长为1，而二次探测步长为原来的二次方；

3.双重散列：如果一次哈希后，出现冲突，然后再次进行哈希，直到找到空闲位置；

②拉链法解决哈希冲突

出现哈希冲突时，采用链表法，将冲突元素按照尾插法进行插入，解决哈希冲突。

六、并发容器相关

1.ConcurrentHashMap相关

①ConcurrentHashMap如何保证线程安全？

a.jdk1.8之前，数据结构为：Segment数组+HashEntry数组+链表。Segment实现了ReentrantLock,实现锁的功能，HashEntry用于存储键值对数据，链表用于解决哈希冲突。

采用分段锁的方式来保证线程安全，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

b.jdk1.8及以后，底层数组结构：Node数组+链表/红黑树。ConcurrentHashMap成员变量使用volatile修饰，保证了禁止指令重排和内存可见性，另外使用CAS和Synchronized结合实现赋值操作，多线程操作只会锁住当前链表或者红黑树的首节点，只要不发生哈希冲突，则效率会更高。