BenchMark介绍最近大佬叫我做下Benchmark，之前一直没接触过，顺便学习一波。
BenchMark 又叫做基准测试，主要用来测试一些方法的性能，可以根据不同的参数以不同的单位进行计算（例如可以使用吞吐量为单位，也可以使用平均时间作为单位，在 BenchmarkMode 里面进行调整）。
开始前的步骤项目使用的是 Maven，因此只要对 pom.xml 添加依赖即可。
123456789101112<dependency> <groupId>org.openjdk.jmh</groupId> <artifactId>jmh-core</artifactId> <version>1.19</version></dependency><dependency> <groupId>org.openjdk.jmh</groupId> <artifactId>jmh-generator-annprocess</ ...
前缀和一、什么是前缀和？一维前缀和：
有一个一维数组 和该数组的一维前缀和数组 ，则 和 满足以下关系：
二维前缀和：
有一个二维数组 和该数组的二维前缀和数组 （其同样是个二维数组），则 和 满足以下关系：
看公式可能有点懵，看底下的图更好理解。
右侧标注橙色的二维前缀和元素，其值是左侧的原二维数组中标注橙色的所有元素的和。
二、如何得到前缀和？一维前缀和：
很容易就可以发现：
代码实现如下：
123456for(int i=0;i<n;i++){ if(i==0) y[i]=x[i]; else y[i]=y[i-1]+x[i];}
二维前缀和：
二维前缀和实际上就是一个矩阵内值的和，而矩阵又可以由两个行数或列数少一的子矩阵组合后，删去重合部分再加上右下角的值来构成，也就是以下式子：
代码实现如下：
123456789for(int y=0;y<n;y++)//n行 for(int x=0;x<m;x++)//m列 { if(x==0&&y==0) b[ ...
lettuce-core版本: 5.1.7.RELEASE
在上一篇介绍了Lettuce是如何基于Netty与Redis建立连接的，其中提到了一个很重要的CommandHandler类，这一期会介绍CommandHandler是如何在发送Command到Lettuce中发挥作用的，以及Lettuce是如何实现多线程共享同一个物理连接的。还是先看一下我们的示例代码，这一篇主要是跟进去sync.get方法看看Lettuc是如何发送get命令到Redis以及是如何读取Redis的命令的。
1234567891011121314151617181920212223242526272829/** * @author xiaobing * @date 2019/12/20 */public class LettuceSimpleUse { private void testLettuce() throws ExecutionException, InterruptedException { //构建RedisClient对象，RedisClient包含了Re ...
首先计算模式字符串的散列函数, 如果找到一个和模式字符串散列值相同的子字符串, 那么继续验证两者是否匹配.
这个过程等价于将模式保存在一个散列表中, 然后在文本中的所有子字符串查找. 但不需要为散列表预留任何空间, 因为它只有一个元素.
基本思想
长度为M的字符串对应着一个R进制的M位数, 为了用一张大小为Q的散列表来保存这种类型的键, 需要一个能够将R进制的M位数转化为一个0到Q-1之间的int值散列函数, 这里可以用除留取余法.
举个例子, 需要在文本 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 查找模式 2 6 5 3 5， 这里R=10， 取Q=997, 则散列值为
2 6 5 3 6 % 997 = 613
然后计算文本中所有长度为5的子字符串并寻找匹配
3 1 4 1 5 % 997 = 508
1 4 1 5 9 % 997 = 201
……
2 6 5 3 6 % 997 = 613 (匹配)
计算散列函数
对于5位的数值, 只需要使用int就可以完成所有需要的计算, 但是当模式长度太大时, ...
redis
未读源码版本：redis-4.0.1源码位置：
dict.h：dictEntry、dictht、dict等数据结构定义。
dict.c：创建、插入、查找等功能实现。
一、dict 简介dict (dictionary 字典)，通常的存储结构是Key-Value形式的，通过Hash函数对key求Hash值来确定Value的位置，因此也叫Hash表，是一种用来解决算法中查找问题的数据结构，默认的算法复杂度接近O(1)，Redis本身也叫REmote DIctionary Server (远程字典服务器)，其实也就是一个大字典，它的key通常来说是String类型的，但是Value可以是String、Set、ZSet、Hash、List等不同的类型，下面我们看下dict的数据结构定义。
二、数据结构定义与dict相关的关键数据结构有三个，分别是：
dictEntry 表示一个Key-Value节点。
dictht表示一个Hash表。
dict是Redis中的字典结构，包含两个dictht。
dictEntry结构的代码如下：
123456789101112typedef struct d ...
redis
未读源码版本：redis-4.0.1源码位置：https://github.com/antirez/sds
一、SDS简介sds (Simple Dynamic String)，Simple的意思是简单，Dynamic即动态，意味着其具有动态增加空间的能力，扩容不需要使用者关心。String是字符串的意思。说白了就是用C语言自己封装了一个字符串类型，这个项目由Redis作者antirez创建，作为Redis中基本的数据结构之一，现在也被独立出来成为了一个单独的项目，项目地址位于这里。
sds 有两个版本，在Redis 3.2之前使用的是第一个版本，其数据结构如下所示：
1234567typedef char *sds; //注意，sds其实不是一个结构体类型，而是被typedef的char*，好处见下文struct sdshdr { unsigned int len; //buf中已经使用的长度 unsigned int free; //buf中未使用的长度 char buf[]; //柔性数组buf};
但是在Red ...
转的一个超级有意思，好懂的并查集解释， 膜拜大神~~
找了好久都没找到原帖大多都是转的 ， 后来在某评论下看到原帖链接啦 点这里哦
故事读完，并查集就会了~~~~~
江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人。这样一来，江湖上就形成了一个一个的帮派，通过两两之间的朋友关系串联起来。而不在同一个帮派的人，无论如何都无法通过朋友关系连起来，于是就可以放心往死了打。但是两个原本互不相识的人，如何判断是否属于一个朋友圈呢？
我们可以在每个朋友圈内推举出一个比较有名望的人，作为该圈子的代表人物。这样，每个圈子就可以这样命名“中国同胞队”美国同胞队”……两人只要互相对一下自己的队长是不是同一个人，就可以确定敌友关系了。
但是还有问题啊，大侠们只知道自己直接的朋友是谁，很多人压根就不认识队长!要判断自己的队长是谁，只能漫无目的的通过朋友的朋友关系问下去： ...
前言深度优先遍历（Depth First Search, 简称 DFS） 与广度优先遍历（Breath First Search）是图论中两种非常重要的算法，生产上广泛用于拓扑排序，寻路（走迷宫），搜索引擎，爬虫等，也频繁出现在 leetcode，高频面试题中。
本文将会从以下几个方面来讲述深度优先遍历，广度优先遍历，想信大家看了肯定会有收获。
深度优先遍历，广度优先遍历简介
习题演练
DFS，BFS 在搜索引擎中的应用
深度优先遍历，广度优先遍历简介深度优先遍历深度优先遍历主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。
树是图的一种特例（连通无环的图就是树），接下来我们来看看树用深度优先遍历该怎么遍历。
1、我们从根节点 1 开始遍历，它相邻的节点有 2，3，4，先遍历节点 2，再遍历 2 的子节点 5，然后再遍历 5 的子节点 9。
2、上图中一条路已经走到底了（9是叶子节点，再无可遍历 ...
动态规划问题一直是大厂面试时最频繁出现的算法题，主要原因在于此类问题灵活度高，思维难度大，没有很明显的套路做法。
也正是因为这个原因，我们将持续更新此回答来尝试破解面试中所涉及的动态规划问题。首先我们主要了解动态规划是什么，动态规划问题应该如何思考？
一共分成三个部分，具体内容框架如下所示：
一、宝石挑选问题引入小 Q 是一个宝石爱好者。
这一天，小 Q 来到了宝石古董店，店家觉得小 Q 是个宝石行家，于是决定和小 Q 玩一个游戏。
游戏是这样的，一共有 块宝石，每块宝石在小 Q 心中都有其对应的价值。注意，由于某些宝石质量过于差劲，因此存在只有店家倒贴钱，小 Q 才愿意带走的宝石，即价值可以为负数。
小 Q 可以免费带走一个连续区间中的宝石，比如区间 或区间 中的宝石。
请问小 Q 能带走的最大价值是多少？
问题分析首先思考最暴力的解法。
枚举所有区间，暴力累加区间中宝石的价值，最后选一个价值最大的区间。时间复杂度 。
显然有些无法接受，因此想想有没有办法优化，比如优化掉暴力累加的部分。
优化 1.0仔细思考不难发现，我们可以枚举区间右端点，然后固定右端点，左端点不断向 ...
mysql的行锁是通过索引加载的，即行锁是加在索引响应的行上的，要是对应的SQL语句没有走索引，则会全表扫描，行锁则无法实现，取而代之的是表锁。
1234567CREATE TABLE SIMPLE_USER( ID BIGINT (20) NOT NULL AUTO_INCREMENT, NAME VARCHAR (32) DEFAULT NULL, PHONE VARCHAR (11) DEFAULT NULL, ADDRESS VARCHAR (32) DEFAULT NULL, PRIMARY KEY (id)) ENGINE = INNODB AUTO_INCREMENT = 1 DEFAULT CHARSET = utf8;
如上面的建表语句，当执行如下update语句时，数据库对该表施加的是表锁。即在该update执行完之前，所有对该表的update是不允许的。
1UPDATE SIMPLE_USER SET ADDRESS='David Road' WHERE NAME='David';
当对 W ...
