链表中的算法

链表

链表是通过指针串联起来的线性结构，每个节点由两部分组成，一个是数据域，一个是指针域，数据域存储数据，指针域储存指向下一节点的指针，最后一个节点指针域是null。

链表类型

  • 单链表

  • 双链表，指针域包含两个指针，分别指向上一个节点的指针和指向下一个节点的指针

  • 循环链表，最后一个节点的指针域指向起始位置

链表存储方式

  • 数组

  • 非数组

链表的重要操作

  • 删除节点，将指向删除节点的指针指向删除节点的下一个节点

  • 添加节点

链表操作的方式

  • 直接使用原来的链表进行操作

  • 设置虚拟头结点进行操作

常用算法

  • 双指针

  • 快慢指针

数组中的算法

数组的特性

  • 数组下标从0 开始

  • 数组是内存连续的

二分查找

  • 适用场景：有序数组

  • target 在左闭右闭即[left, right]的区间: 循环条件l <= r, 左半部分选择r = m - 1;

  • target 在左闭右开即[left, right)的区间:循环条件l < r, 左半部分选择r = m;

双指针法

  • 适用条件：对数组或链表需要两次for循环的算法

  • 快慢指针，快指针寻找需要处理的下标，慢指针指向下一个覆盖的下标

  • 相向指针，类似循环指针，在某个位置朝相反方向移动

滑动窗口

  • 窗口内是什么，一般是符合需求的子串

  • 如何移动起始位置，起始位置对应的数据不符合子串需求

  • 如何移动结束位置，结束位置对应的数据仍然符合子串需求

一致性hash算法

    一致性hash算法的使用场景，缺点，解决方案

使用场景

    解决负载均衡

  • 分配请求

  • 分配服务

解决负载均衡的方法

  • 轮流：一个一个来，轮流需要每个服务或数据都是一致的

  • 加权轮流

  • hash算法，不同的请求按照hash永远落在对应的位置，但hash算法系统扩容缩容，所有的数据都要重新分配

  • 一致性hash算法

一致性hash算法

  • 所有的请求按照 $2^{32}$ 取模

  • 存储节点对 $2^{32}$ 取模

  • 根据请求的模，在hash环上顺时针找到第一个节点，这样如果扩容或缩容影响的数据量就很少了

  • 一致性hash算法解决负载均衡采用虚拟节点，即一个节点映射为多个hash环上的节点

大型网站页面静态化方案

为什么要静态化
  • 提高访问性能
  • SEO优化友好
方案一：网页HTML化

  • 管理后台调用新闻服务创建文章成功后，发送消息到消息队列
  • 静态服务监听消息，把文章静态化，即生成html文件
  • 在静态服务器上面安装一个文件同步工具，此工具的功能可以做到只同步有变动的文件，做增量同步，rsync和inotifywait
  • 通过同步工具把html文件同步到所有的web服务器

缺点

  • 页面无法修改

  • 页面同步实时性不好，多台服务器不一定同时同步，负载均衡下刷新页面可能有是有内容有时又没有了

  • html文件太多，无法维护

  • 同步工具不稳定

方案二：伪静态化

  • 管理后台调用新闻服务创建文章成功后，发送消息到消息队列

  • 缓存服务监听消息，把文章内容缓存到缓存服务器上面

  • 用户发起请求，web服务器根据id，直接查询缓存服务器

  • 获取数据返回给用户

缺点

  • 缓存压力大

  • 缓存维护难度大

方案三：布局样式模板化

  • 分发层做负载均衡，利用hash一致性进行分发

  • 应用层利用openresty+lua，使用html模板和nginx级的缓存

  • 缓存层：jvm缓存+redis分布式缓存

Linux监听文件目录变化并同步

    大型高并发的CMS新闻网站为了访问性能以及SEO，一般采用页面静态化方案。

    静态化方案指由一个服务将新的内容静态化为HTML文件，web服务器直接将静态HTML提供给浏览器，不经过数据库或内存计算。

    

    页面静态化中，需要将新生成的HTML同步给分布式的服务器，此时会用到文件目录监听工具和同步工具。最常用的是rsync和inotifywait。inotifywait监控文件夹变化；rsync同步变化的文件内容，可同步到本机的其他目录或者远程服务器上。

安装 rsync

1
2
3
4
5
wget http://rsync.samba.org/ftp/rsync/src/rsync-3.1.1.tar.gz
tar zxvf rsync-3.1.1.tar.gz 
./configure –prefix=/usr/local/rsync-3.1.1
make
make install

安装 inotifywait

1
2
3
4
5
6
wget http://github.com/downloads/rvoicilas/inotify-tools/inotify-tools-3.14.tar.gz
tar zxvf inotify-tools-3.14.tar.gz
cd inotify-tools-3.14
./configure
make
make install

创建并运行脚本

    新建脚本 inotifywait.sh

1
2
3
4
5
6
7
8
9
#!/bin/bash
# 监控的路径
export CNROMS_SRC=/home/ftpuser/gri/
inotifywait --exclude '\.(part|swp)' -r -mq -e  modify,move_self,create,delete,move,close_write $CNROMS_SRC |
  while read event;
    do
    rsync -vazu --progress  --password-file=/etc/rsyncd_rsync.secret  /home/ftpuser/gri/sla  rsync@10.208.1.1::gri ##这里执行同步的命令，可以改为其他的命令

  done

    启动脚本

1
nohup sh inotifywait.sh > /dev/null 2>&1

指数对数

指数

指数是幂运算aⁿ(a≠0)中的一个参数，a为底数，n为指数，指数位于底数的右上角。

幂运算表示指数个底数相乘。

指数重要定理

当n是一个正整数，aⁿ表示n个a连乘。

当n=0时，aⁿ=1。

当n<0时，aⁿ=1/a-ⁿ。

同底数幂相乘，底数不变，指数相加；

同底数幂相除，底数不变，指数相减。

幂的幂，底数不变，指数相乘。

对数

对数函数是以幂（真数）为自变量，指数为因变量，底数为常量的函数。

如果b=aⁿ，即a的n次方等于b（a>0且a!=1），那么数n叫做以a为底b的对数。其中a叫做对数b的底数，b叫做真数，n叫做以a为底，b的对数。

对数函数

一般地，函数y=logaX（a>0，且a≠1）叫做对数函数，也就是说以幂（真数）为自变量，指数为因变量，底数为常量的函数，叫对数函数。

其中x是自变量，函数的定义域是（0，+∞），即x>0。它实际上就是指数函数的反函数，可表示为x=aⁿ。因此指数函数里对于a的规定，同样适用于对数函数。

对数函数的底数为什么要大于0且不为1？【在一个普通对数式里 a<0，或=1 的时候是会有相应b的值。但是，根据对数定义：log以a为底n的对数；如果a=1或=0那么log以a为底n的对数就可以等于一切实数（比如log11也可以等于2，3，4，5，等等）】

通常我们将以10为底的对数叫常用对数（common logarithm），并记为lgN。另外，在科学计数中常使用以无理数e=2.71828···为底数的对数，以e为底的对数称为自然对数（natural logarithm），并且记为InN。

在实数范围内，负数和零没有对数；

log以a为底1的对数为0（a为常数） 恒过点（1，0）。

重要对数公式

项目关键节点应该做什么

转载公众号：Bella的技术轮子

1.项目立项

做一个项目之前，你要清楚为何要做这个项目，这个项目的价值和意义在哪里？如果是现有版本的大升级，那你还需要清晰的知道目前版本存在哪些问题，痛点是什么，扩展性如何，可维护性如何等等。同时还要确定升级后的版本的目标，只有目标确定了，后面技术方案选型的时候，你才会知道应该选取哪种技术方案，因为你选的技术方案，要能足够实现你的目标。

对于中台项目而言，还要考虑2个问题，即兼容性和差异性。所谓的兼容性，即指升级后的版本是否可以无缝兼容新接入一个行业？接入成本有多高？是否可以把一部分接入工作交由产品 or 运营同学来做，解放一部分技术同学劳动力？所谓差异性，即指升级后的版本是否可以支持不同行业间存在的差异，是否可以做到相互隔离，互不影响。

一般情况下，我会选择用思维导图来表达这些信息，图往往会比文字更简明直观一些，TL们的接受度也更高一些。

2.技术预研

这一阶段的主要目的就是基于上一阶段确定的目标，调研哪些技术可以支撑你实现这个目标，这些技术理论上的可行能否最准转变为落地上的可行，可以拿当前业务场景以及数据做一个推演，数据推演ok之后，可以再做一个小的可以运行的demo，以证明该技术真正可以用在此项目中。

此阶段需要产出各个技术选型的数据推演图，如果推演过程比较复杂的话，也可以考虑再产出一份比较详细的Excel样式的数据推演图，每一个步骤数据如何变化都要体现出来。另外，还需要产出各个技术选型可运行的demo。最后，需要产出各种技术选型的对比，表格形式或思维导图形式都可以，切忌纯文字。基于上述对比，确定最终的技术选型，然后就可以开始技术方案的编写啦~

3.技术方案编写

私以为技术方案应该包含以下几部分，业务背景、场景分析、系统架构、应用架构、系统流程图、领域模型设计、存储模型设计、全局可用定义、功能模块设计、接口定义、项目里程碑等等，如果是需要出海的项目，还需要考虑下本地化方式、时区偏移、部署方式等等。

3.1 业务背景

业务背景主要是交代下做这个项目的背景，即为什么要做这个项目，基于一个什么样的业务背景，也可以把【1.项目立项】中画的思维导图直接放在这一pa。

3.2 场景分析

场景分析则主要是讲这个系统有哪些应用场景，如果能够列举出业务方的真实诉求，那是最好不过了。然而大多数程序员的生活，并不会直接对接业务方同学，而是对接产品经理。

3.3 系统架构

系统架构推荐以图的方式来展示。开局一张图，剩下全靠讲，也不是不可以哈。Bella酱就有过这种经历，开局我放了一张图，然后看着大佬们讲了3个多小时。佩服佩服，那次经历也让我懂得，表达方式是何等重要。一般情况下我会这么画系统架构图，主要侧重于表达用了哪些中间件、什么数据源、什么应用、开放什么SPI、以及这其中各组件之间是如何交互的，最终可以支撑哪些业务。

3.4 应用架构

应用架构仍然推荐图的方式来表达。我一般这么画应用架构图，主要侧重于表达应用由哪些模块组成，每个模块包含哪些功能，各模块之间的层次关系，哪些应用包含哪些模块。另外，这张图中也是可以把用了哪些中间件、什么数据源，支持哪些业务场景画上的，这样这张图会更完整一些，即使不看系统架构图，单单看这一张图，也是可以明白整个项目的设计的。

3.5 系统流程图

系统流程图以流程图为主，可以辅以文字说明，或者表格说明，由于这个和业务逻辑紧密相关，此处不再举例。

3.6 领域模型设计

领域模型设计，这一阶段是非常有必要的，先确定领域模型，后再根据领域模型确定存储模型，并非所有的领域模型都要转换为存储模型，从而保存到数据库中。领域模型设计过程中，要十分清楚系统整体流程图，可以结合上个阶段的系统流程图，来推演一下，根据这些领域模型是否可以推演出系统的正常正确运行。图为主，辅以必要的文字说明此领域模型设计如何让系统运行即可。

3.7 存储模型设计

存储模型设计，需要详细到表中每个字段的设计，字段类型、是否为主键、是否需要建索引、是否可为空、是否为分表字段等等。表结构设计表格展示即可。存储模型设计，还是建议图片的形式表达，方便展示各表之间的关系。

3.8 全局可用定义

全局可用定义，主要定义一些通用的方法、枚举类、共同的约定等，以避免各个应用or各开发人员定义一套自己的方法、枚举等，以确保同一个字段or同一个方法等在系统内唯一。

3.9 功能模块设计

功能模块设计，即各模块的详细设计，这里应该尽可能详细，可以举一些例子，确保负责此模块开发的同学看文档即可明白要做什么，以及如何做。必要的话，可以各模块再出一个详细的技术方案。

3.10 接口定义

接口定义，呐，不多做解释，记得写清楚入参、出参、接口名字，入参和出参记得用自定义类来接收，不要忘记实现序列化哟~

BaseResult、isSuccess、getData、getErrorMessage、buildErrorResponse、buildSuccessResp这些基础的类和方法也不要忘记呀！

3.11 项目里程碑

项目里程碑，即项目的时间节奏，例如开发时间、联调时间、提测时间、发布时间等，此时也应该确定各种资源了，确保相关同学可以在你计划的时间范围内投入项目中。

3.12 其他

如果你的项目需要出海，那你还需要考虑系统的部署方式、本地化、时区偏移、系统所需中间件是否支持等等。

4.项目过程把控

只有好的方案，项目过程把控不到位，最终也是无法交付一个令人满意的产品的。那如何才能使项目按照既定计划有序进行，同时又能保证交付的质量呢？

作为一个项目的owner，你需要做：

  1. 技术方案要切实可行
  2. 明确整个项目的时间节奏，每个阶段应该交付什么可衡量的结果，每个阶段之间的关联性，不能按时交付的影响
  3. 明确每个人所做的事情，每个事情需要做多久，交付结果是什么
  4. 是否可阶段性提测，阶段性验证
  5. 识别项目中存在的风险，风险是否可控
  6. 大促封网，和上下游依赖这些因素也要考虑
  7. 测试人员等相关人员需要提前锁定

具体到action上面，则可以考虑下下面这些：

  1. 日会了解每个人的进度、风险点、需要协助的点等
  2. 各个阶段的可运行单测是必须的
  3. 定期review代码(例如一周一次)，check真实进度，owner或owner&相应开发人员参加即可
  4. 制定开发规范，保证代码风格统一
  5. 功能拆分尽可能细，一个功能点最好不要超过5天，尽量控制在3天之内
  6. 开发整体自测ok之后，对项目进行整体code review，同时提测
  7. code review之后修改的代码，全部修改完毕之后，要进行整体的回归测试，回归测试期间除bug问题，不允许再修改代码
  8. 发布避开大促封网，发布之前确定依赖方发布时间点，看下发布顺序有木有要求

其中，应重点关注项目中的风险，无论是何种原因，自己可控or不可控因素造成的，现状偏离计划的事情，都属于项目风险，应尽早抛出来，而且应尽可能保证你希望看到这一风险的人看到。其次，风险不是抛出来就完事了，还要考虑下是否可以cover掉这一风险，是否需要其他人协助，需要的话，也应尽早提出来。最后，尽可能多给测试留一些时间，你永远不知道测试过程中会发现什么问题。

5.交付清单

交付清单的意义不仅仅在于给到产品同学，让他check他所提的需求我们已实现，还在于我们自身对这个项目的一个回顾，另外，交付清单也可以给到测试同学一个最强王者辅助的作用，测试人员对比交付清单即可知道本次项目的所有功能，方便他们测试。所以，交付清单应尽可能详细，和TC 不冲突哦~

推荐思维导图+Excel+文字的形式展现。

6.发布前准备

主要是一些资源准备，例如线上服务器、线上DB、线上mq等等各种中间件及资源的准备。

其次，将项目中用到的SNAPSHOT 版本二方包替换为正式版二方包，替换完，记得再回归测试一下。

另外，还需要确定依赖的上下游的发布时间，如果此次发布依赖上下游的发布时间，需要和他们协商好具体的发布时间，确定到几点，以方便我们到点check他们是否发布，以决定我们是否可以发布。

咳咳，发布前也可以写一些工具，假如线上数据出现问题，可以通过这些工具修复数据。一名合格的数据卫士不应该直接订db，而应该通过工具来修复。项目上线，相应的工具也同步上线。

7.发布

发布过程中，需要看各种监控，确保此次发布没有问题，才能继续大范围发布。

发布完成，还应该有线上测试环节，以check线上功能可用。

同时，需要跟进几天线上监控、报警、日志等，确保没有问题后，才算此次发布顺利完成。

8.复盘

个人的复盘是必须的，原因我就不多说了。这里的复盘指的不是你对外分享/宣讲等等的复盘，而是对你内心那个真实的自己来讲的复盘，在这个项目中自己究竟有没有成长，成长了哪些，哪些地方做的好，哪些地方做的不好，不好的地方下次可不可以避免or解决，这个项目有没有偏离你的初衷等等。

线程本地变量ThreadLocal

线程本地变量ThreadLocal

线程本地变量只能被本线程访问，不能被其他线程访问。

ThreadLocal相关核心类

  • Thread，有两个属性threadLocals，inheritableThreadLocals，用来保存线程本地变量，threadLocals由ThreadLocal.class维护，inheritableThreadLocals由InheritableThreadLocal.class维护

    1
    2
    3
    4
    5
    6
    7
    8
    9
    /* ThreadLocal values pertaining to this thread. This map is maintained
     * by the ThreadLocal class. */
    ThreadLocal.ThreadLocalMap threadLocals = null;

    /*
     * InheritableThreadLocal values pertaining to this thread. This map is
     * maintained by the InheritableThreadLocal class.
     */
    ThreadLocal.ThreadLocalMap inheritableThreadLocals = null;

  • ThreadLocal 保存线程本地变量的工具类

  • ThreadLocal.ThreadLocalMap，保存线程本地变量的容器，K是ThreadLocal实例化对象，值为变量值，保存形式是ThreadLocal.ThreadLocalMap.Entry数组，值在数组的下标由ThreadLocal实例化对象hash后获取

  • ThreadLocal.ThreadLocalMap.Entry，保存线程本地变量K-V的类，K是弱引用

  • WeakReference，弱引用， 当对象仅被弱引用指向，不被其他强引用指向，不论内存空间是否足够，GC都回收。

常用ThreadLocal
  • ThreadLocal 操作线程本地变量
  • InheritableThreadLocal 可以读取父线程以及本线程的变量
常见问题
  • ThreadLocal可以跨线程使用吗
  • ThreadLocal会内存泄漏吗
重要源码阅读
  • inheritableThreadLocals初始化
1
2
// Thread 类： 获取父线程
Thread parent = currentThread();
1
2
3
4
// 如果使用inheritThreadLocals 则根据父线程本地变量创建本地线程本地变量
if (inheritThreadLocals && parent.inheritableThreadLocals != null)
    this.inheritableThreadLocals =
        ThreadLocal.createInheritedMap(parent.inheritableThreadLocals);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// ThreadLocal类： 创建ThreadLocalMap，从父线程把变量循环放入本地线程变量
private ThreadLocalMap(ThreadLocalMap parentMap) {
    Entry[] parentTable = parentMap.table;
    int len = parentTable.length;
    setThreshold(len);
    table = new Entry[len];

    for (int j = 0; j < len; j++) {
        Entry e = parentTable[j];
        if (e != null) {
            @SuppressWarnings("unchecked")
            ThreadLocal<Object> key = (ThreadLocal<Object>) e.get();
            if (key != null) {
                Object value = key.childValue(e.value);
                Entry c = new Entry(key, value);
                int h = key.threadLocalHashCode & (len - 1);
                while (table[h] != null)
                    h = nextIndex(h, len);
                table[h] = c;
                size++;
            }
        }
    }
}
  • ThreadLocal.ThreadLocalMap的set方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
private void set(ThreadLocal<?> key, Object value) {

    // We don't use a fast path as with get() because it is at
    // least as common to use set() to create new entries as
    // it is to replace existing ones, in which case, a fast
    // path would fail more often than not.

    Entry[] tab = table;
    int len = tab.length;
    int i = key.threadLocalHashCode & (len-1);

    for (Entry e = tab[i];
         e != null;
         e = tab[i = nextIndex(i, len)]) {
        ThreadLocal<?> k = e.get();

        if (k == key) {
            e.value = value;
            return;
        }

        if (k == null) {
            replaceStaleEntry(key, value, i);
            return;
        }
    }

    tab[i] = new Entry(key, value);
    int sz = ++size;
    if (!cleanSomeSlots(i, sz) && sz >= threshold)
        rehash();
}