07-数组原理(上):帮你梳理眼花缭乱的数组 API
关于本讲内容没有提到的代码及方法,你可以根据自己的兴趣,尝试着实现其中的某个方法。 同时也希望你能够多思考日常工作中都有哪些经常用到的 JS 方法,并且去研究其底层源代码的实现逻辑,找机会自己实现一遍,来整体提升你的 JavaScript 的编程能力和对底层的理解能力。 下一讲我们将会进入一个全新的模块——JS 的异步编程篇,期待你能从中学习到更多的东西。每天进步一点点,加油!
IoC,用白话来讲,就是由容器控制程序之间的关系,而非传统实现中,由程序代码直接操控。这也就是所谓“控制反转”的概念所在:控制权由应用代码中转到了外部容器,控制权的转移,是所谓反转。
因为B树不管叶子节点还是非叶子节点,都会保存数据,这样导致在非叶子节点中能保存的指针数量变少,B+树的飞叶子节点存放的是索引。
判断一种数据结构作为索引的优劣主要是看在查询过程中的磁盘IO渐进复杂度,一个好的索引应该是尽量减少磁盘IO操作次数
1.B树只适合随机检索,而B+树同时支持随机检索和顺序检索
2.B+树空间利用率更高。因为内部节点不存储数据,只存储索引值,因为相比较B树来说,B+树一个节点可以存储更多的索引值,从而使整颗B+树变得更矮,减少了I/O次数,3.磁盘读写代价更低,I/O读写次数是影响索引检索效率的最大因素
4.B+树的查询效率更加稳定。B树搜索有可能会在非叶子节点阶数,约靠近根节点的记录查找时间越短,其性能等价于在关键字全集内做一次二分查找。而在B+树中,顺序检索比较明显,随机检索时,任何关键字的查找都必须走一条从根节点到叶节点的路,所有关键字的查找路径相同,导致每一个关键字的查询效率相当
5.B树在在基于范围查询的操作上的性能没有B+树好,因为B+树的叶子节点使用了指针顺序的链接在一起,只要遍历叶子节点就可以实现整棵树的遍历,相比较B+树来说,由于B树的叶子节点是相互独立的,所以对于范围查询,需要从根节点再次出发查询,增加了磁盘I/O操作次数
6.增删文件(节点)时,效率更高,因为B+树的叶子节点包含了所有关键字,并以有序的链表结构存储,这样可很好提高增删效率
了解HashMap的扩容首先要了解HashMap几个非常重要的常量:
//在每次put之后,会有下面这个判断: hashMap的ReSize不是简单的把长度扩大,而是经过一下两个步骤: 创建一个新的Entry空数组,长度是原hashMap数组的 2 倍; 因为长度变长,Hash的规则也随之改变了。所以要遍历原Entry数组,把所有的Entry重新Hash到新的数组。 至此,HashMap完成了扩容操作。
HashMap在put的时候,插入的元素超过了容量(由负载因子决定)的范围就会触发扩容操作,就是rehash,这个会重新将原数组的内容重新hash到新的扩容数组中,在多线程的环境下,存在同时其他的元素也在进行put操作,如果hash值相同,可能出现同时在同一数组下用链表表示,造成闭环,导致在get时会出现死循环,所以HashMap是线程不安全的。
———————————————————————————————— 实现线程安全的几种方式
3.Hashtable,Hashtable通过对整个表上锁实现线程安全,因此效率比较低
String是final修饰的类,是不可变的,所以是线程安全的。
不可变类的线程都是安全的,因为他们都是只读的
确保线程互斥的访问同步代码
保证共享变量的修改能够及时可见
1、AQS是一个JAVA线程同步的框架。是JDK中很多锁工具的核心实现框架。
2、 在AQS中,维护了一个信号量state和一个线程组成的双向链表队列。其中,这个线程队列,就是用来给线程排队的,而state就像是一个红绿灯,用来控制线程排队或者放行的。 在不同的场景下,有不用的意义。
3、在可重入锁这个场景下,state就用来表示加锁的次数。0标识无锁,每加一次锁,state就加1。释放锁state就减1。
常见的内存管理方式有块式管理,页式管理, 段式管理, 段页式管理。
最近最久未使用 :如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小
1.用一个数组来存储数据,给每一个数据项标记一个访问时间戳,每次插入新数据项的时候,先把数组中存在的数据项的时间戳自增,并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候,将被访问的数据项的时间戳置为0。当数组空间已满时,将时间戳最大的数据项淘汰。
2.利用一个链表来实现,每次新插入数据的时候将新数据插到链表的头部;每次缓存命中(即数据被访问),则将数据移到链表头部;那么当链表满的时候,就将链表尾部的数据丢弃。
3.利用链表和hashmap。当需要插入新的数据项的时候,如果新数据项在链表中存在(一般称为命中),则把该节点移到链表头部,如果不存在,则新建一个节点,放到链表头部,若缓存满了,则把链表最后一个节点删除即可。在访问数据的时候,如果数据项在链表中存在,则把该节点移到链表头部,否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。
对于第一种方法, 需要不停地维护数据项的访问时间戳,另外,在插入数据、删除数据以及访问数据时,时间复杂度都是O(n)。对于第二种方法,链表在定位数据的时候时间复杂度为O(n)。所以在一般使用第三种方式来是实现LRU算法。
LinkedHashMap底层就是用的HashMap加双链表实现的,而且本身已经实现了按照访问顺序的存储。此外,LinkedHashMap中本身就实现了一个方法removeEldestEntry用于判断是否需要移除最不常读取的数,方法默认是直接返回false,不会移除元素,所以需要重写该方法。即当缓存满后就移除最不常用的数。
字节二面:8月3号(50min)(记不太清了,只写了几个记忆深的问题)
HTTPS 在内容传输的加密上使用的是对称加密,非对称加密只作用在证书验证阶段
非对称加密的加解密效率是非常低的,而 http 的应用场景中通常端与端之间存在大量的交互,非对称加密的效率是无法接受的。
另外:在 HTTPS 的场景中只有服务端保存了私钥,一对公私钥只能实现单向的加密和解密,所以 HTTPS 中内容传输加密采取的是对称加密,而不是非对称加密。
1)验证域名、有效期等信息是否正确:证书上都有包含这些信息,比较容易完成验证;
2)判断证书来源是否合法:每份签发证书都可以根据验证链查找到对应的根证书,操作系统、浏览器会在本地存储权威机构的根证书,利用本地根证书可以对对应机构签发证书完成来源验证
3)判断证书是否被篡改:需要与 CA 服务器进行校验;
以上任意一步都满足的情况下浏览器才认为证书是合法的。
做题:1.手撕单例模式 2.二叉树的Z字型遍历
字节三面:8月5号(45min)
1.1.项目和研究方向全是CV,为什么不去做CV算法要做后端(。。。菜但不想承认)
***是那一层的协议(???)
1.区域传输时,一个区中主DNS服务器从自己本机的数据文件中读取该区的DNS数据信息,而辅助DNS服务器则从区的主DNS服务器中读取该区的DNS数据信息,传输协议是tcp。
2.域名解析时一般返回的内容都不超过512字节,首选的通讯协议是udp。使用udp传输,不用经过TCP三次握手,这样DNS服务器负载更低,响应更快
解析DNS域名 ———————————————————————————————— 1.浏览器查找自己的DNS缓存,如果有直接返回,如果没有进行步骤二
2.操作系统查找自己的DNS缓存,如果有直接返回给浏览器,如果没有进行步骤三
3.操作系统查找自己的本地host文件,如果有返回给浏览器,如果没有则进行步骤四
4.操作系统向本地域名服务器发起请求,查找本地DNS缓存,如果有,返回给操作系统, 然后操作系统返回给浏览器,如果没有进行步骤五
5.操作系统向根域名服务器发起请求得到顶级域名服务器的IP,然后根域名服务器向顶级域名服务器发起请求得到权限域名服务器的IP,顶级域名服务器再向权限域名服务器发起请求得到IP,本地域名服务器返回给操作系统IP,同时将IP缓存起来,操作系统将IP返回给浏览器,同时将IP缓存起来。
1.根据域名到DNS中找到IP 【如第10问】
2.根据IP建立TCP连接(三次握手)
3.连接建立成功发起http请求
4.服务器响应http请求
5.浏览器解析HTML代码并请求html中的静态资源(js,css)
6.关闭TCP连接(四次挥手)
做题:1.二叉树的右视图
所有现代操作系统都使用虚拟内存,使用虚拟的地址取代物理地址,虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存(一个连续完整的地址空间)。这样做的好处是:
1)一个以上的虚拟地址可以指向同一个物理内存地址,
2)虚拟内存空间可大于实际可用的物理地址;
在 Linux 中零拷贝技术主要有 3 个实现思路
用户态直接 I/O:应用程序可以直接访问硬件存储,操作系统内核只是辅助数据传输。
这种方式依旧存在用户空间和内核空间的上下文切换,硬件上的数据直接拷贝至了用户空间,不经过内核空间。因此,直接 I/O 不存在内核空间缓冲区和用户空间缓冲区之间的数据拷贝。
减少数据拷贝次数:在数据传输过程中,避免数据在用户空间缓冲区和系统内核空间缓冲区之间的 CPU 拷贝,以及数据在系统内核空间内的 CPU 拷贝,这也是当前主流零拷贝技术的实现思路。
写时复制技术:写时复制指的是当多个进程共享同一块数据时,如果其中一个进程需要对这份数据进行修改,那么将其拷贝到自己的进程地址空间中,如果只是数据读取操作则不需要进行拷贝操作。
缓冲区共享 方式完全改写了传统的 I/O 操作,因为传统 I/O 接口都是基于数据拷贝进行的,要避免拷贝就得去掉原先的那套接口并重新改写。
所以这种方法是比较全面的零拷贝技术,目前比较成熟的一个方案是在 Solaris 上实现的 fbuf(Fast Buffer,快速缓冲区)。
fbuf 的思想是每个进程都维护着一个缓冲区池,这个缓冲区池能被同时映射到用户空间(user space)和内核态(kernel space),内核和用户共享这个缓冲区池,这样就避免了一系列的拷贝操作。
RocketMQ 选择了 mmap+write 这种零拷贝方式,适用于业务级消息这种小块文件的数据持久化和传输。
Kafka 采用的是 Sendfile 这种零拷贝方式,适用于系统日志消息这种高吞吐量的大块文件的数据持久化和传输。
但是值得注意的一点是,Kafka 的索引文件使用的是 mmap+write 方式,数据文件使用的是 Sendfile 方式
top命令经常用来监控linux的系统状况,是常用的性能分析工具,能够实时显示系统中各个进程的资源占用情况。
-d:number代表秒数,表示top命令显示的页面更新一次的间隔。默认是5秒。
-b:以批次的方式执行top。
-n:与-b配合使用,表示需要进行几次top命令的输出结果。
-p:指定特定的pid进程号进行观察。
P:以CPU的使用资源排序显示
M:以内存的使用资源排序显示
T:由进程使用的时间累计排序显示
k:给某一个pid一个信号。可以用来杀死进程
r:给某个pid重新定制一个nice值(即优先级)
ps(process status)进程查看命令。查看正在运行的进程、进程运行状态、进程资源占用等。
u 以用户为主的格式来显示程序状况 x 显示无控制终端的程序借助二分法能够快速匹配时间戳,根据时间戳来找出需要查找的日志内容。
1 因为是二分法特性,所以日志的时间必须是按从小到大或者从大到小的顺序排列。
2 根据查找需要,修改匹配时间戳。
3 根据不同的时间戳格式,修改对应的代码。
简单:没有了会话层 和表示层,分工明确,干活牛
2、同时处理的文件描述符是有上限的
3、每次需要重新设定fd集合
4、性能会随用户的增多而效率降低
poll是对select的一种改良,最突出的改良有两点:
1、文件描述符数量没有上限
2、将输入输出参数进行分离,不用每次设定
poll中监听的文件描述符数目增多时:
1、和select一样,poll返回后,需要轮询pollfd来获取就绪的描述符
2、每次调用poll都需要大把大量客户端在一时刻可能只有很少的处于就绪状态,因此随着监视的描述符数量的增长,其效率也会线性下降。
1、文件描述符数目没有上限 通过epoll_ctl()来注册一个文件描述符,内核中使用红黑树的数据结构来管理所有需要监控的文件描述符。
2、基于事件就绪通知方式 一旦被监听的某个文件描述符就绪,内核会采用类似于callback的回调机制,迅速激活这个文件描述符,这样随着文件描述符数量的增加,也不会影响判定就绪的性能。
3、维护就绪队列 当文件描述符就绪,就会被放到内核中的一个就绪队列中,这样调用epoll_weit获取就绪文件描述符的时候,只要取队列中的元素即可,操作的时间复杂度恒为O(1)。
4、关于有些地方说:epoll还有内存映射机制,即内核将就绪队列通过mmap的方式映射到用户态,避免了拷贝内存这样的额外性能开销。
————————————————
用户空间:指的就是用户可以操作和访问的空间,这个空间通常存放我们用户自己写的数据等。
内核空间:是系统内核来操作的一块空间,这块空间里面存放系统内核的函数、接口等。 用户态切换到内核态的3种方式:a.系统调用 b.异常 c.外围设备的中断
a.系统调用 :这是用户进程主动要求切换到内核态的一种方式,用户进程通过系统调用申请操作系统提供的服务程序完成工作。
b.异常:当CPU在执行运行在用户态的程序时,发现了某些事件不可知的异常,这是会触发由当前运行进程切换到处理此
异常的内核相关程序中,也就到了内核态,比如缺页异常(硬中断)。
c.外围设备的中断:当外围设备完成用户请求的操作之后,会向CPU发出相应的中断信号,这时CPU会暂停执行下一条将要执行的指令
转而去执行中断信号的处理程序,如果先执行的指令是用户态下的程序,那么这个转换的过程自然也就发生了有
用户态到内核态的切换。比如硬盘读写操作完成,系统会切换到硬盘读写的中断处理程序中执行后续操作等。
当一个进程开始执行时,系统就为它开辟了一个虚拟内存空间,这个虚拟内存空间与真正的物理地址映射。
进程开始要访问一个地址,它可能会经历下面的过程
1.每次我要访问地址空间上的某一个地址,都需要把地址翻译为实际物理内存地址
所有进程共享这整一块物理内存,每个进程只把自己目前需要的虚拟地址空间映射到物理内存上
2.进程需要知道哪些地址空间上的数据在物理内存上,哪些不在(可能这部分存储在磁盘上),还有在物理内存上的哪里,这就需要通过页表来记录
页表的每一个表项分两部分,第一部分记录此页是否在物理内存上,第二部分记录物理内存页的地址(如果在的话)
3.当进程访问某个虚拟地址的时候,就会先去看页表,如果发现对应的数据不在物理内存上,就会发生缺页异常
4.缺页异常的处理过程,操作系统立即阻塞该进程,并将硬盘里对应的页换入内存,然后使该进程就绪,如果内存已经满了,没有空地方了,那就找一个页覆盖,至于具体覆盖的哪个页,就需要看操作系统的页面置换算法是怎么设计的了。
5.进程运行过程中,要通过malloc来动态分配内存时,也只是分配了虚拟内存,即为这块虚拟内存对应的页表项做相应设置,当进程真正访问到此数据时,才引发缺页异常。
———————————————— 利用虚拟内存机制的优点
1.既然每个进程的内存空间都是一致而且固定的(32位平台下都是4G),所以链接器在链接可执行文件时,可以设定内存地址,而不用去管这些数据最终实际内存地址,这交给内核来完成映射关系
2.当不同的进程使用同一段代码时,比如库文件的代码,在物理内存中可以只存储一份这样的代码,不同进程只要将自己的虚拟内存映射过去就好了,这样可以节省物理内存
3.在程序需要分配连续空间的时候,只需要在虚拟内存分配连续空间,而不需要物理内存时连续的,实际上,往往物理内存都是断断续续的内存碎片。这样就可以有效地利用我们的物理内存
————————————————
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
// 注意:由于栈中存放的是数组的下标,所以需要用到柱子的高度时,记得转换过来
// 创建一个单调栈,为了便于后面计算,栈中存放的是数组的下标
// 第一个元素先直接入栈
// 出栈的元素需要保存起来,作为底部参考值
// 判断栈是否为空,为空,接不到雨水,直接break
// 不为空,计算雨水
原来在字节实习过,为什么来深圳
协程其实可以认为是比线程更小的执行单元。为啥说他是一个执行单元,因为他自带CPU上下文。这样只要在合适的时机,我们可以把一个协程 切换到 另一个协程。只要这个过程中保存或恢复 CPU上下文那么程序还是可以运行的。
1.一个线程可以多个协程,一个进程也可以单独拥有多个协程,这样python中则能使用多核CPU。
2.线程进程都是同步机制,而协程则是异步
3.协程能保留上一次调用时的状态,每次过程重入时,就相当于进入上一次调用的状态
互斥锁是一种独占锁,当线程A加锁成功后,此时互斥锁已经被线程A独占了,只要线程A没有释放手中的锁,线程B就会失败,就会释放掉CPU给其他线程,线程B加锁的代码就会被阻塞。
性能开销成本:两次线程上下文切换的成本。
1、当线程加锁失败时,内核将线程的状态从【运行】切换到睡眠状态,然后把CPU切换给其他线程运行;
2、当锁被释放时,之前睡眠状态的线程会变成就绪状态,然后内核就会在合适的时间把CPU切换给该线程运行;
自旋锁通过CPU提供的CAS,在用户态完成加锁和解锁操作,不会主动产生线程上下文切换,所以相比互斥锁来说,会快一些开销小一些。
当两个线程属于同一个进程,因为虚拟内存是共享的,所以在切换时,虚拟内存这些资源就保持不动,只需要切换线程的私有数据、寄存器等不共享的数据。
上下切换的耗时大概在几十纳秒到几微秒之间,如果锁住的代码执行时间比较短,可能上下文切换的时间比锁住的代码执行时间还要长。 若是能确定被锁住的代码执行时间很短,就不应该使用互斥锁,而应该选择自旋锁。
自旋锁利用CPU周期一直自旋直到锁可用。由于一个自选的线程永远不会放弃CPU,因此在单核CPU上,需要抢占式的调度器(不断通过时钟中断一个线程,运行其他线程)。
自旋的时间和被锁住的代码执行的时间成正比关系。
快速排序的时间复杂度最好是O(nlogn),平均也是O(nlogn),这种情况是轴枢恰好能把两侧的分开。
时间复杂度最差是O(N 2),最差的情况选择的轴枢在数组最左侧或是最右侧
因为一面结束紧接着二面,二面面试官(主管)和一面面试官简单沟通了一下
讲讲你擅长的技术(瞎聊天)
1.DML语句首先进行语法分析,对使用sql表示的查询进行语法分析,生成查询语法分析树。
2.语义检查:检查sql中所涉及的对象以及是否在数据库中存在,用户是否具有操作权限等
3.视图转换:将语法分析树转换成关系代数表达式,称为逻辑查询计划;
4.查询优化:在选择逻辑查询计划时,会有多个不同的表达式,选择最佳的逻辑查询计划;
5.代码生成:必须将逻辑查询计划转换成物理查询计划,物理查询计划不仅能指明要执行的操作,也给出了这些操作的执行顺序,每步所用的算法,存储数据的方式以及从一个操作传递给另一个操作的方式。
6.将DML转换成一串可执行的存取操作的过程称为束缚过程,