• 八股文第八天


    时间:2022年7月29日
    今天就不继续往下学了,发现前七天背的东西都忘光了,今天复习一下。


    第七天

    Hashmap 的底层原理

    在这里插入图片描述

    在JDK1.8之前,HashMap的底层是数组+链表,在JDK1.8之后是数组+链表/红黑树,如果同一节点的节点数>=8,那么就转为红黑树,如果同一节点的节点数<=6那么就转为单向链表。那读到这里其实大家就会有疑问,为啥元素个数大于8就转为红黑树,小于6就是单向链表 ?

    这里就不得不从hash表说起:学过数据结构的人都知道一个完整的hash表包括hash函数和处理冲突的办法,首先常用的hash函数有:直接定址法(线性函数法)、除留取余法。常用的处理冲突的方法为:开放定址法、链地址法。具体操作我就不详细介绍了,大家可以去百度一下


    那HashMap使用的什么函数跟处理办法呢? HashMap使用的哈希函数是 “扰动函数”,那么是扰动函数呢,有一篇帖子说的很清晰大家可以点击去看看 : 什么是“扰动函数”

    为什么要是它作为哈希函数呢,说白了就是为了增加随机性,让数据元素更加均衡的散列,减少碰撞。那为啥是 8 就转变为红黑树呢,这里就要涉及到泊松分布的概率问题,主要是为了寻找一种时间和空间的平衡,是根据概率统计决定的, 是非常严谨和科学的。 因为发生八次碰撞的概率已经降低到0.00000006 ,同时这里也有一篇文章介绍阈值为8泊松分布概率:泊松分布来解释为什么HashMap的链表变树的阈值是8
    在这里插入图片描述
    这几乎已经是不可能的事件,如果真的碰撞发生了 8 次,那么这个时候说明由于元素本身和hash函数的原因,此次操作的hash碰撞的可能性非常大了,后序可能还会继续发生hash碰撞,为了更好的查找性能。所以,这个时候,就应该将链表转换为红黑树了( 其实实际中转化为红黑树的概率很小),那为啥红黑树转为链表的阈值是 6 呢,不是 8,7。 如果也将该阈值设置于8,那么当hash碰撞在8时,会反生链表和红黑树的不停相互激荡转换,白白浪费资源。中间有个差值7可以防止链表和树之间的频繁转换,假设一下:如果设计成链表个数超过8则链表转换成树结构,链表个数小于8则树结构转换成链表,如果HashMap不停的插入,删除元素,链表个数在8左右徘徊,就会频繁的发生红黑树转链表,链表转红黑树,效率会很低下。


    • 当 new HashMap(): 底层没有创建数组,首次调用 put()方法时,底层创建长度为 16 的数组,jdk8 底层的数组是:Node[],而非 Entry[],用数组容量大小乘以加载因子得到一个值,一旦数组中存储的元素个数超过该值就会调用 rehash 方法将数组容量增加到原的两倍,专业术语叫做扩容,在做扩容的时候会生成一个新的数组,原来的所有数据需要重新计算哈希码值重新分配到新的数组,所以扩容的操作非常消耗性能。
      默认的负载因子大小为 0.75,数组大小为 16。也就是说,默认情况下,那么当 HashMap 中元素个数超过 160.75=12 的时候,就把数组的大小扩展为 216=32,即扩大一倍。
    • 在我们 Java 中任何对象都有 hashcode,hash 算法就是通过 hashcode 与自己进 行向右位移 16 的异或运算。这样做是为了计算出来的 hash 值足够随机,足够分散,还有 产生的数组下标足够随机,

    map.put(k,v)实现原理

    (1)首先将 k,v 封装到 Node 对象当中(节点)。

    (2)先调用 k 的 hashCode()方法得出哈希值,并通过哈希算法转换成数组的标。

    (3)下标位置上如果没有任何元素,就把 Node 添加到这个位置上。如果说下标对应的位置上有链表。此时,就会拿着 k 和链表上每个节点的 k 进行 equal。如果所有equals 方 法返回都是 false,那么这个新的节点将被添加到链表的末尾。如其中有一个 equals 返回了 true,那么这个节点的 value 将会被覆盖

    map.get(k)实现原理

    (1)、先调用 k 的 hashCode()方法得出哈希值,并通过哈希算法转换成数组的下标。

    (2)、在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有,则返回 null。如果这个位置上有单向链表,那么它就会拿着参数 K 和单向链表上的每一个节点 的 K 进行 equals,如果所有 equals 方法都返回 false,则 get 方法返回 null。如果其中一 个节点的 K 和参数 K 进行 equals 返回 true,那么此时该节点的 value 就是我们要找的 value 了,get 方法最终返回这个要找的 value,Hash 冲突不同的对象算出来的数组下标是相同的这样就会产生 hash 冲突,当单线链表达到一定长度后效率会非低。

    Hashmap 和 hashtable ConcurrentHashMap 区别(高薪常问)

    区别对比一 (HashMap 和 HashTable 区别):

    1、HashMap 是非线程安全的,HashTable 是线程安全的。

    2、HashMap 的键和值都允许有 null 值存在,而 HashTable 则不行。

    3、因为线程安全的问题,HashMap 效率比 HashTable 的要高。

    4、Hashtable 是同步的,而 HashMap 不是。因此,HashMap 更适合于单线程环境,而 Hashtable 适合于多线程环境。一般现在不建议用 HashTable。
    ① 是 HashTable 是遗留类,内部的实现很多没优化和冗余。
    ②即使在多线程环境下, 现在也有同步的 ConcurrentHashMap 替代,没有必要因为是多线程而用 HashTable。

    区别对比二(HashTable 和 ConcurrentHashMap 区别):

    HashTable 使用的是 Synchronized 关键字修饰,ConcurrentHashMap 是 JDK1.7 使用了锁分段技术来保证线程安全的。JDK1.8ConcurrentHashMap 取消了 Segment 分段锁,采用 CAS 和 synchronized 来保证并发安全。数据结构跟 HashMap1.8 的结构类似,数组+链表/红黑二叉树。 synchronized 只锁定当前链表或红黑二叉树的首节点,这样只要 hash 不冲突,就不会产生并发,效率又提升 N 倍。

    第六天

    常见的数据结构:
    数组,栈,队列,链表,树,散列,堆,图等

    在这里插入图片描述

    • 数组是最常用的数据结构,数组的特点是长度固定,数组的大小固定后就无法扩容了 , 数组只能存储一种类型的数据 ,添加,删除的操作慢,因为要移动其他的元素。

    • 栈是一种基于先进后出(FILO)的数据结构,是一种只能在一端进行插入和删除作的特殊线性表。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据 在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。

    • 队列是一种基于先进先出(FIFO)的数据结构,是一种只能在一端进行插入,在另 一端进行删除操作的特殊线性表,它按照先进先出的原则存储数据,先进入的数据,在读取 数据时先被读取出来。

    • 链表是一种物理存储单元上非连续、非顺序的存储结构,其物理结构不能只表示数 据元素的逻辑顺序,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

    • 链表由一系 列的结节(链表中的每一个元素称为结点)组成,结点可以在运行时动态生成。根据指针的 指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等。

    • 树是我们计算机中非常重要的一种数据结构,同时使用树这种数据结构,可以描述 现实生活中的很多事物,例如家谱、单位的组织架构等等。有二叉树、平衡树、红黑树、B 树、B+树。

    • 散列表,也叫哈希表,是根据关键码和值 (key 和 value) 直接进行访问的数据结构, 通过 key 和 value 来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。

    • 堆是计算机学科中一类特殊的数据结构的统称,堆通常可以被看作是一棵完全二叉 树的数组对象。 图的定义:图是由一组顶点和一组能够将两个顶点相连的边组成的

    集合和数组的区别(了解)

    区别:数组长度固定 集合长度可变 数组中存储的是同一种数据类型的元素,可以存储基本数据类型,也可以存储引用数据类型;

    集合存储的都是对象,而且对象的数据类型可以不一致。在开发当中一般当对象较多的时候, 使用集合来存储对象。

    List 和 Map、Set 的区别(必会)
    List 和Set都是单列数据存储,Map是双列数据存储

    1. List是存储的数据有序的,允许值重复。
    2. set是无序的,并且不允许重复,其中元素中集合的位置是由hashcode决定,所以计算结果是固定的,但是这个位置不是用户所能控制的,所以相对于用户来说是无序的
    3. map是无序的且key值不允许重复,但是value允许重复

    List 和 Map、Set 的实现类(必会)
    集合体系
    collection接口:
    set: 无序,唯一包括两个实现类:HashSet和 TreeSet,并且LinkHashSet继承了HashSet.
    4. Set是怎么保证唯一的?
    重写了hashCode和equals方法
    5. linkHashSet底层数据结构为:链表和哈希表 由链表保证有序性,由哈希表保证唯一性
    6. TreeSet底层是红黑树,并且是有序唯一
    1.如何保证元素排序的呢?
    自然排序 比较器排序
    2.如何保证元素唯一性的呢?
    根据比较的返回值是否是 0 来决定

    List: 有序,不唯一
    7. ArrayList:底层为数组,查询快,增删慢,且线程不安全,但效率高
    8. vector:底层为数组,查询快,增删慢,线程安全,但效率低(以舍弃)
    9. LinkedList:底层为链表,查询慢,但是增删快,线程不安全,效率高


    Map接口:

    1. HashMap:线程不安全,高效,支持null值和null键,无序
    2. TreeMap:能够对键值进行排序,默认是升序
      TreeMap
    3. LinkedHashMap:线程不安全,是hashmap的一个子类,记录的插入的顺序
      LinkedHashMap

    第五天

    同步锁、死锁、乐观锁、悲观锁 (高薪常问):

    1. 同步锁:当多个线程访问同一个数据时,很容易出现问题,为了避免出现这种情况,我们要保证在同一时间只能有一个线程进行访问,在java中使用synchronized关键字来取得一个同步锁对象

    2. 死锁:多个线程同时被堵塞,他们中的一个或者多个都在等在资源的释放。

    3. 乐观锁:总是假设最好的情况,每次去访问数据都会认为没有修改操作,但是在更新的时候回去判断一下有没有更新这个数据,可以使用版本号和CAS算法实现。乐观锁适用于多读的情况,可以提高效率,类如数据库中的write_ condition机制就是由乐观锁实现的

    4. 悲观锁:总是假设最坏的情况,每次去访问数据都会认为别人会修改,所以每次拿数据都会上锁,在传统的关系型数据库中就有很多这种锁机制如:行锁、写锁、读锁等,在java在的独占锁也是悲观锁的思想实现的。

    说一下 synchronized 底层实现原理?(高薪常问)
    synchronized可以保证在同一时间,只有一个方法进入临界区,同时还可以保证共享数据的内存的可见性
    java中每个对象都可以作为锁如:
    普通同步方法:锁的是当前实例对象
    静态同步方法:锁的是当前class类
    同步方法块:锁的是括号里的对象

    synchronized 和 volatile 的区别是什么?(高薪常问)
    volatile 本质是在告诉 jvm 当前变量在寄存器(工作内存)中的值是不确定的,需要从主存中读取; synchronized 则是锁定当前变量,只有当前线程可以访问该变量,其他线程被阻塞住。
    volatile关键字可以作用于成员变量
    作用:
    可以解决可见性和有序性问题

    1. volatile 仅能使用在变量级别,synchronized 则可以使用在变量、方法、和类级别的。
    2. volatile 仅能实现变量的修改可见性,不能保证原子性;而 synchronized 则可以保证变量的修改可见性和原子性。
    3. volatile 不会造成线程的阻塞;synchronized 可能会造成线程的阻塞。
    4. volatile 标记的变量不会被编译器优化;synchronized 标记的变量可以被编译器优化。

    synchronized 和 Lock 有什么区别? (高薪常问)

    1. synchronized是关键字,Lock是一个类。
    2. synchronized不能判断锁的状态,Lock可以判断是否获取次锁
    3. synchronized可以自动释放,Lock需要调用unlock()方法
    4. synchronized如果前一个线程不肯释放锁,那他的后一个就会一直等下去,但是Lock不会一直等下去,如果尝试获取不到锁,线程会结束。
    5. synchronized 的锁可重入、不可中断、非公平,而 Lock 锁可重入、可判断、可公平 (两者皆可); Lock 锁适合大量同步的代码的同步问题,synchronized 锁适合代码少量的同步问题

    第四天

    Java 的异常(必会)

    Java 的异常关系
    Throwable 是所有 Java 程序中错误处理的父类,有两种类:Error 和 Exception。

    Error:表示由 JVM 所侦测到的无法预期的错误,由于这是属于 JVM 层次的严重错误,导致 JVM 无法继续执行,因此,这是不可捕捉到的,无法采取任何恢复的操作,顶多只能显示错误信息

    Exception:表示可恢复的例外,这是可捕捉到的

    1.运行时异常:
    都是 RuntimeException 类及其子类异常,如 NullPointerException(空指针异常)、IndexOutOfBoundsException(下标越界异常)等, 这些异常是不检查异常,程序中可以选择捕获处理,也可以不处理。这些异常一般是由程序逻辑错误引起的,程序应该从逻辑角度尽可能避免这类异常的发生。运行时异常的特点是 Java 编译器不会检查它,也就是说,当程序中可能出现这类异常,即使没有用 try-catch 语句捕获它,也没有用throws 子句声明抛出它,也会编译通过.

    常见的 RunTime 异常几种如下:
    NullPointerException - 空指针引用异常
    ClassCastException - 类型强制转换异常。
    IllegalArgumentException - 传递非法参数异常。
    ArithmeticException - 算术运算异常
    ArrayStoreException - 向数组中存放与声明类型不兼容对象异常
    IndexOutOfBoundsException - 下标越界异常
    NegativeArraySizeException - 创建一个大小为负数的数组错误异常
    NumberFormatException - 数字格式异常
    SecurityException - 安全异常
    UnsupportedOperationException - 不支持的操作异常

    2.非运行时异常(编译异常):

    是 RuntimeException 以外的异常,类型上都属于 Exception 类及其子类。从程序语法角度讲是必须进行处理的异常,如果不处理,程序就不能编译通过。 如 IOException、SQLException 等以及用户自定义的 Exception 异常,一般情况下不自定义检查异常。

    BIO、NIO、AIO 有什么区别?(高薪常问)
    BIO:Block IO 同步阻塞式 IO,就是我们平常使用的传统 IO,它的特点是模式简单使用方便,并发处理能力低。

    NIO:New IO 同步非阻塞 IO,是传统 IO 的升级,客户端和服务器端通过 Channel(通道)通讯,实现了多路复用。有三大核心部分:Channel(通道)、Buffer(缓冲区)、Selector(选择器),如Buffer缓冲数组

    通道、缓冲区、选择器

    AIO:Asynchronous IO 是 NIO 的升级,也叫 NIO2,实现了异步非堵塞 IO , 异步 IO 的操作基于事件和回调机制,即可以理解为read/write方法都是异步的。
    这里有一篇详细介绍NIO,BIO,AIO可以看看

    ThreadLocal 的原理(高薪常问)

    ThreadLocal:为共享变量在每个线程中创建一个副本,每个线程都可以访问自己内部的副本变量。通过 threadlocal 保证线程的安全性。

    其实在 ThreadLocal 类中有一个静态内部类 ThreadLocalMap(其类似于 Map), 用键值对的形式存储每一个线程的变量副本,ThreadLocalMap 中元素的 key 为当前 ThreadLocal 对象,而 value 对应线程的变量副本。

    ThreadLocal 本身并不存储值,它只是作为一个 key 保存到 ThreadLocalMap 中,但是这里要注意的是它作为一个 key 用的是弱引用,因为没有强引用链,弱引用在 GC 的时候可能会被回收。这样就会在 ThreadLocalMap 中存在一些 key 为 null 的键值对 (Entry)。因为 key 变成 null 了,我们是没法访问这些 Entry 的,但是这些 Entry 本身是不会被清除的。如果没有手动删除对应 key 就会导致这块内存即不会回收也无法访问,也就是内存泄漏。 使用完后ThreadLocal ,记得调用 remove 方法。
    在不使用线程池的前提下, 即使不调用 remove 方法,线程的"变量副本"也会被 gc 回收,即不会造成内存泄漏的情况。

    第三天

    反射(了解):
    在 Java 中的反射机制是指在运行状态中,对于任意一个类都能够知道这个类所有的属性和方法;并且对于任意一个对象,都能够调用它的任意一个方法;这种动态获取信息以及动态调用对象方法的功能成为 Java 语言的反射机制。

    获取 Class 对象的 3 种方法 :
    ​ 1.使用类名调用.class属性(.class不是只有类能调用)
    ​ 2.使用一个类的对象调用.getClass()方法
    ​ 3.使用Class类的静态方法forName(“类全名”),最安全/性能最好

    public class Demo01 {
        public static void main(String[] args) throws ClassNotFoundException {
            //获取字节码对象三个方式
    
            //​	1.使用类名调用.class属性(.class不是只有类能调用)
            Class c1 = String.class;
    
            //​	2.使用一个类的对象调用.getClass()方法
            Class c2 = "abc".getClass();
    
            //​	3.使用Class类的静态方法forName("类全名")
            Class c3 = Class.forName("java.lang.String");
    
            System.out.println(c1 == c2);
            System.out.println(c2 == c3);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    jdk1.8 的新特性(高薪常问)

    1. Lambda 表达式
    2. 方法引用
      如果lambda表达式里面只有一行代码,且这一行代码是调用了一个已经存在的方法 我们自己没有写任何其他代码逻辑,就可以使用方法引用,做进一步简化
    3. 函数式接口
    4. 接口允许定义默认方法和静态方法
      jdk出现默认方法和静态方法的作用
    5. Stream API
    6. 日期/时间类改进
    7. Optional 类
    8. Java8 Base64 实现

    第二天

    String,StingBuff,StringBuilder区别
    String是字符串常量
    StringBuffer是字符串变量(线程安全)
    StringBuilder 字符串变量(非线程安全)
    (详细请看第二天文章)

    小结:
    (1)如果要操作少量的数据用 String;
    (2)多线程操作字符串缓冲区下操作大量数据用 StringBuffer;
    (3)单线程操作字符串缓冲区下操作大量数据用 StringBuilder。

    接口和抽象类的区别是什么?(必会)

    实现:抽象类的子类使用 extends 来继承,接口必须使用 implements 来实现接口。

    构造函数:抽象类可以有构造函数;接口不能有。

    main 方法:抽象类可以有 main 方法,并且我们能运行它;接口不能有 main 方法。

    实现数量:类可以实现很多个接口;但是只能继承一个抽象类。

    访问修饰符:接口中的方法默认使用 public 修饰;抽象类中的方法可以是任意访问修饰符。

    string 常用的方法有哪些?
    indexOf():返回指定字符的索引。
    charAt():返回指定索引处的字符。
    replace():字符串替换。
    trim():去除字符串两端空白。
    split():分割字符串,返回一个分割后的字符串数组。
    getBytes():返回字符串的
    byte 类型数组。
    length():返回字符串长度。
    toLowerCase():将字符串转成小写字母。
    toUpperCase():将字符串转成大写字符。
    substring():截取字符串。
    equals():字符串比较。

    什么是单例模式?有几种?

    单例模式:某个类的实例在 多线程环境下只会被创建一次出来。
    单例模式有饿汉式单例模式、懒汉式单例模式和双检锁单例模式,枚举。

    第一天

    面向对象的特征:
    面向对象的特征:封装、继承、多态、抽象。

    封装:就是把对象的属性和行为(数据)结合为一个独立的整体,并尽可能隐藏对象的内部实现细节,就是把不想告诉或者不该告诉别人的东西隐藏起来,把可以告诉别人的 公开,别人只能用我提供的功能实现需求,而不知道是如何实现的。增加安全性。

    继承:子类继承父类的数据属性和行为,并能根据自己的需求扩展出新的行为,提高了代码的复用性。

    多态:指允许不同的对象对同一消息做出相应相应,一个对象的多种形态。即同一消息可以根据发送对象的不同而采用多种不同的行为方式(发送消息就是函数调用)。封装和继承几乎都是为多态而准备的,在执行期间判断引用对象的实际类型,根据其实际的类型调用其相应的方法。

    抽象:表示对问题领域进行分析、设计中得出的抽象的概念,是对一系列看上去不同, 但是本质上相同的具体概念的抽象。在 Java 中抽象用 abstract 关键字来修饰,用 abstract 修饰类时,此类就不能被实例化,从这里可以看出,抽象类(接口)就是为了继承而存在的。

    JDK JRE JVM 的区别 (必会)

    JDK(Java Development Kit)是整个 Java 的核心,是 java 开发工具包,包括了 Java 运行环境 JRE、Java 工具和 Java 基础类库。

    JRE(Java Runtime Environment)是运行 JAVA 程序所必须的环境的集合,包 含 java 虚拟机和 java 程序的一些核心类库。

    JVM 是 Java Virtual Machine(Java 虚拟机)的缩写,是整个 java 实现跨平台的最核心的部分,能够运行以 Java 语言写作的软件程序。

    重载和重写的区别(必会)

    重载: 发生在同一个类中,方法名必须相同,参数类型不同.个数不同.顺序不同, 方法返回值和访问修饰符可以不同,发生在编译时。

    重写: 发生在父子类中,方法名、参数类型必须相同,返回值范围小于等于父类, 抛出的异常范围小于等于父类, 访问修饰符范围大于等于父类;如果父类方法访问修饰符为 private 则子类就不能重写该方法。

    Java 中==和 equals 的区别(必会)

    == 的作用:
    基本类型:比较的就是值是否相同
    引用类型:比较的就是地址值是否相同
    equals 的作用:
    引用类型:默认情况下,比较的是地址值。 特:String、Integer、Date 这些类库中 equals 被重写,比较的是内容而不是地址!

    面试题:请解释字符串比较之中 == 和 equals() 的区别?
    答:
    == :比较的是两个字符串内存地址(堆内存)的数值是否相等,属于数值比较;
    equals():比较的是两个字符串的内容,属于内容比较

  • 相关阅读:
    中国智能客服发展历程
    Bootstrap5 表单
    Linux 6种日志查看方法
    Python---练习:判断是否为一个合法三角形(if else)
    Kamailio不被重视的模块:nat_traversal
    ps gif动图怎么做,教你一招更简单
    webpack笔记(一)
    OCP安装定制文件准备
    2022_08_10_106期__二叉树
    NetSuite Account Register报表详解
  • 原文地址:https://blog.csdn.net/weixin_44233087/article/details/126047541