Earyant的技术博客

springBot配置大全（转载）

发表于 2017-07-28 更新于 2023-10-11
本文字数： 0 阅读时长 ≈ 1 分钟

七大查找算法

发表于 2017-07-27 更新于 2023-10-11
本文字数： 5.6k 阅读时长 ≈ 5 分钟

原文链接

查找算法分类：

1）静态查找和动态查找；
注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
2）无序查找和有序查找。
- 无序查找：被查找数列有序无序均可；
- 有序查找：被查找数列必须为有序数列。

1. 顺序查找

挨个查找，不用多说，时间复杂度为O(n);

2. 二分查找

说明元素必须是有序的，如果是无序的则要先进行排序操作。
基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

复杂度分析：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；

    //二分查找（折半查找），版本1
int BinarySearch1(int a[], int value, int n)
{
 int low, high, mid;
 low = 0;
 high = n-1;
 while(low<=high)
 {
     mid = (low+high)/2;
     if(a[mid]==value)
     return mid;
     if(a[mid]>value)
     high = mid-1;
     if(a[mid]<value)
     low = mid+1;
 }
     return -1;
}
 
//二分查找，递归版本
int BinarySearch2(int a[], int value, int low, int high)
{
   int mid = low+(high-low)/2;
   if(a[mid]==value)
   return mid;
   if(a[mid]>value)
   return BinarySearch2(a, value, low, mid-1);
   if(a[mid]<value)
   return BinarySearch2(a, value, mid+1, high);
}
```  


## 3. 插值查找

在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？

打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。<

同样的，比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5， 我们自然会考虑从数组下标较小的开始查找。

经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：

mid=(low+high)/2, 即mid=low+1/2*(high-low);

通过类比，我们可以将查找的点改进为如下：

mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，

也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。

* 基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。

* 注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
**如果分布比较均匀，插值查找比二分查找快，如果分布不均匀，二分查找比较快**
* 复杂度分析：查找成功或者失败的时间复杂度均为O(log2(log2n))。

//插值查找
int InsertionSearch(int a[], int value, int low, int high)
{
int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
if(a[mid]==value)
return mid;
if(a[mid]>value)
return InsertionSearch(a, value, low, mid-1);
if(a[mid]<value)
return InsertionSearch(a, value, mid+1, high);
}


## 4. 斐波那契查找

在介绍斐波那契查找算法之前，我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。

黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。

0.618被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。

大家记不记得斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。


* 基本思想：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。

相对于折半查找，一般将待比较的key值与第mid=（low+high）/2位置的元素比较，比较结果分三种情况：
   * 1）相等，mid位置的元素即为所求

   * 2）>，low=mid+1;

   * 3）<，high=mid-1。

斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1;

开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种

   * 1）相等，mid位置的元素即为所求

   * 2）>，low=mid+1,k-=2;

说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。

   * 3）<，high=mid-1,k-=1。

说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归 的应用斐波那契查找。

复杂度分析：最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。

```const int max_size=20;//斐波那契数组的长度
    
   /*构造一个斐波那契数组*/
   void Fibonacci(int * F)
   {
      F[0]=0;
      F[1]=1;
      for(int i=2;i<max_size;++i)
      F[i]=F[i-1]+F[i-2];
   }
    
   /*定义斐波那契查找法*/
   int FibonacciSearch(int *a, int n, int key) //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字
   {
      int low=0;
      int high=n-1;
    
      int F[max_size];
      Fibonacci(F);//构造一个斐波那契数组F
    
      int k=0;
      while(n>F[k]-1)//计算n位于斐波那契数列的位置
      ++k;
    
      int * temp;//将数组a扩展到F[k]-1的长度
      temp=new int [F[k]-1];
      memcpy(temp,a,n*sizeof(int));
    
      for(int i=n;i<F[k]-1;++i)
      temp[i]=a[n-1];
    
      while(low<=high)
   {
      int mid=low+F[k-1]-1;
      if(key<temp[mid])
   {
      high=mid-1;
      k-=1;
   }
      else if(key>temp[mid])
   {
      low=mid+1;
      k-=2;
   }
      else
   {
      if(mid<n)
      return mid; //若相等则说明mid即为查找到的位置
      else
      return n-1; //若mid>=n则说明是扩展的数值,返回n-1
   }
   }
      delete [] temp;
      return -1;
   }
    
      int main()
   {
      int a[] = {0,16,24,35,47,59,62,73,88,99};
      int key=100;
      int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key);
      cout<<key<<" is located at:"<<index;
      return 0;
   }

5. 树表查找

5.1 最简单的树表查找算法——二叉树查找算法。

基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。

二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：

1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3）任意节点的左、右子树也分别为二叉查找树。

二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。

不同形态的二叉查找树如下图所示：
- 复杂度分析：它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡（比如，我们查找上图（b）中的“93”，我们需要进行n次查找操作）。我们追求的是在最坏的情况下仍然有较好的时间复杂度，这就是平衡查找树设计的初衷。

基于二叉查找树进行优化，进而可以得到其他的树表查找算法，如平衡树、红黑树等高效算法。

5.2 平衡查找树之2-3查找树（2-3 Tree）

2-3查找树定义：和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下：

1）要么为空，要么：
2）对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key要小，右节点也是一个2-3节点，所有的值比key要大。
3）对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的key还要大。
2-3查找树的性质：

1）如果中序遍历2-3查找树，就可以得到排好序的序列；

2）在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。（这也是平衡树中“平衡”一词的概念，根节点到叶节点的最长距离对应于查找算法的最坏情况，而平衡树中根节点到叶节点的距离都一样，最坏情况也具有对数复杂度。）
- 复杂度分析：
2-3树的查找效率与树的高度是息息相关的。

在最坏的情况下，也就是所有的节点都是2-node节点，查找效率为lgN
在最好的情况下，所有的节点都是3-node节点，查找效率为log3N约等于0.631lgN
距离来说，对于1百万个节点的2-3树，树的高度为12-20之间，对于10亿个节点的2-3树，树的高度为18-30之间。

5.3 平衡查找树之红黑树（Red-Black Tree）

2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgn，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，于是就有了一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）。

基本思想：红黑树的思想就是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。

跳跃表

发表于 2017-07-27 更新于 2023-10-11
本文字数： 37 阅读时长 ≈ 1 分钟

看这篇文章

和B+树很像，不过B+树插入需要Rebalance进行树重调整。

Mysql索引B+树

发表于 2017-07-27 更新于 2023-10-11
本文字数： 308 阅读时长 ≈ 1 分钟

看这篇文章讲的很好

B - 树（Balance Tree）

二叉查找树的时间复杂度是O(log(n)) 已经够快了，但是二叉查找树的查找速度取决于树的高度。
B - 树，每个节点包含最多k个孩子，k被称为阶，k的大小取决于磁盘页的大小。

一个 m 阶的 B 树具有如下几个特征

根节点至少有两个子女。
每个中间节点包含k-1个元素和k个孩子，其中m/2 <= k <= m
每个叶子节点都包含k-1个元素，其中 m/2 <= k <=m
所有叶子节点都位于同一层
每个节点中的元素从小到大排列，节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域分划。

B+树

在b-树基础上进行改造，将索引全部建在叶子节点上，非叶子节点指向叶子节点的大小。

看这篇文章

100块钱可以兑换50块、10块、5块、1块的算法

发表于 2017-07-26 更新于 2023-10-11
本文字数： 760 阅读时长 ≈ 1 分钟

最先想到的当然是for循环了：

public static void main(String[] args) {
   long time1 = System.currentTimeMillis();
           System.out.println("当前时间为"+time1);
           int n = 0;
           int n1, n5, n10, n50;
           for (n1 = 0; n1 < 100; n1++) {
               for (n5 = 0; n5 < 20; n5++) {
                   for (n10 = 0; n10 < 10; n10++) {
                       for (n50 = 0; n50 < 2; n50++) {
                           if (n1 * 1 + n5 * 5 + n10 * 10 + n50 * 50 == 100) {
                               n++;
                               System.out.println("1块的：" + n1 + "张 5块的： " + n5 + "张 10块的 ：" + n10 + "张 50块的：" + n50 + "张");
                           }
                       }
                   }
               }
           }
           long time2 = System.currentTimeMillis();
           System.out.println("结束时间为"+time2);
           long time = time2 - time1;
           System.out.println(n + " 耗费时间为 " + time);
}

很容易得出结果154.但是耗费时间为 1501038954420 - 1501038954413 =7;
虽然时间耗费不是很多，但是通过打印信息可以看出来，50为2的时候只有一种情况，却空跑了很多空循环。

SpringCloud学习5路由网关(zuul)

发表于 2017-07-21 更新于 2023-10-11
本文字数： 1.4k 阅读时长 ≈ 1 分钟

在微服务架构中，需要几个关键的组件，服务注册与发现、服务消费、负载均衡、断路器、智能路由、配置管理等，由这几个组件可以组建一个简单的微服务架构，如下图：

注意：A 服务和 B 服务是可以相互调用的，作图的时候忘记了。并且配置服务也是注册到服务注册中心的。

客户端的请求首先经过负载均衡（zuul、Ngnix），再到达服务网关（zuul 集群），然后再到具体的服务，服务统一注册到高可用的服务注册中心集群，服务的所有的配置文件由配置服务管理（下一篇文章讲述），配置服务的配置文件放在 Git 仓库，方便开发人员随时改配置。

一、Zuul 简介

Zuul 的主要功能是路由和过滤器。路由功能是微服务的一部分，比如／api/user 映射到 user 服务，/api/shop 映射到 shop 服务。zuul 实现了负载均衡。

zuul 有以下功能：

Authentication
Insights
Stress Testing
Canary Testing
Dynamic Routing
Service Migration
Load Shedding
Security
Static Response handling
Active/Active traffic management

二、准备工作

继续使用上一节的工程。在原有的工程上，创建一个新的工程。

三、创建 service-zuul 工程

 <dependency>
        <groupId>org.springframework.cloud</groupId>
        <artifactId>spring-cloud-starter-eureka</artifactId>
    </dependency>
    <dependency>
        <groupId>org.springframework.cloud</groupId>
        <artifactId>spring-cloud-starter-zuul</artifactId>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-web</artifactId>
    </dependency>

    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-test</artifactId>
        <scope>test</scope>
    </dependency>

在其入口 applicaton 类加上注解 @EnableZuulProxy，开启 zuul：

filterType：返回一个字符串代表过滤器的类型，在 zuul 中定义了四种不同生命周期的过滤器类型，具体如下：
pre：路由之前
routing：路由之时
post：路由之后
error：发送错误调用
filterOrder：过滤的顺序
shouldFilter：这里可以写逻辑判断，是否要过滤，本文 true, 永远过滤。
run：过滤器的具体逻辑。可用很复杂，包括查 sql，nosql 去判断该请求到底有没有权限访问。

SpringCloud学习4断路器（Hystrix）

发表于 2017-07-21 更新于 2023-10-11
本文字数： 980 阅读时长 ≈ 1 分钟

在微服务架构中，我们将业务拆分成一个个的服务，服务与服务之间可以相互调用（RPC）。为了保证其高可用，单个服务又必须集群部署。由于网络原因或者自身的原因，服务并不能保证服务的 100% 可用，如果单个服务出现问题，调用这个服务就会出现网络延迟，此时若有大量的网络涌入，会形成任务累计，导致服务瘫痪，甚至导致服务 “雪崩”。
为了解决这个问题，就出现断路器模型。

断路器简介

Netflix 已经创建了一个名为 Hystrix 的库来实现断路器模式。在微服务架构中，多层服务调用是非常常见的。
较底层的服务如果出现故障，会导致连锁故障。当对特定的服务的调用达到一个阀值（hystric 是 5 秒 20 次）断路器将会被打开。
断路打开后，可用避免连锁故障，fallback 方法可以直接返回一个固定值。

在 ribbon 使用断路器

改造 serice-ribbon 工程的代码：

在 pox.xml 文件中加入：
org.springframework.cloud spring-cloud-starter-hystrix
在程序的入口类加 @EnableHystrix：
改造 HelloService 类，加上 @HystrixCommand，并指定 fallbackMethod 方法。

Feign 中使用断路器

如果你使用了 feign，feign 是自带断路器的，并且是已经打开了。如果使用 feign 不想用断路器的话，可以在配置文件中关闭它，配置如下：

feign.hystrix.enabled=false

Circuit Breaker: Hystrix Dashboard (断路器：hystrix 仪表盘)

基于 service-ribbon 改造下：

pom.xml 加入：

org.springframework.boot spring-boot-starter-actuator

    <dependency>
        <groupId>org.springframework.cloud</groupId>
        <artifactId>spring-cloud-starter-hystrix-dashboard</artifactId>
    </dependency>

在主程序入口中加入 @EnableHystrixDashboard 注解，开启 hystrixDashboard：

  该仪表盘可以查看错误率

SpringCloud学习3服务消费者feign

发表于 2017-07-21 更新于 2023-10-11
本文字数： 328 阅读时长 ≈ 1 分钟

使用feign

spring-cloud-starter-eureka
spring-cloud-starter-feign
spring-boot-starter-web
spring-boot-starter-test

配置文件

eureka:
client:
serviceUrl:
defaultZone: http://localhost:8761/eureka/
server:
port: 8765
spring:
application:
name: service-feign

开启feign

在程序的入口类，需要通过注解 @EnableFeignClients 来开启 feign:
调用服务
定义一个 feign 接口类, 通过 @ FeignClient（“服务名”），来指定调用哪个服务：

SpringCloud学习2服务消费者

发表于 2017-07-21 更新于 2023-10-11
本文字数： 993 阅读时长 ≈ 1 分钟

在上一篇文章，讲了服务的注册和发现。在服务架构中，业务都会被拆分成一个独立的服务，服务与服务的通讯是基于 http restful 的。spring cloud 有两种调用方式，一种是 ribbon+restTemplate，另一种是 feign。在这一篇文章首先讲解下基于 ribbon+rest。

ribbon

是一个负载均衡客户端，可以很好的控制 http 和 tcp 的一些行为。Feign 也用到 ribbon，当你使用 @ FeignClient，ribbon 自动被应用。
ribbon 已经默认实现了这些配置 bean：
- IClientConfig ribbonClientConfig: DefaultClientConfigImpl
- IRule ribbonRule: ZoneAvoidanceRule
- IPing ribbonPing: NoOpPing
- ServerList ribbonServerList: ConfigurationBasedServerList
- ServerListFilter ribbonServerListFilter: ZonePreferenceServerListFilter
- ILoadBalancer ribbonLoadBalancer: ZoneAwareLoadBalancer

准备工作

基于上一节的工程，启动 eureka-server 工程；启动 service-hi 工程，它的端口为 8762；将 service-hi 的配置文件的端口改为 8763, 并启动它，这时你会发现：service-hi 在 eureka-server 注册了 2 个，这就相当于一个小的集群。访问 localhost:8761 如图所示：

新建一个service-ribbon

spring-cloud-starter-eureka
spring-cloud-starter-ribbon
spring-boot-starter-web
spring-boot-starter-test

想eureka注册一个客户端

eureka:
   client:
     serviceUrl:
       defaultZone: http://localhost:8761/eureka/
 server:
   port: 8764
 spring:
   application:
     name: service-ribbon

启动类

在工程的启动类中, 通过 @EnableDiscoveryClient 向服务中心注册；

架构如下

SpringCloud学习1EurekaServer

发表于 2017-07-20 更新于 2023-10-11
本文字数： 456 阅读时长 ≈ 1 分钟

创建EurekaServer

Idea初始化项目

选择cloud discovery->eureka server 。

创建启动类

@EnableEurekaServer

配置参数

server:
  port: 8761

eureka:
  instance:
    hostname: localhost
  client:
    registerWithEureka: false
    fetchRegistry: false
    serviceUrl:
      defaultZone: http://${eureka.instance.hostname}:${server.port}/eureka/

创建EurekaClient

初始化项目

通server

创阿金启动类

@EnableEurekaClient

配置参数

 eureka:
   client:
     serviceUrl:
       defaultZone: http://localhost:8761/eureka/
 server:
   port: 8762
 spring:
   application:
     name: service-hi

查找算法分类：

1. 顺序查找

2. 二分查找

5. 树表查找

5.1 最简单的树表查找算法——二叉树查找算法。

5.2 平衡查找树之2-3查找树（2-3 Tree）

5.3 平衡查找树之红黑树（Red-Black Tree）

B - 树（Balance Tree）

一个 m 阶的 B 树具有如下几个特征

B+树

最先想到的当然是for循环了：

断路器简介

在 ribbon 使用断路器

Feign 中使用断路器

Circuit Breaker: Hystrix Dashboard (断路器：hystrix 仪表盘)

在主程序入口中加入 @EnableHystrixDashboard 注解，开启 hystrixDashboard：

使用feign

配置文件

开启feign

调用服务

ribbon

准备工作

新建一个service-ribbon

想eureka注册一个客户端

启动类

架构如下

创建EurekaServer

Idea初始化项目

创建启动类

配置参数

创建EurekaClient

初始化项目

创阿金启动类

配置参数