回馈牛客,分享面试以及答题要点和思路——集合篇
前言:从牛客这里收获了很多,下面的这些题目有的是自己遇到过的,有的是牛客上大家分享出来的,牛客面试题目是很多,但是美中不足的是缺少回答,其实也不太好回答,因为太广了,这里我给出我自己的一些答题要点和思路,基本概念不会有太大的变动,但是思路变化可以千千万,就看你自己怎么和面试官聊了,我个人觉得比较好的回答的思路: 基本原则是尽量回答原理,以及自己在项目中是如何考虑到的,为什么使用它,对比优缺点,技术选型!集合的最佳实践见下方!!!(强烈安利)
另外推荐一下个人刷面经的方法,先收藏,然后建立标签刷和未刷,自己做好笔记,分类进行记录,弥补自己的不足!(求素质三连,评论,点赞,收藏,另外牛妹求加精啊!!!)
集合概述
集合的概述
(大概答出体系,Collection接口,Map接口,Collection还继承了Iterable接口,Collection 它不提供该接口的具体实现。具体的子接口有 List 和 Set 接口 和 Queue 接口,接着就是子接口的各种特点,无序,重复,然后答具体的实现类HashMap,LinkedList等,快速失败机制,为什么存在这个机制,对比安全失败,然后解决线程安全的问题,举一个例子:ArrayList,CopyOnWriterArrayList 然后又可以答具体实现,如何解决线程安全的问题,项目中怎么用到的?设计的思想是什么?)
ArrayList
ArrayList的原理
(实现的接口,标记接口,动态数组,它是线程不安全的,允许元素为null。 其底层数据结构依然是数组)
保存元素的数组使用transient 修饰,为什么
(保存元素的数组不一定都会被使用,那么就没必要全部进行序列化,那如何解决序列化的问题的,思考)
ArrayList数组延迟分配对象数组空间
(空的ArrayList也会浪费内存,对象头,所以把空数组的引用赋值给它,达到延迟初始化,更加合理地区使用内存的目的)
ArrayList的增加元素以及扩容操作
(add()——> ensureCapacityInternal() ——> ensureExplicitCapacity() ——> grow() ——> 比较Integer-8 )
为什么扩容操作都是1.5?
(一次性扩容太大,一次性扩容太小)
ArrayList解决频繁扩容问题的策略
(在创建时就声明一个较大的大小,这样解决了频繁拷贝问题或者还可以在插入前先进行一次扩容。只要提前预知数据的数量级,就可以在需要时直接一次扩充到位 与之前的相比相比的好处在于不必一直占有较大内存,同时数据拷贝的次数也大大减少了)
循环删除问题
(两个相同且连续的元素值,而刚好我要删除这个相同的元素的话,就会导致的结果是只能删除掉第一个元素值)
数组的两种复制的方式
(底层调用C++)
最小化存储量
(trimToSize 将底层数组的容量调整为当前列表保存的实际元素的大小的功能 )
Vector能否保证插入安全?
(不能出现两个及两个以上的线程在同时调用这些同步方法,有些线程连续调用了两个或两个以上的同步方法,需要用的时候怎么办?复合操作加锁 )
Array和ArrayList的异同,具体的使用场景?
(Array 可以包含基本类型和对象类型,ArrayList 只能包含对象类型。Array 大小固定,ArrayList 的大小是动态变化的。ArrayList 提供更多 的方法和特性,如:addAll(),removeAll(),iterator()等等。)
ArrayList与LinkedList有什么区别
(线程安全,数据结构,插入和删除的操作,内存空间问题,使用场景问题)
HashMap
哈希算法有哪些
(平方取中法,除留余数法,伪随机数法)
解决哈希冲突的方法
(开放定址法:ThreadLocal,链地址法 HashMap,再哈希法。。。。。)
String的哈希算法实现?
(31,素数)
HashMap的大致原理
- HashMap 实现了Serializable接口,因此它支持序列化,将对象保存到本地,实现了Cloneable接口,能被克隆,但是浅拷贝
- HashMap是非线程安全的,只适用于单线程环境,多线程环境可以采用并发包下的concurrentHashMap
存放数据的时候
- 当我们往hashmap里面放键值对的时候,计算HashCode主要有三步XXXXX(key.hashCode,扰动函数,取模运算)
- 哈希冲突,解决不同版本的解决方法,为什么,思路
取数据(get),初始化(put)
HashMap的主要参数
(容量,扩容阀值,加载因子xxx)
为什么是0.75的加载因子
(JDK注解如下图所示:负载因子太小了浪费空间并且会发生更多次数的resize,太大了哈希冲突增加会导致性能不好,所以0.75只是一个折中的选择,和泊松分布没有什么关系。加载因子过大,过小的缺点导致的结果说明)
2的整数次幂 和 hashcode 的与运算?
(通常来说素数导致的哈希冲突概率比较低,取模的哈希结果会比较均匀,比如HashTable中就是采用素数的情况,默认的初始大小为11,之后每次扩充为原来的2n+1。
但是HashMap的容量,在源码里面进行了规定了数组的长度是2的次幂,是一个合数。且用与运算操作。主要的原因如下:
- 当length总是2的n次方时,h& (length-1)运算等价于对数组的长度进行取模,将hash生成的整型转换成链表数组中的下标
- 位运算(&)效率要比代替取模运算(%)高很多,主要原因是位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。
- 当n为2的幂次方时,2的n次方-1 实际就是n个1,这种情况下,index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀,Hash算法的结果就是均匀的。(n-1)& hash 的值是均匀分布的。)
扩容机制
(什么时候才扩容,扩容与树形化的区别——最小树形化)
多线程环境下的线程安全问题(有三个,1.8解决了一个,剩2)
(JDK7 扩容时形成死循环的问题,https://blog.csdn.net/qfzhangwei/article/details/69938937)
JDK1.8中HashMap的优化
- 数据结构
- 获取数据时
- 扩容机制
解决hash冲突的时候,不直接用红黑树?而选择先用链表,再转红黑树?
(因为红黑树需要进行左旋,右旋,变色这些操作来保持平衡,而单链表不需要。 当元素小于8个当时候,此时做查询操作,链表结构已经能保证查询性能。
如果一开始就用红黑树结构,元素太少,新增效率又比较慢,无疑这是浪费性能的。
用二叉查找树可以么? 可以。但是二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成很深的问题),遍历查找会非常慢。)
转为红黑树是8,退化为链表是6,最小树形化?
理想情况下,在随机哈希代码下,桶中的节点频率遵循泊松分布,文中给出了桶长度k的频率表。由频率表可以看出,桶的长度超过8的概率非常非常小。所以作者应该是根据概率统计而选择了8作为阀值。红黑树的平均查找长度是log(n),长度为8,查找长度为log(8)=3,链表的平均查找长度为n/2,当长度为8时,平均查找长度为8/2=4,这才有转换成树的必要;链表长度如果是小于等于6,6/2=3,虽然速度也很快的,但是转化为树结构和生成树的时间并不会太短。还有选择6和8的原因是:
中间有个差值7可以防止链表和树之间频繁的转换。假设一下,如果设计成链表个数超过8则链表转换成树结构,链表个数小于8则树结构转换成链表,如果一个HashMap不停的插入、删除元素,链表个数在8左右徘徊,就会频繁的发生树转链表、链表转树,效率会很低。
为什么HashMap可以插入空值?
(从JDK的源码文档上看,当时HashTable不允许插入null。是因为希望每个 key 都会实现 hashCode 和 equals 方法。而 null 显然没有,所以要进行异常的抛出。)
顺序随着时间而改变?
(扩容,位置发生变化,1.7 1.8 对比,)
String、Integer 这样的包装类适合作为 key 键/自定义一个class作为Key的实现该如何定义?
(可变类当HashMap的key:hashcode可能发生改变,导致put进去的值,无法get出 ,hashcode,equals)
HashMap、Linkedhashmap 、TreeMap的区别
- 数据结构
- 特点和使用场景
HashMap和Hashtable区别
(线程是否安全, 效率,对Null key 和Null value的支持, 初始容量大小和每次扩充容量大小的不同,哈希算法,数据结构)
HashSet 的实现原理
(底层采用 HashMap 来保存元素,hashcode,equals,判断重复元素 )
HashMap与HashSet区别,两者在查询某个值的效率
(在查询效率上来说,在不冲突的情况下,HashMap是 O(1) 效率当然要高,HashSet是当调用HashSet的contains(Object obj)方法时,其实是先调用每个元素的hashCode()方法来返回哈希码。如果哈希码的值相等的情况下再调用equals(obj)方法去判断是否相等,只有在这两个方法所返回的值都相等的情况下,才判定这个HashSet包含某个元素。因此,需重写 Course类的hashCode()方法和equals()方法。)
HashSet 和 TreeSet 区别
(数据结构,使用场景,特点,区别就从这里答!)
ConCurrentHashMap
并发性如何体现?
- 用分离锁实现多个线程间的更深层次的共享访问。
- 用 HashEntery 对象的不变性来降低执行读操作的线程在遍历链表期间对加锁的需求。
- 通过对同一个 Volatile 变量的写 / 读访问,协调不同线程间读 / 写操作的内存可见性。
https://www.ibm.com/developerworks/cn/java/java-lo-concurrenthashmap/
基本的数据结构的变化
1.8 和 1.7
哈希算法
7中:ConcurrentHashMap 使用了一种变种的Wang/Jenkins 哈希算法,其主要母的也是为了把高位和低位组合在一起,避免发生冲突。至于为啥不和HashMap采用同样的算法进行扰动,我猜这只是程序员自由意志的选择吧
Java 8的ConcurrentHashMap同样是通过Key的哈希值与数组长度取模确定该Key在数组中的索引。同样为了避免不太好的Key的hashCode设计,它通过如下方法计算得到Key的最终哈希值。不同的是,Java 8的ConcurrentHashMap作者认为引入红黑树后,即使哈希冲突比较严重,寻址效率也足够高,所以作者并未在哈希值的计算上做过多设计,只是将Key的hashCode值与其高16位作异或并保证最高位为0(从而保证最终结果为正整数)
ConCurrentHashMap的Get方法?
(通过这种机制保证get操作能够得到几乎最新的结构更新。)
标记处1 if (count != 0) {
标记处2 if (v != null)//可以看出并没有使用锁,但 value 值为 null 时才使用了加锁
get 代码的①和②之间,另一个线程新增了一个 entry
因为每个 HashEntry 中的 next 也是 final 的,没法对链表最后一个元素增加一个后续 entry 所以新增一个 entry 的实现方式只能通过头结点来插入了。
newEntry 对象是通过 new HashEntry(K k , V v, HashEntry next) 来创建的。如果另一个线程刚好 new 这个对象时,当前线程来 get 它
因为没有同步,就可能会出现当前线程得到的 newEntry 对象是一个没有完全构造好的对象引用
如果在这个 new 的对象的后面,则完全不影响,如果刚好是这个 new 的对象,那么当刚好这个对象没有完全构造好,也就是说这个对象的 value 值 为 null
就出现了如上所示的代码,需要重新加锁再次读取这个值!
get 代码的①和②之间,另一个线程修改了一个 entry 的 value
value 是用 volitale 修饰的,可以保证读取时获取到的是修改后的值。
get 代码的①之后,另一个线程删除了一个 entry
假设我们的链表元素是:e1-> e2 -> e3 -> e4 我们要删除 e3 这个 entry, 因为 HashEntry 中 next 的不可变,所以我们无法直接把 e2 的 next 指向 e4, 而是将要删除的节点之前的节点复制一份,形成新的链表。
如果我们 get 的也恰巧是 e3,可能我们顺着链表刚找到 e1,这时另一个 线程就执行了删除 e3 的操作,而我们线程还会继续沿着旧的链表找到 e3 返回。
这里没有办法实时保证了,也就是说没办法看到最新的。 我们第①处就判断了 count 变量,它保障了在 ①处能看到其他线程修改 后的。①之后到②之间,如果再次发生了其他线程再删除了 entry 节点,就没法保证看到最新的了,这时候的 get 的实际上是未更新过的!!!。
不过这也没什么关系,即使我们返回 e3 的时候,它被其他线程删除了, 暴漏出去的 e3 也不会对我们新的链表造成影响
(1.8的get1. 计算hash值,定位到该table索引位置,如果是首节点符合就返回
- 如果遇到扩容的时候,会调用标志正在扩容节点ForwardingNode的find方法,查找该节点,匹配就返回
- 以上都不符合的话,就往下遍历节点,匹配就返回,否则最后就返回null)
ConCurrentHashMap的put方法
1.8的更新太多了,TreeNode / TreeBin / ForwardingNode 节点
多线程协助扩容问题
ConCurrentHashMap的 size 方法?
1.7
- 对整张表加锁实现同步的一个缺陷就在于使程序的效率变得很低
- 每个 Segment 维护了一个 count 变量来统计该 Segment 中的键值对个数。
- 在执行 size 操作时,需要遍历所有 Segment 然后把 count 累计起来。
- 之所以在每个 Segment 对象中包含一个计数器,而不是在 ConcurrentHashMap 中使用全局的计数器,是为了避免出现“热点域”而影响 ConcurrentHashMap 的并发性。
- ConcurrentHashMap 在执行 size 操作时先尝试不加锁,如果连续两次不加锁操作得到的结果一致,那么可以认为这个结果是正确的。
- 尝试次数使用 RETRIES_BEFORE_LOCK 定义,该值为 2,retries 初始值为 -1,因此尝试次数为 3。
- 如果尝试的次数超过 3 次,就需要对每个 Segment 加锁,这样造成全局锁表,会造成一定的性能损失
1.8 呢???
HashMap,HashTable 和 ConCurrentHashMap 区别
- 数据结构
- 线程安全
- 哈希算法
- 版本改进
- 实现原理
- 使用场景
迭代访问
什么是迭代器(Iterator)?
(迭代器是一种设计模式,它是一个对象,它可以遍历并选择序列中的对象,而开发人员不需要了解该序列的底层结构。)
Iterator 和 ListIterator 的区别是什么?
( Iterator可用来遍历Set和List集合,但是ListIterator只能用来遍历List。
Iterator对集合只能是前向遍历,ListIterator既可以前向也可以后向。
ListIterator实现了Iterator接口,并包含其他的功能,比如:增加元素,替换元素,获取前一个和后一个元素的索引,等等。)
使用Iterator遍历集合,删除值为a的元素会发生什么
(用iterator迭代器的remove方法不会fail fast,要是用普通的remove方***fail fast。)
Enumeration接口和Iterator接口的区别有哪些?
(枚举速度快,占用内存少,但是不是快速失败的,线程不安全。迭代允许删除底层数据,枚举不行。 Enumeration速度是Iterator的2倍,同时占用更少的内存)
Collections工具类
Collection和Collections的区别
(集合和包装类)
Collections的同步包装Map 与 ConcurrentHashMap 区别
(SynchronizedHashMap
会同步整个对象
每一次的读写操作都需要加锁
对整个对象加锁会极大降低性能
这相当于只允许同一时间内至多一个线程操作整个Map,而其他线程必须等待
ConcurrentHashMap当你程序需要高度的并行化的时候,你应该使用
ConcurrentHashMap
尽管没有同步整个Map,但是它仍然是线程安全的
读操作非常快,而写操作则是通过加锁完成的
在对象层次上不存在锁(即不会阻塞线程)
锁的粒度设置的非常好,只对哈希表的某一个key加锁)
Arrays.sort()和Collections.sort 在jdk1.6以前是用的归并排序,1.7后变成了TimSort排序(归并优化)为什么容易引发bug?
https://blog.csdn.net/shadow_zed/article/details/72758912
https://blog.csdn.net/shadow_zed/article/details/72758912
Timsort是一种结合了归并排序和插入排序的混合算法
先用的归并,当剩余数据小于一定数量就开始用插入
comparable 和 Comparator的区别
(Comparable 排序接口若一个类实现了Comparable接口,就意味着该类支持排序,Comparator比较器接口,我们若需要控制某个类的次序,而该类本身不支持排序。)
集合的最佳实践
(阿里的开发手册!!!比如:集合容量初始化,Map的迭代遍历经历选择entrySet ,Arrays.asList()把数组转换成集合时,不能使用其修改集合相关的方法,ArrayList的subList结果不可强转成ArrayList,否则会抛出ClassCastException异常等。。。。。。。。。。。)
#Java工程师##面试题目#