文章字数：918,阅读全文大约需要3分钟

五个常用的算法思想

贪婪算法

1. 特性

• 局部最优解，总是找出当前看来最好的选择，而不是从整体考虑
• 局部最优解通常不是全局最优
• 想要通过贪婪算法找到最优解，通常需要严谨的数学证明

2. 计算过程

• 将问题拆解成若干个子问题
• 选择子问题的最优解
• 将子问题的解合并成问题的解

3. 例子

• 背包问题： 有若干个重量、价值不同的物体，在背包承重固定的情况下找出能拿走加个最高的组合。
• 策略1: 找最贵的拿，直到再拿就超重
• 策略2: 拿最重的
• 策略3: 拿最轻的
• 策略4: 拿性价比最高的
  最后可以比较所有策略的结果，去出最优的
  结果只是接近最优，但是性能大幅提升

动态规划算法

1. 动态规划法能解决具有以下特点的问题

• 最优子结构: 可以把局部问题结合起来得出全局最优解
• 重复子问题: 计算最优解的过程中会处理很多相同的问题

2. 原理

• 一个问题是另一个问题状态转移后的到的，所以计算每一步的状态转移过程即可的到最终答案

3. 例子

• 斐波那契数列的计算
• 斐波那契数列第二项之后的元素都是前两个元素之和
• 如果每次都从头计算，会有很多重复的运算
• 直接将每次的结果都保存下来，接下来计算每项都直接从结果集中取前两项的值

分治算法

1. 将大问题分成若干小问题，再把小问题划分下去。直到base cases，解决之后一步步向上，最终解决大问题
2. 例子: 快速排序

回溯算法

• 回溯算法和暴力破解很像，但是优点在于排除了很多不可能的步骤

1. 原理

• 遍历元素时如果得出此方法不通，则直接返回。

2. 例子: N皇后问题

• 加入有N*N的棋盘，要在上面放上N个皇后，并保证N个都无法吃掉对方
• 即不在一行，不在一列，不在对角线上
• 每一个棋子都是一个循环
• 当最后一个棋子确定此路不同时，结束循环
• 父循环进入下一次循环

3. 其它例子: 深度优先遍历

分支限界算法

• 和回溯法类似，但是分支限界算法是从广度上进行排除不可能的步骤的
• 回溯法是找到一个解就深入下去，直到判断无解，然后放弃一整条路径，进入下一个
• 分支限界算法是先把所有的最外层问题解出来，然后再去除不可能的。
• 然后再从可能的中进入下一次子问题

文章字数：99,阅读全文大约需要1分钟

• 监听复制事件
• 读取剪贴板的内容
• 追加信息到剪贴板

1
2
3
4
5
6
7
8
9
10
11

window.oncopy = function(e){
    var selecttion = window.getSelection().toString();
    if(e.clipboardData){
        e.clipboardData.setData('text/plain', selecttion + '这是大勇哥的博客：https://blog.csdn.net/zy444263/article/details/83827697')
    }else if(window.clipboardData){
        //ie浏览器
        window.clipboardData.setData('text/plain', selecttion + '这是大勇哥的博客：https://blog.csdn.net/zy444263/article/details/83827697')
    }
    //阻止默认行为，否则无法重置被选中的内容。
    e.preventDefault();
}

文章字数：105,阅读全文大约需要1分钟

apache的BeanUtils.copyProperties（from,to）可以实现实体类属性复制，但是空属性不会忽略。在网上找到了一种方法可以忽略空属性

忽略空属性的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static String[] getNullPropertyNames (Object source) {
        final BeanWrapper src = new BeanWrapperImpl(source);
        java.beans.PropertyDescriptor[] pds = src.getPropertyDescriptors();

        Set<String> emptyNames = new HashSet<String>();
        for(java.beans.PropertyDescriptor pd : pds) {
            Object srcValue = src.getPropertyValue(pd.getName());
            if (srcValue == null) emptyNames.add(pd.getName());
        }
        String[] result = new String[emptyNames.size()];
        return emptyNames.toArray(result);
    }

    public static void copyPropertiesIgnoreNull(Object src, Object target){
        BeanUtils.copyProperties(src, target, getNullPropertyNames(src));
    }
//使用
BeanUtils.copyProperties(examLifeStyle, examDetail, getNullPropertyNames(examLifeStyle));

文章字数：122,阅读全文大约需要1分钟

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
33
34
35
36
37
38
39
40
41
42
43

/**
 * 将canvas的内容保存成图片
 */
function saveAsPng(canvasOb, name) {
    if(name == null || name == "") {
        name = "img";
    }
    var type = "image/png";
    var imgData = canvasOb.toDataURL({format: type});
    var base64Str = imgData.substr(22, imgData.length);
    var blob = base64ToBlob(base64Str, type);
    downloadByBlob(blob, name + "png");
}

/**
 * 将base64数据转换成blob文件对象
 */
function base64ToBlob(b64data, type) {
    var byteCharacters = atob(b64data);
    var byteArrays = [];
    for (var offset = 0; offset < byteCharacters.length; offset += 512) {
      var slice = byteCharacters.slice(offset, offset + 512);
      var byteNumbers = [];
      for (var i = 0; i < slice.length; i++) {
          byteNumbers.push(slice.charCodeAt(i));
      }
      byteArrays.push(new Uint8Array(byteNumbers));
    }
    var result = new Blob(byteArrays, {type: type})
    result = Object.assign(result,{preview: URL.createObjectURL(result)});
    return result;
}

/**
 * 根据指定的blob对象和文件名调用浏览器下载文件
 */
function downloadByBlob(blob, fileName) {
    var link = document.createElement("a");
    link.download = fileName + ".png";
    link.href = URL.createObjectURL(blob);
    link.click();
}

文章字数：553,阅读全文大约需要2分钟

java是自动管理内存的语言，需要知道对象是否存活已决定是否清理对象。

引用计数法

1. 方式: 每当有一个地方引用对象，对象计数器+1，引用失效-1
2. 判断方式: 计数不为0时存活，否则判断死亡
3. 优点: 简单实现，高效判断
4. 缺点: 如果对象相互引用，但是没有其它对象引用这两个。这两个对象会一直相互引用

引用链法

1. 方式

• 可达性分析
• 第一次标记，筛选
• 第二次标记，筛选

2. 可达性分析

• 一系列的GC Roots对象作为起点，向下搜索
• GC Root对象有: 虚拟机栈中的引用对象、JNI引用对象、方法区中常量、类静态属性引用的对象。
• GC Root不可达代表对象不可用
• 不可达对象再经过两次标记筛选后才会加入优先级很低的销毁队列

3. 第一次标记筛选

• 条件: 判断该对象是否有必要执行finalize()方法
  需要执行（需要设置）则筛选出来进入下一次筛选
  没必要则判定死亡，执行回收

4. 第二次标记筛选

• 对象存放在F-Queue队列中，被一个自动建立，优先级低的Finalizer线程去执行finalize()。
• finalize()方法如果没有或者执行过一次，则视为没必要执行

文章字数：147,阅读全文大约需要1分钟

能够将对象写入到文件，并从文件中读取的操作（序列化，反序列化）

使用方法

1. 需要被序列化的类必须实现Serializable接口，最好声明字段private static final long serialVersionUID = 1L;表示序列化对象的版本，防止多个序列化版本时冲突。

2. 被序列化的类加上get set方法

3. 序列化反序列化

1
2
3
4
5
6
7
8
9
10
11
12

Student s1 = new Student("zhangsan");
Student s2 = new Student("lisi");
// 写入
ObjectOutputStream os=new ObjectOutputStream(new FileOutputStream("test.txt"));
os.writeObject(s1);
os.writeObject(s2);
os.close();
// 读取
ObjectInputStream ois=new ObjectInputStream(new FileInputStream("test.txt"));
Student s1=(Student) ois.readObject();
Student s2=(Student) ois.readObject();
ois.close();

4. 多个类读取比较麻烦，可以保持在集合里再序列化到文件中。

文章字数：207,阅读全文大约需要1分钟

嵌入式调用

• Tomcat7RunnerCli引导类
• 嵌入式tomcat的启动依赖于Tomcat7Runner调用Tomcat api
• org.apache.catalina.startup.Tomcat的api，用于嵌入式启动

手写嵌入式Tomcat

• 新建Tomcat对象
• 设置端口
• 设置Context目录
• 添加Servlet
• 调用Tomcat.start()
• 强制Tomcat等待

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public static void main(String[] args) {
    String classpath = System.getProperty("user.dir");//目录绝对路径
    Tomcat tomcat = new Tomcat();
    tomcat.setPort(9090); // 端口绑定，也可以使用tomcat.getConnector().serPort(9091);
    Host host = tomcat.getHost(); // 设置Host
    host.setName("localhost"); // 和xml设置一样
    host.setAppBase("webapps"); // 根据xml设置

    // --- 基础配置完成
    // 加载class,加入 启动工程
    Context context = tomcat.addContext(host, "/", "classpath ");
    if(context  instanceof StandardContext) {
        StandardContext standardContext = (StandardContext)context;
        context  .setDefaultContextXml("d:/tomcat/conf/web.xml");
        // wrapper 是Servlet的基本单元
        Wrapper wrapper = tomcat.addServlet("/", "DemoServler", new DemoServlet);
        wrapper.addMapping("/demo.do");
    }
    // --- 启动
    tomcat.start(); // 启动
    tomcat.getServer().await(); // server等待，防止main运行完直接结束
}

文章字数：1003,阅读全文大约需要4分钟

一、Map

1.1hash冲突解决

• 开放寻址
• 再散列
• 链地址法

1.2 ConcurrentHashMap

• HashTable使用sync锁方法实现线程安全，效率低。
• putIfAbsent() 比HashMap多了一个方法，如果存在设置
• ConcurrentHashMap使用了分段存储的原理，分段锁

##1.8之前

1. 会根据并发度将数据分成若干区域Segment
2. 每个区域都继承了可重入锁，即线程每次只会锁区域。
3. 区域下是table,再下一级是HashEntry。
4. get和set会先将hash进行再散列
5. 然后根据并发度取模，得出位于那个区域内。
6. get方法没有加锁，因为数据是volatile修饰的，有修改马上体现（链表不是，遍历时可能会不一致，弱一致性）
7. 扩容只会扩容当前区域的map
8. size()会尝试两次不加锁的获取，一致返回，不一致全部加锁获取。

1.8后

1. 取消了区域segment只维护一个数组，锁粒度更小
2. 链表+红黑树(8个以内链表，之后用红黑树，查询效率高(O(logn)))

• sizeCtl

1. 负数，进行初始化或扩容，-1正则初始化，-N,有n+1个线程在扩容

2. 正数，0没初始化，>0初始化或下次扩容的阈值

3. 初始化时会检测sizeCrl的值，如果<0,表示有线程在初始化或扩容，让出运行权。

4. 并发扩容，如果线程发现有线程在扩容，会帮助扩容然后再插入。

5. put方法先再hash保证分布均匀，其次判断是否扩容，最后CAS插入

6. get方法主要是定位，用hash值根据当前table大小取模

二、其他容器

2.1ConcurrentSkipListMap

• SkipList跳表，空间换时间，每次插入都会随机判断是否当作索引。

2.2ConcurrentLinkedQueue

2.3写时复制容器

• CopyOnWriteArrayList
• CopyOnWriteArraySet
• 每次写都会创建一个新的容器，创建完将引用转到新的容器
• 数据一致性不高
• 空间占用大

三、阻塞队列

• 队列满的时候，插入元素线程阻塞，直到队列不满
• 队列空的时候，获取元素线程阻塞，直到有数据

3.1 常用方法

3.2 阻塞队列接口

• BlockingQueue阻塞队列接口

3.3常用实现类

• ArryBlockingQuenue一个数组结构组成的有界阻塞队列(先进先出，需要初始大小)
• LinkedBlockingQuenue一个链表组成的有界阻塞队列(先进先出，默认初始Integer.Max_Value)
• PriorityBlockingQueue支持优先级排序的无界阻塞队列(默认自然排序，优先级需要实现compareTo())
• DelayQueue使用优先级队列实现的无界阻塞延时队列，到期才能取出(内部元素必须实现Delayed，定义compareTo根据等待时间排序，getDelay获取剩余时间)
• SynchronousQueue不存储元素的阻塞队列，每个put都要对应一个take，速度很快，生产者和消费者需要匹配。
• LinkedTransferQueue链表结构组成的无界队列(transfer()消费者消费后，才返回。tryTransfer()立刻消费了则返回true否则返回false)
• LinkedBlockingDeque链表组成的双向阻塞队列(可以从头和尾插入和移除元素，fork/join工作窃取的实现)，方法名是addLast、addFirst这样的方式区分。

文章字数：817,阅读全文大约需要3分钟

高并发场景下，消息队列常用于流量削峰，解耦等作用。

基本标准

1. 消息可靠，不丢失信息
2. 支持集群
3. 性能好，满足绝大部分要求。
4. 开源，发现问题可以修改源码
5. 社区活跃，用的人多大部分问题都能提前发现

RabbitMQ

使用Erlang编写，最早是为电信行业系统之间通讯设计。支持AMQP

特点：

1. 轻量级：轻量，开箱即用。容易部署和使用。
2. Exchange：生产者和队列之间加入了一个根据路由规则分发消息到不同的队列的功能。
3. 客户端支持语言多：支持很多种客户端语言

不足

1. 消息堆积支持不好：消息大量堆积性能急剧下降
2. 性能不好：每秒几万到十几万的数据量，比起其他几十万的（RabbitMQ）性能差一个数量级
3. Erlang：使用Erlang语言，拓展性不好，二次开发成本高（相对于java）

RocketMQ

阿里巴巴2012年开源的，后来捐赠给Apache。使用java开发，在阿里内部被广泛使用。

优点

1. 性能稳定，可靠：性能稳定，可靠性高，功能齐全。
2. 中文社区活跃，使用java开发：社区活跃，使用java开发，拓展和二次开发比较容易。
3. 延迟低：业务响应延时做了优化，大多数情况下毫秒级响应。
4. 性能好：每秒能处理几十万条信息

劣势

1. 与其它产品的集成和兼容性不足

kafka

期初是分布式日志提交系统

优点

1. 兼容性好：大数据相关的开源软件都会优先支持Kafka
2. 性能高：性能比RocketMQ还好一点，也是每秒几十万数据。足够多的客户端并发异步批量发送，在开启压缩情况下极限处理能力达到2000万条。

不足

1. 异步批量：异步批量的思想性能好，但是也带来延时较高的问题。

对比

文章字数：427,阅读全文大约需要1分钟

和红黑树相比旋转操作更多，频繁插入删除的情况下红黑树更优

概念

1. 二叉查找树

• 任意节点，若左子树不为空，则左子树上所有的节点值都小于它的根节点值
• 人员节点，若右子树不为空，则右子树上所有节点均大于它的节点值
• 左右节点都可以单独当做二叉查找树
• 利用二分查找法，查找的最大次数等于树的高度
• 在极端情况下，数可能会退化成链表。

2. 平衡二叉查找树（AVL）

• 具有二叉查找树所有的优点
• 每个节点的左子树和右子树高度差最多为1
• 每次插入后如果不满足条件2，则需要通过若干左旋右旋操作恢复平衡

需要平衡的类型

1. 左-左型

• 倾斜于左的情况，此时需要进行右旋。
• 即顺时针旋转两个节点，使父节点被自己的左孩子渠道，自己成为右孩子
  例1

  1 2 3 4 5

  9 / 右旋 5 5 ====> / \ / 4 9 4

  例2

  1 2 3 4 5 6 7

  6 4 / \ / \ 4 9 3 6 / \ 右旋 / / \ 3 5 ====> 2 5 9 / 2

2. 右-右型

• 倾斜于右的情况，和左-左型刚好相反

3. 右-左型

   1 2 3 4 5

   7 7 9 \ 先对10右旋，变成右-右型 \ 再左旋节点7 / \ 10 ======> 9 =====> 7 10 / \ 9 10

4. 左-右型

• 整体倾斜于左，但是新增的节点倾斜于右
• 和右-左型处理刚好相反