算法1
算法1给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水) 木板组成水桶装水,定义高度为一数组,间隔为1,求水桶最大容量如[1,5,1,2,6,3]为15,解题思路:自两边木板向中间遍历求容量,每次相对短的木板向内移动,共比较n-2次 将水灌满,求灌满后的高度,其实就是从最高点向左右两个方向向中间遍历,依次求经过的最大值,这样一来就是从最高点向两侧递减的,再减去柱子原高度即可 容易理解的想法还有按高度分层计算,但是时间复杂度过高

2019-03-14Sherlock
Redis原理-源码解析:数据结构3 sorted set(zset))
Redis原理-源码解析:数据结构3 sorted set(zset))Redis的set数据结构在此不多讲,同Java中原理一样,set也可以理解为是hash剥离了value的数据结构,即同为dic 但是zset(有序集合)其实在底层原理上完全不同于set 所有原理实现基于Redis版本6.0.9 先看一下基本的指令实现,着重注意中文注解的地方 t_zset.c 可以看出zset的数据结构不是固定的,在其元素数或是元素的字符串过长时,其结构为zset;否则使用ziplist数据结构(像hash一样为了节省空间),二者的创建方法如下: ziplist的代码和原理可以参考我的博客Redis原理-源码解析:数据结构2 list-鱼鱼的Java小站,就是一个节省内存的压缩的链表结构

2021-02-28鱼鱼
对多线程的执行效率探究——合理的任务并发拆分
对多线程的执行效率探究——合理的任务并发拆分通常,我们选择多线程执行任务有两个理由,一是复杂任务采用多线程处理能够在发生并发时让用户减少等待也能防止阻塞,一是充分利用空闲时间,提高任务处理的效率,就后者而言,此处探讨不考虑客户端并发是否有必要把一个任务拆分成多线程来处理 为了探究多线程的效率问题,我做了一个实验,将不同种类的任务分别用单线程和多线程执行,同时也试验了不同种类的锁机制 测试基于Java 8的版本,希望看到总结可以直接点击到文末 开启五个线程执行任务,设定了足够次数的循环输出,输出的数字和当前线程,利用System.currentTimeMillis()统计任务用时 (代码略)以下是相同任务在不同环境下执行多次的平均执行时间

2019-12-09鱼鱼
Redis原理-源码解析:数据结构2 list
Redis原理-源码解析:数据结构2 list所有原理实现基于Redis版本6.0.9 Redis中的list采用的是链表,在开始前,我们先看看list的最基本指令实现 t-list.c 由此可知,Redis的List底层数据结构都是基于quickList的 这是list所依赖的数据结构: quicklist.h 我们注意到其是由quicklistNode所构成的链表,而其中的数据实则为zl(ziplist)或是bookmark,在大多时候quicklistNode都使用ziplist存储数据 在上文中lpush执行了一个插入方法quicklistPush,在quicklist.c中有他的实现: quicklist真正存储数据的结构是ziplist,所以倒不如说,在Redis中,list是一个由ziplist节点构成的链表

2020-11-28鱼鱼
有关Session的碎碎念-ban掉cookie之后
有关Session的碎碎念-ban掉cookie之后java web中, 用session来表示用户浏览器(客户端)与服务器建立的一次会话 通常用sessionId来标记一个session,在Java中,有很简单的方式直接获取sessionId; 但是sessionId并不是session的特性,实际上,sessionId是在客户端首次创建会话时将生成的sessionId存入cookie中,在之后的访问中直接读取这个id值 当客户端禁止了cookie行为后,SessionId在每次刷新页面时都会更新,利用id来表示会话也成为了妄想,此篇文章意在说明,如何操作能使SessionId能够独立于cookie使用 这种操作其实在shiro中已经被应用了,当我们进入登录页面中,url后会出现";jssionid=xxxxxx",将sessionid显示的标注在url中,可以使用:
![有关Session的碎碎念-ban掉cookie之后]()
2019-03-08鱼鱼
Rocket MQ的基本应用
Rocket MQ的基本应用消息队列,常用于应用间通信 本篇文章基于RocketMQ官方文档 Topic:消息分类,依靠topic来定义消息类型 Tag:消息二级分类,可选,同个topic用不同的tag区分消息类别 Message : 泛指MQ所传送的消息体 Producer:消息生产者 Consumer:消息消费者 Name Server:有点类似于zookeeper,负责服务的注册与发现,维护Broker与Topic的映射关系 Broker:负责消息的存储与生产者消费者消息接收与分发,与Name Server建立长连接,保持心跳上传负责的topic信息 Producer:消息生产者,从Name Server获取Broker对应Topic映射关系,然后与Broker建立连接发送消息

2019-06-28鱼鱼
分布式系统中的一致性算法和问题解决
分布式系统中的一致性算法和问题解决在撰写脑裂问题相关的博客时发现脑裂问题的产生原因在不同算法下的分布式系统各不相同,需要先大致了解一致性算法并针对性的解决 市面上有很多开源的分布式系统,他们的数据一致性算法不尽相同,例如k-v系统的祖师爷——zookeeper采用的是ZAB的算法,而最近流行的Consul是raft算法,不同数据中心server沟通的方式则是gossip协议 不同的协议和方式对选举和数据同步有不同的处理机制,利用这篇文章来对比常见的分布式一致性算法 一个系统可能会使用多个不同的一致性算法,以便于在不同的业务环节上有着各自更贴切的处理 ps:有种观点是一致性算法不是很准确,因为replica也能保证数据某种程度上具有一致性,有人称之为共识算法

2021-03-13鱼鱼
IO与NIO
IO与NIO我们都知道IO流传输,其实IO模型有很多,例如BIO、NIO、AIO等,传统的IO都是同步的 IO为各种流操作 IO操作分类 I IO操作分类 II 其中,输入流可以为InputStream和Reader,分别为字节流和字符流,对应地,输出流为OutputStream和Writer,具体的使用在此不详述 NIO是IO模型中后推出的新IO模型 NIO并不一定是多线程的,但是NIO是多管道的,利用缓冲作为中间介质进行数据传输,运用的其实是多路复用技术,它恰恰是通过减少线程数量从而减少上下文的频繁切换,提高性能 Channel:通道,相当于一个连接,不能直接输出数据,只能与Buffer交换数据

2019-05-11鱼鱼
并发之AQS全解析
并发之AQS全解析我们知道juc(java.util.concurrent)包下有很多实用的类,提供了很多并发工具,例如线程池、原子类、并发工具、信号量工具、锁等,可以说基本实现都为悲观锁,底层原理基本都使用了AQS(AbstractQueuedSynchronizer),AQS不是一种概念,是并发中实打实的工具类 本篇文章针对AQS做解析 AQS是多线程访问共享资源的同步器框架 AQS的资源可以是独占的也可以是共享的 我们先来简单看一下它的使用方式和ApI(因为是抽象类,是不能直接使用的),下图是AQS的整体脉络 AQS核心就是一个状态值state,同时维护了一个线程的阻塞队列,队列的节点为有两种状态:SHARED(共享)和EXCLUSIVE(独占),节点状态有五种:
![并发之AQS全解析]()
2021-03-12鱼鱼
Spring的事务
Spring的事务Spring事务将一系列操作绑定为具有原子性的操作,此篇文章讲基于Spring提供的声明式事务 MySQL的事务我们已经明白,Spring的事务是委派了ORM框架来解决相应的问题,在jdbc中,体现的就是在Mybatis框架中,体现的就是SqlSession的建立到提交 声明式事务:在方法或是实现类上加上以下注解: 其中一些常用参数: propagation:配置事务传播行为;(后面详细解读) isolation:事务隔离级别; timeout:超时时间; roolbackFor:导致事务回滚的异常类设置; readOnly:boolean,是否只读 有七种事务传播行为,用来决策当发生事务嵌套时的解决方案
![Spring的事务]()
2019-07-18鱼鱼
Spring源码解析(1) 基于SSM看Spring的使用和Spring启动监听
Spring源码解析(1) 基于SSM看Spring的使用和Spring启动监听查看源码的顺序就见仁见智了,比较普遍的做法是从IoC入手,了解容器注入的每一个环节,掌握大致的流程 由于使用的是Spring,所以在这里我们引入比较古老的xml配置文件进行bean的配置,首先定义一个bean: 配置描述bean的xml,核心只有一行: 这样一来就可以使用BeanFactory这个容器来注入bean并使用了: 本来有封装好的XmlBeanFactory,这一类现在已经被弃用了,所以采用了他的父类DefaultListableBeanFactory;当然,也可以使用更加方便和常用的ApplicationContext: 当然从xml文件读取bean的配置只是其中一种目前用的不多的加载方式,还有基于包扫描等加载bean的方法,此处仅为理解IoC的基本使用

2020-08-04鱼鱼
Java的socket通信
Java的socket通信网络编程中,会使用socket通信 TCP/IP协议,即Transmission Control Protocol/Internet Protocol,传输控制协议/网际协议,他使用TCP/IP四层模型(实际开发中只涉及到四层模型,软件范畴涉及不到OSI七层参考模型): TCP是面向连接的通信协议,通过三次握手建立连接,通讯完成时要拆除连接,由于TCP是面向连接的所以只能用于端到端的通讯 具有高度的可靠性 三次握手,即通信时,客户端和服务端共计要传输三次包,三次握手建立连接: 1.主机(客户端)发送 SYN=1(建立连接标识)和seq=x(序号),客户端进入SYN_SEND状态,等待服务端确认

2019-03-27鱼鱼