目录
八:Arrays.sort和 Collections.sort的实现原理和区别
前言:
在面试中有项目的询问环节,本文主要是对八股进行复盘解析
一:list和set区别
List , Set 都是继承自 Collection 接口 List 特点:元素有放入顺序,元素可重复 , Set 特点:元素无放入顺序,元素不可重复,重复元素会覆盖掉,(元素虽然无放入顺序,但是元素在set中的位 置是有该元素的 HashCode 决定的,其位置其实是固定的,加入Set 的 Object 必须定义 equals ()方法 ,另外list 支持for循环,也就是通过下标来遍历,也可以用迭代器,但是set只能用迭代,因为他无序,无法用下标来取得想 要的值。) Set和List对比 Set:检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变。 List:和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他元素位置改变
二:HashSet是如何保证元素不重复
向 HashSet 中 add ()元素时,判断元素是否存在的依据,不仅要比较hash值,同时还要结合 equles 方法比较。 HashSet 中的 add ()方法会使用 HashMap 的 add ()方法。
HashMap 的 key 是唯一的,由以下的代码可以看出 HashSet 添加进去的值就是作为 HashMap 的key。所以不会 重复( HashMap 比较key是否相等是先比较 hashcode 在比较 equals )
以下是Hashset得源码:
private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
三:HashMap是线程安全的吗?为什么 线程不安全
首先HashMap不是线程安全的; 如果有两个线程A和B,都进行插入数据,刚好这两条不同的数据经过哈希计算后得到的哈希码是一样的,且该位 置还没有其他的数据。所以这两个线程都会进入我在上面标记为1的代码中。假设一种情况,线程A通过if判断,该 位置没有哈希冲突,进入了if语句,还没有进行数据插入,这时候 CPU 就把资源让给了线程B,线程A停在了if语句 里面,线程B判断该位置没有哈希冲突(线程A的数据还没插入),也进入了if语句,线程B执行完后,轮到线程A执 行,现在线程A直接在该位置插入而不用再判断。这时候,你会发现线程A把线程B插入的数据给覆盖了。发生了线 程不安全情况。本来在 HashMap 中,发生哈希冲突是可以用链表法或者红黑树来解决的,但是在多线程中,可能 就直接给覆盖了。
四:HashMap的扩容机制
当向容器添加元素的时候,会判断当前容器的元素个数,如果大于等于阈值,即当前数组的长度乘以加载因子的值的时候,就要自动扩容啦。 扩容( resize )就是重新计算容量,向 HashMap 对象里不停的添加元素,而 HashMap 对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。当然 Java 里的数组是无法自动扩的,方法是使用一个新的数组代替已有的容量小的数组,就像我们用一个小桶装水,如果想装更多的水,就得换大水桶。
五:HashMap在1.7和1.8有啥区别
在 JDK1.7 及之前的版本中, HashMap 又叫散列链表:基于一个数组以及多个链表的实现,hash值冲突的时候, 就将对应节点以链表的形式存储。 JDK1.8 中,当同一个hash值( Table 上元素)的链表节点数不小于8时,将不再以单链表的形式存储了,会被 调整成一颗红黑树。这就是 JDK7 与 JDK8 中 HashMap 实现的最大区别。
jdk1.7:
使用一个 Entry 数组来存储数据,用key的 hashcode 取模来决定key会被放到数组里的位置,如果 hashcode 相 同,或者 hashcode 取模后的结果相同( hash collision ),那么这些 key 会被定位到 Entry 数组的同一个 格子里,这些 key 会形成一个链表。 在 hashcode 特别差的情况下,比方说所有key的 hashcode 都相同,这个链表可能会很长,那么 put/get 操作 都可能需要遍历这个链表,也就是说时间复杂度在最差情况下会退化到 O(n)
jdk1.8:使用一个 Node 数组来存储数据,但这个 Node 可能是链表结构,也可能是红黑树结构 如果插入的 key 的 hashcode 相同,那么这些key也会被定位到 Node 数组的同一个格子里。 如果同一个格子里的key不超过8个,使用链表结构存储。 如果超过了8个,那么会调用 treeifyBin 函数,将链表转换为红黑树。 那么即使 hashcode 完全相同,由于红黑树的特点,查找某个特定元素,也只需要O(log n)的开销 也就是说put/get的操作的时间复杂度最差只有 O(log n) 听起来挺不错,但是真正想要利用 JDK1.8 的好处,有一个限制: key的对象,必须正确的实现了 Compare 接口 如果没有实现 Compare 接口,或者实现得不正确(比方说所有 Compare 方法都返回0) 那 JDK1.8 的 HashMap 其实还是慢于 JDK1.7 的
六:对象的四种引用
强引用 只要引用存在,垃圾回收器永远不会回收
Object obj = new Object(); User user=new User();
可直接通过obj取得对应的对象 如 obj.equels(new Object()); 而这样 obj 对象对后面 new Object 的一个强 引用,只有当 obj 这个引用被释放之后,对象才会被释放掉,这也是我们经常所用到的编码形式。
软引用 非必须引用,内存溢出之前进行回收,可以通过以下代码实现Object obj = new Object(); SoftReference<Object> sf = new SoftReference<Object>(obj); obj = null; sf.get();//有时候会返回null
这时候sf是对obj的一个软引用,通过sf.get()方法可以取到这个对象,当然,当这个对象被标记为需要回收的对象 时,则返回null; 软引用主要用户实现类似缓存的功能,在内存足够的情况下直接通过软引用取值,无需从繁忙的 真实来源查询数据,提升速度;当内存不足时,自动删除这部分缓存数据,从真正的来源查询这些数据。
弱引用 第二次垃圾回收时回收,可以通过如下代码实现Object obj = new Object(); WeakReference<Object> wf = new WeakReference<Object>(obj); obj = null; wf.get();//有时候会返回null wf.isEnQueued();//返回是否被垃圾回收器标记为即将回收的垃圾
弱引用是在第二次垃圾回收时回收,短时间内通过弱引用取对应的数据,可以取到,当执行过第二次垃圾回收时, 将返回null。弱引用主要用于监控对象是否已经被垃圾回收器标记为即将回收的垃圾,可以通过弱引用的 isEnQueued 方法返回对象是否被垃圾回收器标记。 ThreadLocal 中有使用到弱引用
public class ThreadLocal<T> { static class ThreadLocalMap { static class Entry extends WeakReference<ThreadLocal<?>> { /** The value associated with this ThreadLocal. */ Object value; Entry(ThreadLocal<?> k, Object v) { super(k); value = v; } } //.... } //..... }
虚引用 垃圾回收时回收,无法通过引用取到对象值,可以通过如下代码实现Object obj = new Object(); PhantomReference<Object> pf = new PhantomReference<Object>(obj); obj=null; pf.get();//永远返回null pf.isEnQueued();//返回是否从内存中已经删除
虚引用是每次垃圾回收的时候都会被回收,通过虚引用的get方法永远获取到的数据为null,因此也被成为幽灵引 用。虚引用主要用于检测对象是否已经从内存中删除。
七: 获取反射的三种方法
1.通过new对象实现反射机制 2.通过路径实现反射机制 3.通过类名实现反射机制
public class Student { private int id; String name; protected boolean sex; public float score; } public class Get { //获取反射机制三种方式 public static void main(String[] args) throws ClassNotFoundException { //方式一(通过建立对象) Student stu = new Student(); Class classobj1 = stu.getClass(); System.out.println(classobj1.getName()); //方式二(所在通过路径-相对路径) Class classobj2 = Class.forName("fanshe.Student"); System.out.println(classobj2.getName()); //方式三(通过类名) Class classobj3 = Student.class; System.out.println(classobj3.getName()); } }
八:Arrays.sort和 Collections.sort的实现原理和区别
Collection和Collections区别
java.util.Collection 是一个集合接口。它提供了对集合对象进行基本操作的通用接口方法。 java.util.Collections 是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、 线程安全等操作。 然后还有混排(Shuffling)、反转(Reverse)、替换所有的元素(fill)、拷贝(copy)、返 回Collections中最小元素(min)、返回Collections中最大元素(max)、返回指定源列表中最后一次出现指定目 标列表的起始位置( lastIndexOfSubList )、返回指定源列表中第一次出现指定目标列表的起始位置 ( IndexOfSubList )、根据指定的距离循环移动指定列表中的元素(Rotate); 事实上Collections.sort方法底层就是调用的array.sort方法
public static void sort(Object[] a) { if (LegacyMergeSort.userRequested) legacyMergeSort(a); else ComparableTimSort.sort(a, 0, a.length, null, 0, 0); } //void java.util.ComparableTimSort.sort() static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) { assert a != null && lo >= 0 && lo <= hi && hi <= a.length; int nRemaining = hi - lo; if (nRemaining < 2) return; // Arrays of size 0 and 1 are always sorted // If array is small, do a "mini-TimSort" with no merges if (nRemaining < MIN_MERGE) { int initRunLen = countRunAndMakeAscending(a, lo, hi); binarySort(a, lo, hi, lo + initRunLen); return; } }
legacyMergeSort (a):归并排序 ComparableTimSort.sort() : Timsort 排序 Timsort 排序是结合了合并排序(merge sort)和插入排序(insertion sort)而得出的排序算法
Timsort的核心过程:TimSort 算法为了减少对升序部分的回溯和对降序部分的性能倒退,将输入按其升序和降序特点进行了分 区。排序的输入的单位不是一个个单独的数字,而是一个个的块-分区。其中每一个分区叫一个run。针对这 些 run 序列,每次拿一个 run 出来按规则进行合并。每次合并会将两个 run合并成一个 run。合并的结果保 存到栈中。合并直到消耗掉所有的 run,这时将栈上剩余的 run合并到只剩一个 run 为止。这时这个仅剩的 run 便是排好序的结果。
九:数组在内存中是如何分配的
对于 Java 数组的初始化,有以下两种方式
静态初始化:初始化时由程序员显式指定每个数组元素的初始值,由系统决定数组长度,如:
//只是指定初始值,并没有指定数组的长度,但是系统为自动决定该数组的长度为4
String[] computers = {"Dell", "Lenovo", "Apple", "Acer"}; //①
//只是指定初始值,并没有指定数组的长度,但是系统为自动决定该数组的长度为3
String[] names = new String[]{"多啦A梦", "大雄", "静香"}; //②
动态初始化:初始化时由程序员显示的指定数组的长度,由系统为数据每个元素分配初始值,如:
//只是指定了数组的长度,并没有显示的为数组指定初始值,但是系统会默认给数组数组元素分配初始值为null
String[] cars = new String[4]; //③
因为 Java 数组变量是引用类型的变量,所以上述几行初始化语句执行后,三个数组在内存中的分配情况如下图所示:
标签:Object,Java,HashMap,元素,线程,数组,new,某小厂,复盘 From: https://blog.csdn.net/2301_76613040/article/details/142034354由上图可知,静态初始化方式,程序员虽然没有指定数组长度,但是系统已经自动帮我们给分配了,而动态初始化方式,程序员虽然没有显示的指定初始化值,但是因为 Java 数组是引用类型的变量,所以系统也为每个元素分配了初始化值 null ,当然不同类型的初始化值也是不一样的,假设是基本类型int类型,那么为系统分配的初始化值也是对应的默认值0。