首页 > 秋招结束,回馈牛客系列2
头像
全村儿的希望~
编辑于 2020-11-15 20:55
+ 关注

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

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

一.整体架构

框架:Collection是单列集合的根接口,Map是双列集合的根接口;

1b23881bed883ba018a5dcae56a9a557.png

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

a3438479fb7c40e21489defd886b844.png

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

7b1c64821780c3be256bb51de440f7aa.png

1.PriorityQueue

底层实现原理:通过二叉小顶堆实现,可以用一棵完全二叉树表示,PriorityQueue的底层可以通过数组来实现。
图片来源于网络博主,详细原理可参考:https://blog.csdn.net/u010623927/article/details/87179364

五、Map接口

1.HashMap的底层实现(必问)

jdk1.8之前:

①数据结构:数组+链表形式(链表散列)

beaf3054b9c5dd70234dfdc63454bd8.png

②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之后:

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

dcebb193370d8ecd4b884bfdab15f22.png

②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以后,则采用红黑树的结构,这样这部分时间复杂度就变为了Ologn)。特殊情况:如果所有的对象的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通过keyhashcode经过hash()函数后获得hash值,然后通过(n-1d&hash值判断当前元素在数组中的位置,如果当前位置不存在元素,则直接存储,如果存在元素,则比较khash值是否相等,相等则直接覆盖,如果不相等则通过拉链法解决哈希冲突;

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

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

15.concurrentHashMap的底层实现

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

实现线程安全的原因?

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

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

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倍?

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

19.HashMap的相关方法

①put()方法

1.执行过程

image

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修饰,保证了禁止指令重排和内存可见性,另外使用CASSynchronized结合实现赋值操作,多线程操作只会锁住当前链表或者红黑树的首节点,只要不发生哈希冲突,则效率会更高。

2.阻塞队列(BlockingQueue)

①阻塞队列是什么?

阻塞队列是一个支持两个附加操作的队列,这两个附加操作支持阻塞的插入和移除方法。

支持阻塞的插入方法:当队列满时,队列会阻塞插入元素的线程,直到队列不满。

支持阻塞的移除方法:当队列为空时,获取元素的线程会等待线程变为非空。

②阻塞队列的作用?

阻塞队列常用于生产者和消费者的场景,生产者是向队列里添加元素的线程,消费者是从队列里获取元素的线程,阻塞队列就是生产者用来存放元素、消费者用来获取元素的容器。

③有哪些常用的阻塞队列?

ArrayBlockingQueue:由数组结构组成的有界阻塞队列。

LinkedBlockingQueue:由链表结构组成的有界阻塞队列。

SynchronousQueue:不存放元素的阻塞队列

④ArrayBolckingQueue

ArrayBlockingQueue底层数据结构为数组,按照先进先出的原则对元素进行排序。

⑤LinkedBlockingQueue

LinkedBlockingQueue底层数据结构为链表,按照先进先出的原则对元素进行排序,此外,默认和最大的链表长度为:Integer.MAX_VALUE。

⑥SynchronousQueue

SynchronousQueue是一个不存储元素的阻塞队列,每一个put操作必须等待一个take操作,否则不能继续添加元素。

七、面试场景题

1.如果自己定义了一个类,作为map的key,需要注意哪些问题?

需要重写equals()方法和hashcode()方法

尽量保证不为空

尽量不修改key的值;

2.如果我先往map里面put进去自定义的Person类的key-value数据,这个类的nameage属性,然后将name修改了,那再get()会发生什么?

如果将name的值修改了,当get()的时候,会根据新的name值找到其在数组中的索引位置,此时大概率与之前存储的位置不相等,因此会get()到一个空;较小概率能够获取到修改后的键值。

3.如果我重写了equals方法,让两个Person类对象是否相等与name无关,那再get能得到数据吗?

大概率是得不到的,因为name改变了,导致数组中的索引值改变了,索引在新的索引位置是找不到值的,还是会返回null;equals()方法是当出现hash冲突时,比较是否相等的方法,因此重写与不重写没啥关系。

4.如果我重写了hashcode方法,让hashcodename无关,那能get到数据吗?

如果是重写了equals方法,与name无关,则会get到数据;如果equals方法与name有关,则get不到数据;


全部评论

(5) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐