键盘敲入字母时，期间发生了什么？   前提：     主要涉及到设备控制器（包含：数据寄存器、命令寄存器、状态寄存器）的概念；   CPU与设备并不是直接交互，而是通过设备控制器来实现的。        过程：     用户从键盘敲入字母时，就会将数据缓存在键盘控制器的寄存器中，键盘控制器通过总线发送中断给CPU；   CPU收到中断请求，保存进程的上下文，调用键盘控制器的中断处理函数读取寄存器中的数据存放到【读缓存区队列】；   显示器控制器会定时的从【读缓存区队列】放到【写缓存区队列】，最后将【写缓存区队列】的数据写入到显示器控制器的寄存器中；   最后恢复中断的进程上下文。     大体...

链式队列   由链表实现的队列；       顺序队列   由数组实现的队列；   数组实现可变长度的队列    思路：     使用System.arraycopy()进行扩容、进行数据迁移   记录数组有效长度、不需要记录数组的总容量    package com.hshuo; /**  * 数组实现可变长度的队列  * @author SHshuo  * @data 2022/2/26--11:39  */ public class arrayToVolatileQue...

结构   先进后出；      分类     顺序栈（用数组实现ArrayDeque）；   链式栈（由链表实现LinkedDeque）。        时间复杂度O（1）     因为无论是顺序栈还是链式栈，入栈、出栈都只涉及栈顶个别数据的操作；   例如顺序栈实际上就是操作数组的最后一个元素，链式栈实际上就是对头节点做增删。        扩容   出栈、入栈的时间复杂度都为O（1）；   入栈的时候有两种情况：     一种是可能会涉及到数据迁移时间复杂度为O（n）；   一种是会普通的入栈操作时间复杂度为O（1）；   通过将耗时多的入栈操作的时间均摊到其他入栈操作上，平均时间复杂度为...

单链表   头结点：用来记录链表的基地址；   尾结点：指向的是一个空地址NULL；         插入、删除     数组在进行插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂度是O(n)；   链表中插入、删除操作时，并不需要为了保持内存的连续性而搬移节点，因为链表的存储空间本身就不是连续的；所以只需要考虑相邻节点的指针改变，对应的时间复杂度为O(1);       边界的问题：    针对链表的插入、删除操作，需要对插入第一个节点和删除最后一个节点的情况进行特殊处理；      插入操作   在空链表插入第一个节点   if(head ==&nb...

为什么数组下标要从0开始，而不是从1开始？     数组下标表示偏移（offset）；   例如数组a[]，那么a[0]表示偏移0个位置，也就是首地址；a[i]表示偏移i个type_size位置，所以a[i]的内存地址只需要通过：a[i]_address = base_address + i * type_size;   但是如果数组如果从1开始技数，那么数组元素a[i]的内存地址就会变为：a[i]_address = base_address + (i - 1) * type_size；也就是额外需要CPU做一次减法指令。        数组的随机访问     数组是一种线性表的数据结构，它...

排序算法的执行效率     最好情况、最坏情况、平均时间复杂度；   时间复杂度的系数、常数、低阶；   比较次数和交换次数。        排序算法的稳定性   概念：   如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。   场景：   如果要给电商交易系统中的订单排序，订单有两个属性，一个是下单时间、一个是订单金额；现在有10万条数据，希望按照金额从小到大对订单数据进行排序；对于金额相同的订单，按照下单时间从早到晚排序，如何实现？     普通思路：先按照金额对订单数据排序，在遍历订单数据对每个金额相同的小区间再按照下单时间排序；   最优思路：借助稳定...

归并算法   思路：     分解成两个待排序的区间；   使用递归将两个子序列分别排好序；   申请空间，定义两个指针指向两个序列的起始位置，比较指针所指向的元素，选择相对小的元素放入合并空间。         统一格式：     先递归、后merge；   递归的跳出条件是：     if(right == left){     return 0; }    稳定性：   主要取决于合并的过程，也就是两个有序子数组合并成一个有序数组的时候，将左侧的优先放在数组中，即可实现稳定性   public void&nb...

堆的概念     底层：用数组存储；   数据结构：完全二叉树（除了最底层，其它层都必须填满，最后一层可以从左到右填满）；   如图：       性质：（i对应的是数组的下标）       如果当前节点是i，父节点：（i - 1）/ 2;   如果当前节点是i，左子树的根节点：2i + 1;   如果当前节点是i，右子树的根节点：2i + 2。       堆排序不是稳定的排序算法？     在排序过程中，通过heapfity（）的过程涉及到将存在堆最后一个节点跟堆顶节点交换的操作，可能会导致改变相同数据的原始相对顺序。         为什么多数使用快排而不是堆排？     堆排序数据访问...

HTTP方法：     Get：获取资源；   Post：传输实体的主体；   Put：传输文件（需要在请求报文主体中包含文件内容，例如content-Type：text/html等信息）；   Delete：删除文件；   Head：确定URI的有效性及资源更新的日期时间等；   Options：询问支持的方法；   Trace：追踪路径；   Connect：要求用隧道协议（SSL/TLS）连接代理。       put与post请求的区别？（北森云计算一面）    关键点：幂等性：   二者都可以创建或者更新请求；但是当两个请求相同时     put方法如果两个请求相同，后一个请求会把前...

构造二叉树   思路：     根据中序遍历找到根节点，在前序遍历或者后序遍历中计算左右子树的范围；   之后递归实现。    例题：      105. 从前序与中序遍历序列构造二叉树   106. 从中序与后序遍历序列构造二叉树   889. 根据前序和后序遍历构造二叉树（根据前序遍历找到左子树的根节点，在后序遍历中找到对应下标并计算左子树的范围）             完全二叉树   958. 二叉树的完全性检验   两个条件:     左孩子为空，右孩子不为空不是完全二叉树；   遇到左孩子或者右孩子为空的节点，下一次遍历的时候以后的所有节点都应该没有左孩子和右孩子。    核心代码...

概念     零拷贝是指计算机执行IO操作时，CPU不需要将数据从一个存储区域复制到另一个存储区域，进而减少上下文切换以及CPU的拷贝时间。它是一种IO操作优化技术。          过程    早期的I/O过程     CPU发出对应的指令给磁盘控制器；   磁盘控制器收到指令后，开始准备数据并把数据放到磁盘控制器的内部缓冲区中，然后产生一个中断；   CPU收到中断信号后，将磁盘控制器的缓冲区的数据一次一个字节的读进自己的寄存器，然后把寄存器的数据写入到内存，（也就是将数据从磁盘控制器拷贝到PageCache，再将数据从PageCache拷贝到用户缓冲区）而在数据传输期间CPU是无法执行...

为什么是删除缓存值而不是更新缓存值？   数据一致性问题     无论是先更新数据库还是后更新数据库都会造成数据不一致问题；   例如：线程A先更新数据库数据为21，线程B并发的更新数据库数据为20，接着更新缓存为20。线程A继续更新缓存数据为21，造成不一致问题；后更新数据库同理     浪费缓存资源、造成缓存利用率不高的问题     因为在每次数据发生变更的时候，都无脑更新缓存，但是缓存中的数据不一定会被马上读取，这样就会导致缓存中可能存放了很多不常访问的数据，浪费缓存资源；   会造成缓存利用率不高同时也会浪费机器的性能，所以考虑到删除缓存。        Cache Asize（旁路缓...

过期数据的删除策略      惰性删除：只会在取出key的时候才对数据进行过期检查。这样对CPU最友好，但是可能会造成太多的过期key没有被删除；   定期删除：每隔一段时间随机抽取（而不是遍历所有设置过期时间的key）一批key执行删除过期key的操作。同时redis底层会通过限制删除操作执行的时长和频率来减少删除操作对CPU时间的影响。        由于通过定期删除会漏掉很多过期的key，然后也没有及时查看也就没有走惰性删除；也就是仍有可能漏掉了很多过期的key，会导致大量过期的key堆积在内存中造成out of memory；      redis内存淘汰机制     volatile...

缓存穿透     大量请求的key根本不存在于缓存中，导致请求直接到了数据库上，根本没有经过缓存这一层。大多属于恶意攻击。   解决：布隆过滤器     布隆过滤器。将所有可能存在的请求的值都存放在布隆过滤器中，当用户请求过来，先判断用户发来的请求的值是否存在于布隆过滤器中。不存在的话，直接返回请求参数错误信息给客户端，存在的话才会走下面的流程。   布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在。   利用Guava中自带的布隆过滤器。 <dependency>     <groupId>...