Luffy's Blog

前言：BST、AVL、RBT、B-tree都是动态结构，查找时间基本都在O(longN)数量级上。下面做出详细对比。 二叉查找树（Binary Search Tree）二叉查找树又称二叉搜索树，二叉排序树，特点如下: 左子树上所有结点值均小于根结点 右子树上所有结点值均大于根结点 结点的左右子树本身又是一颗二叉查找树 二叉查找树中序遍历得到结果是递增排序的结点序列。 BST 的操作代价分析：查找代价：任何一个数据的查找过程都需要从根结点出发，沿某一个路径朝叶子结点前进。因此查找中数据比较次数与树的形态密切相关。当树中每个结点左右子树高度大致相同时，树高为logN。则平均查找长度与logN成正比，查找的平均时间复杂度在O(logN)数量级上。当先后插入的关键字有序时，BST退化成单支树结构（退化成链表）。此时树高n。平均查找长度为(n+1)/2，查找的平均时间复杂度在O(N)数量级上。 插入代价新结点插入到树的叶子上，完全不需要改变树中原有结点的组织结构。当树中**每个节点左右子树高度大致相同时，插入的平均时间复杂度是O(logN)**；若退化成单链表了，插入的时间复杂度是O(N)。 ...

字节提前批技术中台一面凉经~ 07.26 15:00-16:10 面试官人很好 自我介绍 项目介绍，结合项目问了些问题（qps多少？内存占用多少？后面怎么更新和维护这个项目？打算用令牌桶限流） JDK平时用的版本？ String类可继承吗？ final修饰，不可被继承 HashMap八股 JDK1.7—>1.8变化 底层结构和头插变尾插 并发下怎么用Map？concurentHashMap—底层实现 JDK1.7—1.8 还有别的方法保证线程安全吗？ hashmap加锁，但不会用，承载能力没这个好 为什么？ 1.7中分段锁底层是什么？ put怎么锁 get会锁？ 获取Entry数组长度是线程安全的吗？（这个没听过哈哈啊 应该是的吧） 红黑树 set get的时间复杂度？O(logn) 说说并发下的线程安全问题吧（这个是我理解面试官所说的）锁 valtile JUC下的原子类 天然线程安全无状态代码 static volatile作用？底层实现？ mysql的有哪些存储引擎，对比下 ACID 四大隔离级别 遇到过慢SQL吗？ 哈哈 没遇到，自己设计的表 ...

上下文首先，需要讲清楚什么是上下文。 每个任务运行前，CPU 都需要知道任务从哪里加载、又从哪里开始运行，这就涉及到 CPU 寄存器 和 程序计数器（PC）： CPU 寄存器是 CPU 内置的容量小、但速度极快的内存； 程序计数器会存储 CPU 正在执行的指令位置，或者即将执行的指令位置。 这两个是 CPU 运行任何任务前都必须依赖的环境，因此叫做 CPU 上下文。 上下文切换那么，什么是上下文切换呢？下面是一个上下文切换时需要履行的步骤： 将前一个 CPU 的上下文（也就是 CPU 寄存器和程序计数器里边的内容）保存起来； 然后加载新任务的上下文到寄存器和程序计数器； 最后跳转到程序计数器所指的新位置，运行新任务。 被保存起来的上下文会存储到系统内核中，等待任务重新调度执行时再次加载进来。 CPU 的上下文切换分三种：进程上下文切换、线程上下文切换、中断上下文切换。 系统调用Linux 按照特权等级，把进程的运行空间分为内核空间和用户空间： 内核空间：具有最高权限，可以访问所有资源； 用户空间：只能访问受限资源，不能直接访问内存等硬件设备，必须借助系统调用。 进程可以在用 ...

AOF重写 AOF 持久化是通过保存被执行的写命令来记录数据库状态的，所以AOF文件的大小随着时间的流逝一定会越来越大；影响包括但不限于：对于Redis服务器，计算机的存储压力；AOF还原出数据库状态的时间增加； 为了解决AOF文件体积膨胀的问题，Redis提供了AOF重写功能：Redis服务器可以创建一个新的AOF文件来替代现有的AOF文件，新旧两个文件所保存的数据库状态是相同的，但是新的AOF文件不会包含任何浪费空间的冗余命令，通常体积会较旧AOF文件小很多。 AOF 文件重写的实现 AOF重写并不需要对原有AOF文件进行任何的读取，写入，分析等操作，这个功能是通过读取服务器当前的数据库状态来实现的。 1234567891011121314151617181920 # 假设服务器对键list执行了以下命令s;127.0.0.1:6379> RPUSH list "A" "B"(integer) 2127.0.0.1:6379> RPUSH list "C"(integer) 3127.0.0.1:6379& ...

1. 什么是微服务？官网: https://www.martinfowler.com/articles/microservices.html In short, the microservice architectural style is an approach to developing a single application as a suite of small services, each running in its own process and communicating with lightweight mechanisms, often an HTTP resource API. These services are built around business capabilities and independently deployable by fully automated deployment machinery. There is a bare minimum of centralized management of these services, wh ...

1. Nginx介绍Nginx是一款轻量级的Web服务器、反向代理服务器，由于它的内存占用少，启动极快，高并发能力强，在互联网项目中广泛应用。 上图基本上说明了当下流行的技术架构，其中Nginx有点入口网关的味道。 说了这么多，我们先安装玩玩吧 2. 安装Nginx一般都是项目都是部署在linux上，这里我们采用Docker的方式启动Nginx，关于Docker的，上一篇有详细介绍 Docker 下面记录centos7利用Docker安装Nginx的命令 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475[root@hspEdu01 nginx]# docker pull nginxUsing default tag: latestTrying to pull repository docker.io/library/nginx ... latest: ...

最近在学Docker，花了很多时间，算是把Docker的一些基本使用方法get到了，现在记录下 1. Docker基础知识1. 什么是Docker 官网的介绍是“Docker is the world’s leading software container platform.” 官方给Docker的定位是一个应用容器平台。 Docker 是一个容器平台的领导者 Docker 容器平台 Docker 应用容器平台 1.2 为什么使用Docker 合作开发的时候，在本机可以跑，别人的电脑跑不起来 这里我们拿java Web应用程序举例，我们一个java Web应用程序涉及很多东西，比如jdk、tomcat、spring等等。当这些其中某一项版本不一致的时候，可能就会导致应用程序跑不起来这种情况。Docker则将程序直接打包成镜像，直接运行在容器中即可。 服务器自己的程序挂了，结果发现是别人程序出了问题把内存吃完了，自己程序因为内存不够就挂了 这种也是一种比较常见的情况，如果你的程序重要性不是特别高的话，公司基本上不可能让你的程序独享一台服务器的，这时候你的服务器就会跟公司其他 ...

公司的技术栈是SpringCloud+ZoomKeeper+RabbitMq+JPA+MongoDB，利用zk去做配置文件，rabbitmq做一些异步处理，持久层采用JPA(数据库的Mysql)，对于大部分都是查询的业务，数据是存在MongoDB中。 MongoDB是一个高性能、开源、无模式的文档型数据库，是当前NoSql数据库中比较热门的一种。 适合对大量或者无固定格式的数据进行存储，比如：日志、缓存等。对事物支持较弱，不适用复杂的多文档（多表）的级联查询。 MongoDB的适用场景： 在应用服务器的日志记录 存储一些监控数据 应用不需要事务及复杂 join 支持 应用需要2000-3000以上的读写QPS 应用需要TB甚至 PB 级别数据存储 应用发展迅速，需要能快速水平扩展 应用要求存储的数据不丢失 应用需要99.999%高可用 应用需要大量的地理位置查询、文本查询 下面就讲下SpringBoot利用MongoTemplate操作mongdb 1. MongDB的安装安装MongDB可以看官网安装 英语不好的小伙伴可以看这个安装 我是在centos7.0上安装的MongDB4 ...

关于多线程的几点补充在理解线程的状态时，需要先了解每个对象都有的——锁池和等待池这两个概念。 锁池就是一个线程A已经占用了对象锁，其他对象想要拿到该对象锁就必须等待A释放锁，这些想拿到对象锁的线程就会进入锁池，等待和竞争锁。 等待池：假设一个线程A调用了某个对象的wait()方法，线程A就会释放该对象的锁，进入到该对象的等待池。 从上面就可以看出锁池是里的线程都是竞争锁的，而等待池里的线程已经被释放锁，等待被唤醒，所以是不会竞争该对象的锁 我们先聊下sleep和wait的区别 Sleep是Thread的静态方法，线程休眠，不会让出锁，而是到时候就继续执行。可以在程序的任何地方进行使用。 Wait是Object的方法，线程释放锁，进入等待池，等待notify()或notifyAll()唤醒，进而进入锁池，竞争锁。Wait必须是在已经持有锁的情况下去调用释放锁，不然会抛出IllegalMonitorStateException，因为锁都没，何谈释放锁呢？ 接下来就是wait，notify，notifyAll()的区别，上面已经说到，调用wait就是使线程释放当前锁进入等待池，那么也不是一直 ...

进程的上下文切换和线程的上下文切换的区别首先我们需要知道进程和线程的上下文切换做了什么： 切换页目录以及使用新的地址空间 切换内核栈和硬件的上下文 两种的区别就是进程有第一个操作，线程是没有的，第二个线程和进程都有 关于讨论两者的区别，需要知道进程和线程的在内存地址上的区别，进程是独立的地址空间，而进程里面的线程是连续的地址空间，同一个进程内的线程地址是共享的。 其实切换进程和线程最大的区别就是虚拟地址空间的改变。对于进程由于是独立的地址空间，每一个线程都是有自己的虚拟地址空间，一旦进行切换就需要切换虚拟地址空间；线程由于是地址空间是共享的，所以不需要切换虚拟地址空间。那么问题来了，什么是虚拟地址？为什么虚拟地址空间的切换是消耗性能的？ 虚拟地址空间，是一个操作系统为每一个进程提供的一块独立的、私有的、地址连续的虚拟内存，但虚拟内存终究还是虚拟的，需要真正和物理地址挂钩，那么这样的技术就叫地址空间映射技术，把虚拟地址和物理地址建立关系。对于这种关系表就叫做页表，由于每一个进程都有自己的虚拟内存，所以每一个进程也有自己的页表，页表就是查询虚拟内存和物理内存关系的，但对于线程都是共享地 ...