稳定的排序

  • 稳定的排序的定义？
    • 稳定的排序是指当有两个相等元素的顺序在排序后仍然保持不变
  • 稳定的排序 - > 看元素的相对位置是否发生改变
    • 冒泡排序
      • 依次比较相邻元素的大小 如果大 就交换位置
    • 插入排序
      • 总是维持已知元素序列的有序性，取出一个元素，放到对应的位置
    • 归并排序
      • 分而治之，先把数组递归的分割成更小的集合，然后合并相邻的数组，并将他们合并成一个有序的序列
    • 基数排序
      • 确定最大的位数
      • 然后根据位数 从个位开始 用相应的位置的值放入桶中 进行排序
    • 桶排序
      • 其实就是先划分范围（桶）
      • 然后把数放到不同的桶中
      • 然后桶内排序，最后合并桶

快排的实现

原理

选定一个基准数，然后将比这个数字小的数字放到左边，比这个数字大的数字放到右边，然后依次迭代两边的区间，直到区间长度为1 结束

具体实现过程

头部索引为i 尾部索引为j 然后j– 依次遍历 遇到比基准数小的数停下来，交换i和j的数的位置，同时i++ 寻找比基准数大的数 再与j的数进行交换，直到ij相遇


进程和线程，协程的区别，以及如何通信

进程是竞争计算机资源的基本单位，能够分配和管理资源

线程是执行单元 是进程内部调度实体，比进程更小的基本单位

协程是比线程更轻量级，一个线程可以有多个协程，可以视为不带返回值的函数调用


线程与进程区别

  • 地址空间
    • 线程共享本进程的地址空间，而进程之间是独立的地址空间
  • 资源
    • 线程共享本进程的资源（io，cpu，内存）进程之间资源独立的，能更好的进行资源管理和保护
  • 健壮性
    • 多进程要比多线程具有更好的健壮性，一个进程崩溃并不会对其他的进程产生影响，但是一个线程崩溃，会导致整个进程崩溃
  • 执行过程
    • 每个进程有独立的程序运行入口，执行进程的开销较大
    • 线程不能独立运行，必须依赖于进程，但是执行开销小
  • 并发性
    • 两者都可以并发
  • 切换性
    • 进程切换，消耗的资源大 涉及频繁的切换的时候，线程优于进程。同时进行而且要求需要共享变量的并发操作的时候 只能使用线程
  • 其他
    • 线程是处理器调度的基本单位，进程不是 （进程本身就独占内存）

协程和线程区别

协程避免了无意义的调度，可以提高性能，但是需要程序承担调度任务

  • 线程
    • 相对独立，有自己的上下文，切换受到系统控制
  • 协程
    • 相对独立，有自己的上下文
    • 切换由自己控制，由当前协程控制切换到其他的协程

何时使用线程池与进程池

对资源管理要求高，而且不限制开销和效率 使用多进程

要求效率高，切换频繁，对资源管理要求不高，使用多线程

进程通信方式

  • 管道
    • 速度慢，只能父子进程通信
  • FIFO
    • 任何进程都可以通信 但是速度慢
  • 消息队列
    • 容量受到内存限制，第一次读的时候需要考虑上一次未读完的问题
  • 共享内存
    • 速度快 但是需要考虑读写问题

线程通信方式

  • 共享内存
    • 速度快，但是需要注意线程安全

tcp，ip，udp协议层次

涉及到计网

ip -》 知道对方在哪里 在网络层 （定义ip + 端口） 高速缓存arp 映射mac 地址与 IP 地址 （逻辑地址）

tcp udp在运输层

  • TCP
    • 可靠交付
      • 保证数据能够按序到达，无差错，不重复，不丢失
    • 面向连接传输
      • 必须是一对一才能连接，无法一对多
    • 基于字节流
      • 用户通过tcp协议传输，会被分成多个tcp包，接收方需要知道消息的边界才能接受信息，并且包需要按序到达，如果先接受到了后面的报文，需要丢弃报文，并返回应该接受到的包的序号
    • 全双工通信
      • 两端都可以发送和接受
  • UDP
    • 无连接
    • 尽最大努力交付
      • 不保证可靠交付，主机不需要维持连接状态
    • 面向报文
      • udp一次性向ip交付完整的报文，网络层加上ip首部

arrayList底层是数组元素的物理地址相邻，寻找单个元素效率较高，但是插入或者移除元素需要移动的元素个数多，效率慢

linklist底层是链表结构，寻找单个元素的效率满，需要一次遍历，但是插入或者删除元素效率高

hashmap插入过程

元素的存取流程

  1. 判断hashmap是否为空，如果为空，就先设定容量初始值为16

  2. 获取key的hashcode，计算出元素的下标

  3. 检查是否发生hash碰撞，如果没有发生碰撞直接放到桶中

  4. 如果发生碰撞，比较两个key是否相同，如果相同则覆盖，如果不相同，以链表的形式放到尾部（尾插）

  5. 如果链表长度超过阈值（8）为了防止性能下降 将链表转换成红黑树（jdk8后）

  6. 插入成功之后，如果元素个数超过阈值，则进行扩容至原来的两倍，同时重新对元素的下标进行重新计算

为什么把头插法改成尾插法

头插法非线程安全，会产生环

jvm内存模型（结构）

  • 程序计数器
    • 是较小的一块区域，用于指示当先线程执行的字节码的位置，用于在线程切换的时候恢复状态
  • 堆
    • 用于储存对象实例 new出来的对象，java的堆被所有的线程内存共享
  • 虚拟机栈
    • 每一个线程有一个私有的栈，用于储存局部变量，方法参数，操作数栈，方法调用等信息，每一个调用的方法都会产生一个栈帧，栈帧会随着方法的调用和返回，创造和销毁
  • 本地方法栈
    • 与虚拟机类似，但是用于执行本地方法，本地方法不是用java写的，而是用c或者cpp写的，关键字为native
  • 方法区
    • 储存类的元数据信息，静态变量，常量等
    • jvm1.8之前，方法区是用永久代实现，占用jvm内存，方法区中有常量池，class，classloader，而string table存在常量池中
    • jvm1.8之后，方法区基于metaspace（原空间）实现，占用的是本地内存吗 stringtable 存在堆中

innodb引擎索引结构

b树与b+树区别

b树的每一个节点都储存了key和value，而b+树非叶子节点只储存索引信息，data都存在叶子节点中，叶子节点构成一个有序链表，所以b+树的层级更小，io更少

索引结构

innodb是基于B+树的索引结构

  • 聚簇索引
    • 每张表都有一个主键索引，这个索引就是聚簇索引，聚簇索引决定了表中数据的物理储存数据，表中的数据就是按照聚簇索引顺序储存，相邻的数据是相邻储存的
  • 辅助索引
    • 除了聚簇索引之外，非聚簇索引也成为辅助索引，叶子节点储存了索引列的值以及对应的主键的值，通过辅助索引可以快速定位主键值，从而快速定位主键所在行的数据
  • 叶子节点包含数据行
    • 叶子节点包含了索引列的值以及整行数据
  • 自适应哈希索引
    • 当某一个索引的访问频率很高的时候，会自动创建hash索引，加速这个索引的查询
  • 聚簇索引更新
    • 插入或者删除 都会导致更新索引，从而影响性能