数据结构与算法-字符串的匹配

Posted on 2019-07-09 | Edited on 2022-09-21 | In 数据结构与算法 , 算法

BF算法（buter force）

原理：分为主串和模串，在主串m中匹配模串n，所以主串有从0,1,2,3….到m-n个m-n+1个子字符串

时间复杂度：理论上是O(m*n),m是主串长度，n是子串长度。但是因为匹配到模串第一个不符合的就会返回进行下一次匹配所以实际效果会好不上。加上比较简单、易于排错所以一般工业会采用这种方法

代码示例：

public class BruteForce {
    private char[] main;
    private char[] pattern;


    public BruteForce(String main, String pattern) {
        this.main = main.toCharArray();
        this.pattern = pattern.toCharArray();
    }

    //暴力搜索的方法，总共有起始位置0，1，2，...n,m-n+1个子串，每个子串和摩串匹配时间复杂度是O(m-n)
    public int indexOf() {
        if (main.length < pattern.length) {
            return -1;
        }
        boolean eq = true;
        for (int i = 0; i <= main.length - pattern.length + 1; i++) {
            for (int j = 0; j < pattern.length; j++) {
                if (main[i + j] != pattern[j]) {
                    eq = false;
                    break;
                }
                eq = true;
            }

            if (eq) {
                return i;
            }
        }
        return -1;
    }
}

RK算法-RobinKrap

BF算法的优化，由于BF算法需要一个个比较子串，复杂度是O(m*n),所以KR对BF算法做了优化，预先将所有的子串的hash值计算出来然后吧子串的位置记录下来，计算模串的hash，然后在hash中查找，这样复杂度就是计算模串的O(n)+hash获取的O(1)。

代码

 public class RobinKrap {
    private char[] main;
    private char[] pattern;

    private Integer patternHash;

    private Map<Integer, Integer> hashMap = new HashMap<>();

    //本质和bf的方法一样，只是预先将0~m-n个n-m+1个子串的hash和位置预先计算出来保存起来，然后在查询时候用模的hash去匹配看是否存在
    public RobinKrap(String main, String pattern) {
        this.main = main.toCharArray();
        this.pattern = pattern.toCharArray();

        patternHash = this.pattern.hashCode();

        for (int i = 0; i < main.length() - pattern.length() + 1; i++) {
            hashMap.put(Arrays.copyOfRange(this.main, i, pattern.length()).hashCode(), i);
        }
    }


    public int indexOf() {
        return hashMap.containsKey(patternHash)?hashMap.get(patternHash):-1;
    }

    public static void main(String[] args) {
        String s = "abcdefghijklmnklmn";
        String p = "klmn";
        BruteForce bf = new BruteForce(s, p);
        int i = bf.indexOf();
        System.out.println(i);
        for (int idx = i; idx < i + p.length(); idx++) {
            System.out.print(s.charAt(idx));
        }
        System.out.println();
    }

}

数据结构与算法-图的广度和深度搜索

Posted on 2019-07-09 | Edited on 2022-09-21 | In 数据结构与算法 , 算法

问题：接上一篇文章我们用图这种数据结构存储好友之间的关系，那么我们如何获取2度、3度关系，或者说在迷宫中如何获取出口呢？

针对上述问题介绍俩种图的搜索算法广度搜索发（bfs）、深度搜索发(dfs)

BFS-广度搜索法–2、3度人脉

如图：
avator

原理：我们先从起点找到最近的点，然后逐层扩大直到找到终点或者找到我们需要的层级。代码如下：

public void search(Vertex end) {
    //借用队列，将下一个要查找的点入队列
    LinkedList<Vertex> queue = new LinkedList<>();
    //记录搜索过的点，找到值后跳过
    Set<Vertex> visited = new HashSet<>();
    //记录路径key是当前的点的下标，value是来源，打印时候通过递归层层找到最开始的起点
    Map<Integer, Integer> path = new HashMap<>();

    //添加起点坐标
    queue.add(list.get(0));
    visited.add(list.get(0));
    //初始化路径
    list.forEach(v -> {
        path.put(v.getVal(), -1);
    });

    //第一层结束后才开始第二层
    while (queue.size() > 0) {
        //队列出列
        Vertex v = queue.poll();
        for (Vertex adjV : v.getAdj()) {
            if (visited.contains(adjV)) {
                continue;
            }

            //修改path和visited
            visited.add(adjV);
            path.put(adjV.getVal(), v.getVal());
            if (adjV.equals(end)) {
                //找到终点打印
                GraphUtil.printPath(path, list.get(0), end.getVal());
                return;
            }
            queue.add(adjV);
        }
    }
}

时间复杂度：E代表边，V代表点，最坏情况下访问所有的边和点，即O(V+E),可以简写为O(E)。

//上述找到N度关系
    public List<Vertex> searchByDegree(List<Vertex> list, int degree) {
      //记录当前是第几度关系的容器
      LinkedList<DegreeVertex> queue = new LinkedList<>();
      Set<Vertex> visited = new HashSet<>();

      int i = 0;
      queue.add(new DegreeVertex(i, list.get(0)));
      visited.add(list.get(0));

      List<Vertex> ret = new ArrayList<>();
      while (queue.size() > 0) {
          DegreeVertex degreeVertex = queue.poll();
          //超过度直接返回
          if (degreeVertex.getDegree() > degree) {
              break;
          }

          i = degreeVertex.getDegree() + 1;
          for (Vertex adjV : degreeVertex.vertex.getAdj()) {
              if (visited.contains(adjV)) {
                  continue;
              }

              visited.add(adjV);
              if (i == degree) {
                  ret.add(adjV);
              }
              queue.add(new DegreeVertex(i, adjV));
          }
      }

      return ret;
  }

深度优先算法

原理：类似走迷宫的场景，主要采用回溯的思想，当一条道路走不通，往回退一步选择别的道路

如图：
avator

  public class DFS {

    private List<Vertex> graph = new ArrayList<>();

    //利用visited和path
    private Set<Vertex> visited = new HashSet<>();
    private Map<Integer, Integer> path = new HashMap<>();
    //用于结束递归的标记位发现后置为true停止递归
    private boolean found = false;

    public DFS(List<Vertex> graph) {
        this.graph = graph;
    }

    public void search(Vertex end) {
        graph.forEach(vertex -> {
            path.put(vertex.getVal(), -1);
        });
        search(graph.get(0), end);
        GraphUtil.printPath(path, graph.get(0), end.getVal());
    }

    public void search(Vertex start, Vertex end) {
        if (found) {
            return;
        }
        visited.add(start);
        if (start.equals(end)) {
            found = true;
            return;
        }

        for (Vertex adjV : start.getAdj()) {
            if (visited.contains(adjV)) {
                continue;
            }
            path.put(adjV.getVal(), start.getVal());
            visited.add(adjV);
            search(adjV, end);
        }
    }

}

时间复杂度，最坏情况下每个边访问俩遍所以是O(E)

数据结构与算法-图(graph)

Posted on 2019-07-07 | Edited on 2022-09-21 | In 数据结构与算法 , 数据结构

引言：我们如果存储、如何存储微博、微信等社交网络中的好友关系呢

定义

一种非线性数据结构。图中数据我们成为定点（vertex），图中数据的关系我们成为边（edge）。没个定点有多少条边我们成为度（dregee），有向图中，因为关系是有方向的，指向定点的边的数量我们称为入度（in-dregee），指向其他定点的边的数量称为初度（out-degree）如图：

avator

分类

针对图是否有方向我们可分为无向图，和有向图，另外在无向图中我们如果加入类似亲密度的概念还分为带权图

表示方法

临接矩阵存储法

底层用2维数组来表示：

无向图：i到j的距离a[i][j]设置为1，a[j][i]也设置为1
有向图：i指向j的距离a[i][j]设置为1。如果j指向[i]的距离也设置为1
带权图：同无向图是双向关系，只是存储的是权重

如图：
avator

邻接表储存法

上面的方法用来表示关系优点是比较直接，缺点是浪费空间，无向图和带权图下办部分空间几乎都浪费了。我们可以采用之前散列类似的方式来保存图的关系。

key为定点，那么到其他地方的关系我们可以在这个顶点后，他说有的边的关系用一个利于查找的数据结构保存（数组、链表、跳表、红黑树），因为链表的查询复杂度是O(N),我们可以考虑用红黑树查找、删除、添加，O(Log2N),跳表（log2N)来优化他。如图

avator

如何保存用户的关系

对于大量的而用户我们可以用mysql表来存储

a关注b,写入一条记录a->b状态1，0
b成为a的粉丝，写入一条记录b->a状态1，1
这时候只需要以a或者b把数据加载到内存中，用邻接表方式存储起来即可

CREATE TABLE `social_relation` (
  `id` bigint(11) unsigned NOT NULL AUTO_INCREMENT COMMENT 'pk',
  `u_id` char(32) DEFAULT NULL COMMENT '关注u_id',
  `follow_u_id` char(32) DEFAULT NULL COMMENT '被关注u_id',
  `follow_status` smallint(6) DEFAULT NULL COMMENT '关注状态位',
  `followed_status` smallint(11) DEFAULT NULL COMMENT '被关注状态位',
  PRIMARY KEY (`id`),
  UNIQUE KEY `uniq_uid_follow_u_id` (`u_id`,`follow_u_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

数据结构与算法-堆以及堆排序

Posted on 2019-07-02 | Edited on 2022-09-21 | In 数据结构与算法 , 数据结构

堆的特点以及实现

堆的定义：任意一个节点都大于（小于）他们的子节点，堆顶是最大（小）的元素，如果堆顶是最大的元素成为大顶堆，如果堆顶是最小的元素成为小顶堆

堆是完全二叉树，底层实现是通过数组实现。他们之间的关系如下：

下标为i的节点leftNode的下标是2i+1，rightNode是2(i+1)
下标为i的节点他的父节点是(i-1)/2

堆的几种操作原理

插入–自下而上的堆化

时间复杂度O(logN)

public void insert(int value) {
    if (count == capacity) {
        System.out.println("堆已经满了");
        return;
    }

    array[count] = value;
    int i = count;
    count++;
    //插入到堆最后一个节点，然后开始迭代，判断如果节点如果大于父节点交换俩个节点，这时候堆顶就是最大的数据
    while (i > 0) {
        int pIdx=(i - 1) / 2;
        if (array[i] > array[pIdx]) {
          swap(array,i,pIdx);
        }else{
          break;
        }
        i=pIdx;
    }
}

删除–自上而下的堆化

时间复杂度是O(logN)

//删除堆顶
public void delTop() {
    //删空了
    if (count == 0) {
        return;
    }
    
    //为了防止空洞直接，将最后一位数据和堆顶交换，删除最后一位数据，然后将新的堆顶自上而下的堆化
    array[0] = array[count - 1];
    array[count - 1] = 0;
    count--;
    heapify(array, count - 1, 0);
}

 //自上而下的堆化操作。遍历在自己的子节点中发现有比自己大的值，就和自己替换比较
private static void heapify(int[] a, int heapCapicity, int i) {
    while (true) {
        int top = i;
        //如果当前元素小于左子节点，将左子节点和当前节点值交换。
        if (2 * i + 1 <= heapCapicity && a[top] < a[2 * i + 1]) {
            top = 2 * i + 1;
        }
        //如果当前元素小于右子节点，将右子节点和当前节点值交换。
        if (2 * (i + 1) <= heapCapicity && a[top] < a[2 * (i + 1)]) {
            top = 2 * (i + 1);
        }

        //没变说明不需要交换直接跳出循环
        if (top == i) {
            break;
        }
        swap(a, top, i);
        i=top;
    }
}

堆排序的原理

大致分俩个步骤，升序为例建大顶堆，降序建小顶堆

建堆：整个数组的[0，n/2]是非叶子节点，对所有的非叶子节点进行自上而下的堆化操作。时间复杂度O(NlogN)
排序：因为堆顶元素是最大的，所以将堆顶和堆尾的元素交换，然后堆范围缩小1，再次交换堆顶，直到最后一位。时间复杂度O(NlogN)

public static void buildHeap(int a[]) {
    //从非叶子节点开始建堆
    for (int i = a.length / 2-1; i >= 0; i--) {
        heapify(a, a.length , i);
    }
}


public static int[] sort(int a[]) {
    buildHeap(a);
    System.out.println("buildHeap:"+Arrays.toString(a));

    //开始交换，直到剩下最后一个元素为止
    int swapIdx = a.length - 1;
    while (swapIdx > 1) {//注意剩下2个元素时候交换完后跳出循环
        swap(a, 0, swapIdx);//堆顶（Max）和交换区的元素交换
        swapIdx--;//缩小交换区
        heapify(a,swapIdx,0);//找第二大的元素
    }
    return a;
}

时间复杂度o(nlogn)

堆排序的缺点

堆是个完全二叉树无法想数组顺序访问那样很好的利用cpucache
堆排序数据的逆序度高。

堆的使用

优先级队列

java的优先级队列PriorityQueue实际上底层的实现就是堆，维护一个小（大）顶堆，堆顶就是队列的第一个元素。

类似的实现还有高性能定时器：我们定时任务都在一个队列中，通常的做法是每隔一段时间轮询队列，这样如果任务列表很长或者计算资源不足时候不是很精确同时也会浪费计算资源。我们如果用堆来实现的话，维护一个小顶堆，堆顶是最先执行的任务，我们定时器取堆顶的任务计算和现在的时间差T如果T>0,线程就睡眠T时间，这样节省了资源，当小于等于0时候开始执行任务，同时从堆中移除。

topn问题

N个文件中取topN，比较坏的做法是，每个文件取一个放在数组中，然后从第一个文件中取出来循环和数组中的数据比较，如果发现大于数组中的值就放入数组。这样时间复杂度很高；用堆的思想，我们可以我们可以维护一个元素为N的小顶堆，依次取文件如果发现比小顶堆小就插入到小顶堆中。

一个静态的大文件中取topn，静态文件我们可以维护一个元素为N的小顶堆，方式同上；动态数据我们可以始终维护一个小顶堆。

求中位数

场景：比如运维中求中位数，90分位等的要求，即100份，前0份或者90份的样本数的大小。如：1，2，3，4，5，6。中的3，4都可以做中位数，一般取3

方法：我们可以把样本数分为俩部分，用俩个堆来维护，前n/2的数据放在大顶堆中，后面的数据放在小顶堆中，大顶堆的堆顶就是中位数。当有新的样本数据插入时候判断如果小于大顶堆就插入到大顶堆中，否则就插入小顶堆中。这时候可能破坏了平衡，那么我们可以将新插入的那个堆的堆顶元素置换到另一个堆中来保持平衡

数据结构与算法-红黑树

Posted on 2019-06-28 | Edited on 2022-09-21 | In 数据结构与算法 , 算法

二叉搜索树在极限情况下会退化成链表，为了保证查找的稳定性，引入了平衡二叉搜索树，其中最有名的就是红黑树。

平衡二叉树定义

整棵树里左子树和右子树的高度不能相差1。类似的数据结构有：AVL树、伸展树、树堆、红黑树。

红黑树将节点标记为红节点或者黑节点，它的特点：

所有根节点都是黑节点;
子节点都是黑节点，且值为nil;
红节点不能相邻
每个节点到其叶子节点的所有路径经历的黑节点数都一样。

如何实现平衡

红黑树将所有红色节点去掉会变成四叉树，如图，在将四叉树的节点挂在子节点下，会变成完全二叉树。

avtor

红黑树的复杂度

如上所说,完全二叉树的事件复杂度【log2(N-1)~~log2N】,在把红色家进度复杂度不会超过2log2N。

二叉搜索树

Posted on 2019-06-25 | Edited on 2022-09-21 | In 数据结构与算法 , 数据结构

二叉查找树的定义（Binary Search Tree）

左子树每个节点的值要小于节点值，右子树每个节点的值都要大于该节点的值。对于大小相等的节点，两种做法，链表或者数组的方式保存，一种是当做大于该节点放在右子树，本文取第二种方法

二叉查找树的查找操作

遍历或者递归查找树，如果该值小于节点的值从左子树查找，如果大于大于根节点从有子树查找

//遍历方法
public static List<TreeNode> find(TreeNode tree, int value) {
    TreeNode p = tree;
    List<TreeNode> treeNodes = new ArrayList<>();
    while (p != null) {
        if (value >= p.value) {
            if (p.value == value) {
                treeNodes.add(p);
            }
            p = p.right;
        } else {
            p = p.left;
        }
    }

    return treeNodes;
}

//递归
public static List<TreeNode> find(TreeNode tree, int value) {
    TreeNode p = tree;
    List<TreeNode> treeNodes = new ArrayList<>();
    if (value < p.value && p.left != null) {
        findNodeByValue(p.left, value, treeNodes);
    }

    if (value >= p.value && p.right != null) {
       findNodeByValue(p.right, value, treeNodes);
    }
    return treeNodes;
}

private static void findNodeByValue(TreeNode tree, int value, List<TreeNode> treeNodes) {
    if (tree == null) {
        return;
    }

    if (value < tree.value) {
        findNodeByValue(tree.left, value, treeNodes);
    }else{
        // if (value >= tree.value)
        if (value == tree.value) {
            treeNodes.add(tree);
        }
        findNodeByValue(tree.right, value, treeNodes);
    }
}

二叉查找树的添加操作

新插入的值一般在叶子节点，所以遍历树，如果小于节点值，并且做节点是空就插入到左子树，如果大于节点的值并且节点为空插入有子树，否则继续遍历

//遍历
public static void insertNode(TreeNode treeNode, int v) {

    TreeNode p = treeNode;
    while (p != null) {
        if (v<p.value) {
            if (p.left == null) {
                p.left = new TreeNode(v);
                return;
            }

            p = p.left;
        } else {
            //
            if (p.right == null) {
                p.right = new TreeNode(v);
                return;
            }

            p = p.right;
        }
    }
}

//递归
public static void insertNode(TreeNode treeNode, int v) {
    TreeNode p = treeNode;
    if (v < p.value) {
        if (p.left == null) {
            p.left = new TreeNode(v);
            return;
        }
        insertNode(p.left, v);
    } else if (v >= p.value) {
        if (p.right == null) {
            p.right = new TreeNode(v);
            return;
        }
        insertNode(p.right, v);
    }
}

二叉查找树的删除

找到该节点，如果遇到冲突，放在数组中
如果查找的节点叶子节点直接将父节点指向null
1. 如果只有左（右）子树，将该节点指向改节点中的左（右）子树
2. 如果既有左子树，又有右子树，找第一个大于该节点的节点a，将a的值复制到该节点，然后删除a。
从数组逆向遍历一个个删除。

public static TreeNode delNode(TreeNode tree, int v) {
    //遍历树，找到相等节点放在eqNodes父节点放在pNodes
    TreeNode node = tree;
    List<TreeNode> eqNodes = new ArrayList<>();
    List<TreeNode> pNodes = new ArrayList<>();
    while (node != null) {
        if (v < node.value) {
            if (node.left!=null && node.left.value == v) {
                eqNodes.add(node.left);
                pNodes.add(node);
            }

            node = node.left;
        } else {
            if (node.right!=null && node.right.value == v) {
                eqNodes.add(node.right);
                pNodes.add(node);
            }
            node = node.right;
        }
    }

    //没有相等的
    if (eqNodes.size() == 0) {
        return tree;
    }

    //后续遍历相等的节点一次删除
    for (int i = eqNodes.size() - 1; i >= 0; i--) {
        node = eqNodes.get(i);
        TreeNode parent = pNodes.get(i);

        //同时有左右子树，找到右子树里最小的节点和父节点，将右子树最小的节点的值复制给之前要删除的节点
        while (node.left != null && node.right != null) {
            TreeNode minNode = node.right;
            TreeNode minPNode = node;
            while (minNode.left != null) {
                minPNode = minNode;
                minNode = minPNode.left;
            }

            //复制
            node.value = minNode.value;
            //删除右子树最小的节点
            node = minNode;
            parent = minPNode;
        }

        //找到child树，不会出现左右子树同时存在的情况：P
        TreeNode child = null;
        if (node.left != null) {
            child = node.left;
        } else if (node.right != null) {
            child = node.right;
        }

        //开始删除如果parent是空，删的是根节点，如果node<parent删除的是左子树，反之是右子树
        if (parent == null) {
            tree = child;
        } else if (node.value < parent.value) {
            parent.left = child;
        } else {
            parent.right = child;
        }
    }

    return tree;

}

时间复杂度

查找、删除、添加的逻辑都是类似的时间复杂度和树的高度相关。节点和高度的关系如下:
以完全二叉树为例，假设树的层级是H，非叶子节点是：1+2+4+8+…+(2的H-1次方)，叶子节点是【1~2的H次方】。H就是log(n-1)+1~Logn之间，所以时间复杂度是logN

最坏情况

破坏平衡退化成链表。

搜索树和散列比的其他功能

搜索数能很方便的找到最小节点、最大节点、找到前驱节点和后置节点代码如下。

搜索数如果想按从小到大打印可以通过中序遍历2Logn比散列要快。

和散列对比其他的优势：

散列虽然查找是o(1)，但是考虑到hash函数以及hash冲突要遍历链表以及开发寻址，所以不一定效率高
hash冲突导致性能不稳定，搜索树通过平衡性能很稳定
散列需要扩容和缩容额外需要资源
负载因子不能太大容易造成内存浪费

二叉树

Posted on 2019-06-25 | Edited on 2022-09-21 | In 数据结构与算法 , 数据结构

树定义

非线性的数据结构，线性数据结构（数组、链表等数据结构）。
树节点的关系：同级的节点叫做兄弟节点、下级节点叫做子节点、上级节点叫父节点、如果父节点为空叫做做根节点、最下层节点叫叶子节点。
常用的名词：
高度：从叶子节点到跟节点的距离
深度：从根节点到叶子节点的距离
层：深度-1

二叉树

满二叉树：所有叶子节点均在最后一层，除叶子节点以外的节点都是满节点状态。
完全二叉树：所有叶子节点均在最后俩层，最后一层的叶子节点都在左边，并且非叶子节点都是满节点状态。

二叉树的遍历

见代码，都会用到递归算法。

//前序遍历：自己-->left-->right
public static void frontForeach(TreeNode node) {
    if (node != null) {
        System.out.println(node.value);
        frontForeach(node.left);
        frontForeach(node.right);
    }
}

//中序遍历：left-->自己-->right
public static void midForeach(TreeNode node) {
    if (node != null) {
        midForeach(node.left);
        System.out.println(node.value);
        midForeach(node.right);
    }
}

//后续遍历：left-->right-->自己
public static void backForeach(TreeNode node) {
    if (node != null) {
        backForeach(node.left);
        backForeach(node.right);
        System.out.println(node.value);
    }
}

什么样的二叉树适合用数组表示

满二叉树以及完全二叉树适合用数组标识因为节点的公式是,根节点是数组下标为1的元素开始，他的子节点节点依次是2(arrayIndx)，2(arrayIndx)+1。因为普通的二叉树会浪费很多空间。

hash算法的应用

Posted on 2019-06-19 | Edited on 2022-09-21 | In 数据结构与算法 , 数据结构

hash算法的标准

不能逆向推导出原数据
对输入数据很敏感，改了一bit，最后得到的hash值也不相同
散列冲突概率很小
算法执行效率高

应用场景

安全加密

我们在保存数据时候可以对数据用hash函数进行加密比如：MD5、SHA、DES、AES

hash算法做安全加密应该尽量避免hash冲突，但是也不可能完全避免，但是概率很低比如MD5的范围如下：

1	2^128=340282366920938463463374607431768211456

加密算法越高级效果越好，但是相应的性能会越差

唯一标识

我们可以通过hash函数作为数据的唯一标识，比如对一个图片的搜索我们如果一个个比对他们的2进制码会很耗时，我们可以抽样踩点进行hash计算，然后hash相同的在去比较是否。

数据校验

大数据可能会被分块保存，我们只需要记录每一块的hash值，当文件块下载完成后进行hash值的校验，校验文件是否完整

散列函数

因为hash函数冲突的概率很低，所以我们可以利用hash作为散列函数

负载均衡

session-sticky模式的访问，对于客户端请求hash之后和服务器个数取模，这样保证每个请求都打到同一个后端

数据分片

对于海量数据我们可以将数据hash之后分散到各服务器节点中，这样在计算的时候根据数据hash取模到某个服务器节点计算（map-reduce思想）

分布式存储

海量数据根据数据的hash分片落到某一个节点上，理论上可以存储无数的数据，常用于nosql的存储，不过要注意一致性hash，防止节点变更大量的数据进行rehash。

Nginx--常用参数

Posted on 2019-06-15 | Edited on 2022-09-21 | In Nginx

proxy_redirect

语法：proxy_redirect [ default|off|redirect replacement ]
默认值：proxy_redirect default
上下文：http, server, location
作用：修改从被代理服务器传来的应答头中的”Location”和”Refresh”字段

比如：Nginx监听的端口是80，请求http://www.a.com:8080/ 就会报错，这时候如果设置了【proxy_redirect：http://www.a.com:8080/ /】即可定位到这里

client_max_body_size

语法：client_max_body_size [ 8m ]
默认值：1m;
默认值：proxy_redirect default
上下文：http, server, location
作用：request的body大小的限制，如果reqeustBody体较大记得设置入上传图片，否则request会413.

client_body_buffer_size

语法：client_body_buffer_size[ 512k ]
默认值：proxy_redirect 8k
上下文：http, server, location
作用：requestbody的buffer限制，如果requestbody小于buffer，requestBody会写入到内存中，如果大于这个值会写入到临时文件中，临时文件默认在/tmp,可以通过client_body_temp设置目录，注意读写权限。

proxy_connect_timeout

语法：proxy_connect_timeout [ 60s ];
默认值：proxy_connect_timeout 60s;
上下文：http, server, location
作用：nginx与upstream server的连接超时时间

proxy_send_timeout

语法：proxy_send_timeout [ 60s ];
默认值：proxy_send_timeout 60s;
上下文：http, server, location
作用：nginx发送数据至upstream server超时, 默认60s, 如果连续的60s内没有发送1个字节, 连接关闭

proxy_read_timeout

语法：proxy_read_timeout [ 60s ];
默认值：proxy_read_timeout 60s;
上下文：http, server, location
作用：nginx接收upstream server数据超时, 默认60s, 如果连续的60s内没有收到1个字节, 连接关闭

proxy_buffering

语法：proxy_buffering on|off
默认值：proxy_buffering 0n
上下文：http,server,location
作用：开启从后端被代理服务器的响应内容缓冲，upstream服务器会将响应保存在proxy_buffer_size和proxy_buffers指定的缓冲器内

proxy_buffer_size

语法：proxy_buffer_size the size
默认值：proxy_buffer_size 4k/8k
上下文：http,server,location
作用：该指令设置缓冲区大小,从代理后端服务器取得的第一部分的响应内容,会放到这里.小的响应header通常位于这部分响应内容里边.默认来说,该缓冲区大小等于指令 proxy_buffers所设置的;但是,你可以把它设置得更小。

proxy_buffers

语法：proxy_buffers 数量大小
默认值：proxy_buffers 8 4k/8k
上下文：http,server,location
作用：设置缓冲区的大小和数量,从被代理的后端服务器取得的响应内容,会放置到这里. 默认情况下,一个缓冲区的大小等于内存页面大小,可能是4K也可能是8K,这取决于平台。(getconf PAGE_SIZE 查看)

RestTemplate的优化

Posted on 2019-06-15 | Edited on 2022-09-21 | In java , spring

用RestTemplate上传图片发现请求经常超时，修改了下ClientHttpRequestFactory明显有所改善。mark下，具体见代码

@Configuration
public class RestConfigure {

    @Autowired
    private HttpLogInterceptor httpLogInterceptor;

    @Bean
    public RestTemplate restTemplate() {
        RestTemplate restTemplate = new RestTemplate();
        restTemplate.setRequestFactory(clientHttpRequestFactory());
        restTemplate.setInterceptors(Collections.singletonList(httpLogInterceptor));
        return restTemplate;
    }

    @Bean
    public HttpClientConnectionManager poolingConnectionManager() {
        PoolingHttpClientConnectionManager poolingConnectionManager = new PoolingHttpClientConnectionManager();
        // 连接池最大连接数
        poolingConnectionManager.setMaxTotal(Runtime.getRuntime().availableProcessors()*2);
        // 每个路由的最大连接数
        poolingConnectionManager.setDefaultMaxPerRoute(Runtime.getRuntime().availableProcessors()*2);
        return poolingConnectionManager;
    }

    @Bean
    public HttpClientBuilder httpClientBuilder() {
        HttpClientBuilder httpClientBuilder = HttpClientBuilder.create();
        //设置HTTP连接管理器
        httpClientBuilder.setConnectionManager(poolingConnectionManager());
        return httpClientBuilder;
    }

    @Bean
    public ClientHttpRequestFactory clientHttpRequestFactory() {
        //比 HttpComponentsClientHttpRequestFactory 性能好上传一个10MB文件从10s-->400ms
        OkHttp3ClientHttpRequestFactory clientHttpRequestFactory = new OkHttp3ClientHttpRequestFactory();
        // 链接超时，毫秒
        clientHttpRequestFactory.setConnectTimeout(1000);
        // 读写超时，毫秒
        clientHttpRequestFactory.setWriteTimeout(10000);
        clientHttpRequestFactory.setReadTimeout(10000);
        return clientHttpRequestFactory;
    }

}

Liu hao

励志当好厨子的程序员

RSS

GitHub E-Mail