汇总:华为通用软件面试基础问题(java)(最新)

1、Collection接口下有哪些子类/h2>

1.2 Collection和Map

1.4 集合的遍历方法

用迭代器迭代

1.5 List接口的实现类

(1)ArrayList:底层数据结构是数组,查询快,增删慢,线程不安全,效率高,可以存储重复元素
(2)LinkedList 底层数据结构是链表,查询慢,增删快,线程不安全,效率高,可以存储重复元素
(3)Vector:底层数据结构是数组,查询快,增删慢,线程安全,效率低,可以存储重复元素

(2)、LinkedHashSet底层数据结构采用链表和哈希表共同实现,链表保证了元素的顺序与存储顺序一致,哈希表保证了元素的唯一性。线程不安全,效率高。
(3)、TreeSet底层数据结构采用二叉树来实现,元素唯一且已经排好序;唯一性同样需要重写hashCode和equals()方法,二叉树结构保证了元素的有序性。根据构造方法不同,分为自然排序(无参构造)和比较器排序(有参构造)。
  自然排序要求元素必须实现Compareable接口,并重写里面的compareTo()方法,元素通过比较返回的int值来判断排序序列,返回0说明两个对象相同,不需要存储;
  比较器排需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象,或者采用匿名内部类的方式new一个Comparator对象,重写里面的compare()方法;
**

比较:

**
  1、TreeSet 是二叉树(红黑树的树据结构)实现的,Treeset中的数据是自动排好序的,不允许放入null值;
  2、HashSet 是哈希表实现的,HashSet中的数据是无序的,可以放入null,但只能放入一个null,两者中的值都不能重复,就如数据库中唯一约束 ;
  3、HashSet要求放入的对象必须实现HashCode()方法,放入的对象,是以hashcode码作为标识的,而具有相同内容的String对象,hashcode是一样,所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例;
  适用场景分析:HashSet是基于Hash算法实现的,其性能通常都优于TreeSet。为快速查找而设计的Set,我们通常都应该使用HashSet,在我们需要排序的功能时,我们才使用TreeSet。

1.7 List和Set的比较

(1)、List,Set都是继承自Collection接口;
(2)、List特点:元素有放入顺序,元素可重复 ;Set特点:元素无放入顺序,元素不可重复,重复元素会覆盖掉;
(3)、Set:检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变。
    List:和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他元素位置改变。
https://www.cnblogs.com/dongtian-blogs/p/10861138.html

2 排序算法有哪些泡算法的时间复杂度和空间复杂度

排序算法分为两种:比较算法、非比较算法
1、比较算法时间复杂度O(nlogn) ~ O(n^2)
冒泡排序、选择排序、插入排序、归并排序、堆排序、快速排序
2、非比较排序O(n)
计数排序、基数排序、桶排序
特点:排序算法的稳定性:如果Ai = Aj,排序前Ai在Aj之前,排序后Ai还在Aj之前,则称这种排序算法是稳定的
排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,前一个键排序的结果可以为后一个键排序所用
具体算法以及代码请参考: https://editor.csdn.net/md/rticleId=105536263
时间复杂度
这个时间复杂度还是很好计算的:外循环和内循环以及判断和交换元素的时间开销;
最优的情况也就是开始就已经排序好序了,那么就可以不用交换元素了,则时间花销为:[ n(n-1) ] / 2;所以最优的情况时间复杂度为:O( n^2 );
最差的情况也就是开始的时候元素是逆序的,那么每一次排序都要交换两个元素,则时间花销为:[ 3n(n-1) ] / 2;(其中比上面最优的情况所花的时间就是在于交换元素的三个步骤);所以最差的情况下时间复杂度为:O( n^2 );
综上所述:
最优的时间复杂度为:O( n^2 ) ;有的说 O(n),下面会分析这种情况;
最差的时间复杂度为:O( n^2 );
平均的时间复杂度为:O( n^2 );
空间复杂度
空间复杂度就是在交换元素时那个临时变量所占的内存空间;
最优的空间复杂度就是开始元素顺序已经排好了,则空间复杂度为:0;
最差的空间复杂度就是开始元素逆序排序了,则空间复杂度为:O(n);
平均的空间复杂度为:O(1);

1、时间复杂度:

(1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
(2)时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
说人话:举例来

for (i=1; i<=n; i++)
   x++;
  for (i=1; i<=n; i++)
   for (j=1; j<=n; j++)
   x++;

第一个for循环的时间复杂度为Ο(n),第二个for循环的时间复杂度为Ο(n2),则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。
再来一个例子:

解: 语句1的频度是1,
设语句2的频度是f(n), 则:2^f(n)<=n; f(n)<=log2n
取最大值f(n)=log2n,
T(n)=O(log2n )
这下应该明白时间复杂度怎么求了吧。。。不会求的直接背也行,记得是一个平均值

封装类型

Java语言按照错误严重性,从throwale根类衍生出Error和Exception两大派系
**Error(错误):**程序在执行过程中所遇到的硬件或操作系统的错误。错误对程序而言是致命的,将导致程序无法运行。
常见的错误有内存溢出,jvm虚拟机自身的非正常运行,calss文件没有主方法。
程序本身是不能处理错误的,只能依靠外界干预。
Error是系统内部的错误,由jvm抛出,交给系统来处理。
EXCEPTION(异常):是程序正常运行中,可以预料的意外情况。
比如数据库连接中断,空指针,数组下标越界。
异常出现可以导致程序非正常终止,也可以预先检测,被捕获处理掉,使程序继续运行。
编译异常(可检测)和运行时异常(不可检测)
**编译时异常:**又叫可检查异常,通常时由语法错和环境因素(外部资源)造成的异常。比如输入输出异常IOException,数据库操作SQLException。其特点是,Java语言强制要求捕获和处理所有非运行时异常。通过行为规范,强化程序的健壮性和安全性。
**运行时异常:**又叫不检查异常RuntimeException,这些异常一般是由程序逻辑错误引起的,即语义错。比如算术异常,空指针异常NullPointerException,下标越界IndexOutOfBoundsException。运行时异常应该在程序测试期间被暴露出来,由程序员去调试,而避免捕获。
java语言处理运行时错误有三种方式:
一是程序不能处理的错误,
二是程序应该避免而可以不去捕获的运行时异常,
三是必须捕获的非运行时异常。

5 OutOfMemoryError是哪种异常/h2>

内存溢出异常

操作系统为每个进程分配的内存是具有一定限制性。譬如,32位的操作系统限制为2GB。而当检查出哪个区域出现OutOfMemoryError异常时,需要平衡该进程的某个区域内存大小来解决另一个区域出现内存溢出的情况。例如,在高并发情况下,不断地创建线程可能会使线程私有的虚拟机栈出现内存溢出情况,在不能减少线程数或者更换更大位数的操作系统时,就只能通过减少最大堆和减少栈容量的方式来解决虚拟机栈导致的内存溢出。所以,无论在处理异常或者是实验,我们都要学会调整设置虚拟机启动参数
以下为了解内容

1、Java堆溢出原因及其解决方案

Java堆用于存储对象实例和数组的,只要不断地创建对象或者数组,并且保证GC Roots到对象之间有可达的路径来避免垃圾回收机制清除这些对象,那么在对象数量达到最大堆的容量限制后就会产生内存溢出异常。
要了解Java堆内存可能溢出原因,首先我们要知道当生成新对象时,向Java堆申请内存的过程:
① JVM先尝试在Eden区(Young区包括1个Eden和2个survivor)分配新建对象所需要的内存;
② 如果内存大小足够,则申请结束。反之,执行下一步;

原文链接:https://blog.csdn.net/qq_41285600/article/details/82798920
解决方案:
Java堆出现内存溢出异常有两种解决方案。一种是基于内存调整来改变堆区内存大小以便能够存储更多的对象,但堆内存受到物理内存的限制,当出现无法再扩展堆内存的情况时,就采用第二种方式,从代码上检查是否存在某些对象的生命周期过长、持有状态时间过长的情况,尝试减少程序在运行期的内存消耗。

2、虚拟机栈和本地方法栈溢出

虚拟机栈和本地方法栈的内存分布在不同的虚拟机上是有差别的。例如,在HotSpot上是将虚拟机栈和本地方法栈合二为一的。虽然有-Xoss参数用于设置本地方法栈,但实际上是无效的,栈容量只由-Xss参数设定。关于虚拟机栈和本地方法栈,在Java虚拟机规范中描述了两种异常:①如果线程请求的栈深度大于虚拟机所允许的最大栈深度,将抛出StackOverflowError异常。②如果虚拟机在扩展栈时无法申请到足够的空间,则抛出OutOfMemoryError异常。
导致这两种异常的原因是有一定区别的。虚拟机栈是线程私有的,它存储的是存放着局部变量表、操作数栈、动态链接以及方法出口等信息的栈帧,当前线程每执行一个方法时,实际上都对应着一个栈帧在虚拟机栈中出栈到入栈的过程,而当这个线程执行方法较多时,创建的栈帧也会随之越来越多,而虚拟机栈内存是受到了JVM总体内存的一个分布限制,一旦栈帧较多时,可能就会出现栈满溢出异常,也就是StackOverflowError异常。而出现OutOfMemoryError异常的情况是相对于多线程环境下而言的,一旦线程数量过多,并且都没有即使回收,从而会不断地申请内存给虚拟机栈,从而导致在扩展栈时无法申请到足够的空间,出现OutOfMemoryError异常。当然,OutOfMemoryError异常也可能出现在单钱程的情况下。当为一个线程设置虚拟机栈内存大小与其它区内存之和大于JVM所允许的最大内存,就可能出现OutOfMemoryError异常。

3、方法区和运行时常量池溢出

在jdk1.7之前,运行时常量池属于方法区的一部分,也就是运行时常量池处于永久代。而方法区出现的内存溢出异常经常是由运行时常量池内存溢出异常所导致的。但在jdk1.7时,为了消除永久代,常量池位置发生了一定的变化,由原来的方法区转移到了堆区,但永久代实际上还是存在的,因为内加载机制还在永久代。我们也知道,堆区是GC管理的主要区域,而常量池存储了该类的所有常量,如果使其处于永久代不进行及时的回收,导致内存溢出可能会是经常的。放入堆区个人理解就是为了方便及时合理回收运行时常量池。在jdk1.8之后,完全消除永久代这一个区域,jvm将方法区放入了一个与堆不相连的区域,该区域称为元空间(元空间介绍引用:https://www.cnblogs.com/duanxz/p/3520829.html)。

4、本机直接内存溢出

本机直接内存容量可以通过-XX:MaxDirectMemorySize指定,如果不指定,则默认与Java堆最大值(-Xmx制定)一样。NIO提供了一个不经过JVM直接访问本机物理内存的类——DirectMemory。DircetMemory继承与ByteBuffer,但和普通的ByteBuffer不同,普通的ByteBuffer在堆上进行内存分配,其最大的内存受到堆内存的限制。而DircetMemory是向本机物理内存申请内存分配,所以其大小只受物理内存的限制。由于直接内存是介于堆区和操作系统之间的一个Buffer,所以读写操作比普通的Buffer要快,同样也造成创建和销毁较普通Buffer慢的特点。以下代码清单中直接越过DircetByteBuffer(存储在Java堆上的操作直接内存的一个对象引用)类,直接通过反射获取unsafe实例进行内存分配。因为虽然使用了DircetByteBuffer分配内存也会抛出内存溢出异常,但它抛出异常时并没有真正向操作系统申请分配内存,而是通过计算得知内存无法分配,于是手动抛出异常,真正申请分配内存的方法是unsafe.allocateMemory()。

6、Hashmap、Hashtable、ConcurrentHashmap的原理和区别

HashTable

底层数组+链表实现,无论key还是value都不能为null,线程安全,实现线程安全的方式是在修改数据时锁住整个HashTable,效率低,ConcurrentHashMap做了相关优化
初始size为11,扩容:newsize = olesize*2+1
计算index的方法:index = (hash & 0x7FFFFFFF) % tab.length

HashMap

底层数组+链表实现,可以存储null键和null值,线程不安全
初始size为16,扩容:newsize = oldsize*2,size一定为2的n次幂
扩容针对整个Map,每次扩容时,原来数组中的元素依次重新计算存放位置,并重新插入
插入元素后才判断该不该扩容,有可能无效扩容(插入后如果扩容,如果没有再次插入,就会产生无效扩容)
当Map中元素总数超过Entry数组的75%,触发扩容操作,为了减少链表长度,元素分配更均匀
计算index方法:index = hash & (tab.length – 1)

ConcurrentHashMap

底层采用分段的数组+链表实现,线程安全
通过把整个Map分为N个Segment,可以提供相同的线程安全,但是效率提升N倍,默认提升16倍。(读操作不加锁,由于HashEntry的value变量是 volatile的,也能保证读取到最新的值。)
Hashtable的synchronized是针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术
有些方法需要跨段,比如size()和containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁
扩容:段内扩容(段内元素超过该段对应Entry数组长度的75%触发扩容,不会对整个Map进行扩容),插入前检测需不需要扩容,有效避免无效扩容

汇总:华为通用软件面试基础问题(java)(最新)

锁分段技术:

首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。
ConcurrentHashMap提供了与Hashtable和SynchronizedMap不同的锁机制。Hashtable中采用的锁机制是一次锁住整个hash表,从而在同一时刻只能由一个线程对其进行操作;而ConcurrentHashMap中则是一次锁住一个桶。
ConcurrentHashMap默认将hash表分为16个桶,诸如get、put、remove等常用操作只锁住当前需要用到的桶。这样,原来只能一个线程进入,现在却能同时有16个写线程执行,并发性能的提升是显而易见的。

6、java的锁机制分类

6.1自旋锁

自旋锁原理非常简单,如果持有锁的线程能在很短时间内释放锁资源,那么那些等待竞争锁的线程就不需要做内核态和用户态之间的切换进入阻塞挂起状态,它们只需要等一等(自旋),等持有锁的线程释放锁后即可立即获取锁,这样就避免用户线程和内核的切换的消耗。

6.2 偏向锁

偏向锁,顾名思义,它会偏向于第一个访问锁的线程,如果在运行过程中,同步锁只有一个线程访问,不存在多线程争用的情况,则线程是不需要触发同步的,这种情况下,就会给线程加一个偏向锁。

6.3 轻量级锁

轻量级锁是由偏向所升级来的,偏向锁运行在一个线程进入同步块的情况下,当第二个线程加入锁争用的时候,偏向锁就会升级为轻量级锁;其他线程会通过自旋的形式尝试获取锁,不会阻塞,提高性能。

6.4 重量级锁Synchronized

当作用于静态方法时,锁住的是Class实例,又因为Class的相关数据存储在永久带PermGen(jdk1.8则是metaspace),永久带是全局共享的,因此静态方法锁相当于类的一个全局锁,会锁所有调用该方法的线程

7、Synchronized有多少种用法方法和锁代码块哪种比较好说过锁类和锁实例么/h2>

7.1、同步普通方法(锁实例对象)

这个也是我们用得最多的,只要涉及线程安全,上来就给方法来个同步锁。这种方法使用虽然最简单,但是只能作用在单例上面,如果不是单例,同步方法锁将失效。

此时,同一个实例只有一个线程能获取锁进入这个方法。

7.2、同步静态方法(锁类本身)

同步静态方法,不管你有多少个类实例,同时只有一个线程能获取锁进入这个方法。

同步静态方法是类级别的锁,一旦任何一个线程进入这个方法,其他所有线程将无法访问这个类的任何同步类锁的方法。

7.3、同步类(锁类本身)

下面提供了两种同步类的方法,锁住效果和同步静态方法一样,都是类级别的锁,同时只有一个线程能访问带有同步类锁的方法。

这里的两种用法是同步块的用法,这里表示只有获取到这个类锁才能进入这个代码块。

7.4、同步this实例(锁实例对象)

这也是同步块的用法,表示锁住整个当前对象实例,只有获取到这个实例的锁才能进入这个方法。

声明:本站部分文章及图片源自用户投稿,如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢!

上一篇 2020年3月23日
下一篇 2020年3月23日

相关推荐