最近，某个项目需要上线一个功能，需要对请求进来的流量进行控制，也就是我们常说的限流。“限流”，通过字面意思也能猜到是要干什么的，但是，它是怎么实现的？使用了那种算法？为什么要这样实现？可能就不大理解了。在这之前，我也是这样，只知其然不知其所然。

1. 为什么要限流

一个系统，面临大数据量，高并发的访问时，将出现无法提供服务，或请求响应超时等情况，严重的，在连锁反应下导致系统崩溃。这时候，对请求进行限流就很有必要了。通过限流，当请求达到一定的并发数或速率，就进行让请求等待、排队、降级、拒绝服务等，平缓进入系统的请求数峰值。

2. 常用的限流算法

常用的限流算法有两种，分别是漏桶算法，令牌桶算法。

1. 漏桶算法
   
   漏桶算法是将请求放入到漏桶中，桶中的请求按照一定的速率出去。突发大流量请求，经过漏桶算法控制后，将以恒定的速率进入网络。

2. 令牌桶算法
   
   固定容量的令牌桶可自行以恒定的速率产生令牌。如果令牌不被消耗，或者被消耗的速度小于产生的速度，桶内的令牌累积，直到把桶填满。后面再产生的令牌就会从桶中溢出抛弃。请求进来时，需要先从令牌桶中获取到令牌，方能被系统处理及响应。否则，被直接拒绝服务。

总结：
漏桶算法直接强制限制了请求的速率，无论多大的并发请求数，都会以恒定的速率出现。当一个系统的请求处理速率大于漏桶算法的限制速率时，面对突发的大流量，将会出现大量请求被拒绝，而系统利用率低的情况，在这个时候，漏桶算法就不合适了。此时，就要用令牌桶算法。令牌桶在容量固定，在请求量平缓且低于令牌生成速率（令牌生成速率及令牌桶容量要根据系统的处理能力设置）时，令牌桶是满的，面对突发的大流量，令牌桶容量大小的请求数能获取到令牌，降低流量峰值的同时，避免大量请求被丢弃。请求流量平缓进入系统，直到与令牌生成速率持平。
两种算法原理是不同的，但都能达到限流的目的，我们可以结合实际场景使用。比如，当调用的第三方系统处理能力有限，且没有相应的限流机制，这个时候，有突发大流量，为了第三方系统的稳定，就必须抛弃掉多余的流量。使用漏桶算法，刚好可以达到这个目的。相反，作为被调用方，在无法预测有多大的流量进入己方系统时，就可以使用令牌桶算法限流，即使在大流量请求到来，也能平缓过渡。

3. 限流实例

Google开源工具包Guava提供了限流工具类RateLimiter，该类基于令牌桶算法来完成限流，我们可以导入相应的包进行使用。

<dependency>
       <groupId>com.google.guava</groupId>
       <artifactId>guava</artifactId>
       <version>20.0</version>
</dependency>

3.1 调用代码：

3.2 限流工具类RateLimiter：

/**
     * Acquires the given number of permits from this {@code RateLimiter} if it can be obtained
     * without exceeding the specified {@code timeout}, or returns {@code false} immediately (without
     * waiting) if the permits would not have been granted before the timeout expired.
     * 如果没有超过延时时间，能够从令牌桶获取到指定数量的令牌就返回true；
     * 或者在延时结束时还没有获取到令牌，就返回false（没有指定延时时间 timeout，就马上返回false）
     * @param permits the number of permits to acquire
     * @param timeout the maximum time to wait for the permits. Negative values are treated as zero.
     * @param unit the time unit of the timeout argument
     * @return {@code true} if the permits were acquired, {@code false} otherwise
     * @throws IllegalArgumentException if the requested number of permits is negative or zero
     */
    public boolean tryAcquire(int permits, long timeout, TimeUnit unit) {
        long timeoutMicros = max(unit.toMicros(timeout), 0);
        // 入参校验
        checkPermits(permits);
        long microsToWait;
        // 同步块，解决并发获取令牌的情况
        synchronized (mutex()) {
            long nowMicros = stopwatch.readMicros();
            // 马上能获取到令牌或者在延时时间内能获取到令牌 canAcquire(nowMicros, timeoutMicros)
            if (!canAcquire(nowMicros, timeoutMicros)) {
                return false;
            } else {
                // 预定下一张令牌，返回下一张令牌生成需等待的时间
                microsToWait = reserveAndGetWaitLength(permits, nowMicros);
            }
        }
        stopwatch.sleepMicrosUninterruptibly(microsToWait);
        return true;
    }

3.3 令牌桶限流效果

     相信很多同行小伙伴会因为许多原因想跳槽，不论是干得不开心还是想跳槽涨薪，在如此内卷的行业，我们都面临着“面试造火箭，上班拧螺丝”的局面，鉴于当前形势博主呕心沥血整理的干货满满的造火箭的技巧来了，本博主花费2个月时间，整理归纳java全生态知识体系常见面试题！总字数高达百万！ 干货满满，每天更新，关注我，不迷路，用强大的归纳总结，全新全细致的讲解来留住各位猿友的关注，希望能够帮助各位猿友在应付面试笔试上！当然如有归纳总结错误之处请各位指出修正！如有侵权请联系博主QQ1062141499!

---

目录

2 最快速度求两个数组之交集算法与hash

3 用Java实现最快速度的数组交集

4 判断两个链表是否相交

5 java计算字符串中出现次数最多的字符

---

 在开发高并发系统时有三把利器用来保护系统：缓存、降级和限流

• 缓存 缓存的目的是提升系统访问速度和增大系统处理容量
• 降级 降级是当服务出现问题或者影响到核心流程时，需要暂时屏蔽掉，待高峰或者问题解决后再打开
• 限流 限流的目的是通过对并发访问/请求进行限速，或者对一个时间窗口内的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务、排队或等待、降级等处理

常用的限流算法

漏桶算法

      漏桶算法思路很简单，水（请求）先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会直接溢出，可以看出漏桶算法能强行限制数据的传输速率。

 下面时伪代码：

public class TokenBucketDemo {
    public long timeStamp = getNowTime();
    public int capacity; // 桶的容量
    public int rate; // 水漏出的速度
    public int water; // 当前水量(当前累积请求数)
    public boolean grant() {
        long now = getNowTime();
        water = max(0, water - (now - timeStamp) * rate); // 先执行漏水，计算剩余水量
        timeStamp = now;
        if ((water + 1) < capacity) {
            // 尝试加水,并且水还未满
            water += 1;
            return true;
        }
        else {
            // 水满，拒绝加水
            return false;
        }
    }
}

       漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是固定的参数，所以即使网络中不存在资源冲突（没有发生拥塞），漏桶算法也不能使某一个单独的流突发到端口速率。因此，漏桶算法对于存在突发特性的流量来说缺乏效率。

令牌桶算法

       对于很多应用场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。如图所示，令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。

令牌桶算法图例 

 

 

 

　a. 按特定的速率向令牌桶投放令牌

　b. 根据预设的匹配规则先对报文进行分类，不符合匹配规则的报文不需要经过令牌桶的处理，直接发送；

　c. 符合匹配规则的报文，则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去，同时令牌桶中的令牌 量按报文的长度做相应的减少；

　d. 当令牌桶中的令牌不足时，报文将不能被发送，只有等到桶中生成了新的令牌，报文才可以发送。这就可以限制报文的流量只能是小于等于令牌生成的速度，达到限制流量的目的。

注意：当令牌不足时，这里报文：

   1、可以被丢弃

   2、可以排放在队列中以便当令牌桶中累积了足够多的令牌时再传输

   3、可以继续发送，但需要做特殊标记，网络过载的时候将这些特殊标记的包丢弃

 伪代码：

public class TokenBucketDemo {
    public long timeStamp = getNowTime();
    public int capacity; // 桶的容量
    public int rate; // 令牌放入速度
    public int tokens; // 当前令牌数量
    public boolean grant() {
        long now = getNowTime();
        // 先添加令牌
        //min(桶的容量，当前令牌 + 上次请求获取令牌时间到当前时间内生成的令牌)
        tokens = min(capacity, tokens + (now - timeStamp) * rate);
        timeStamp = now;
        if (tokens < 1) {
            // 若不到1个令牌,则拒绝
            return false;
        }
        else {
            // 还有令牌，领取令牌
            tokens -= 1;
            return true;
        }
    }
}

令牌桶算法临界问题思考：

       场景：在0:59秒的时候有100个请求过来，此时令牌桶有100个token，瞬间通过。1:00的时候又有100个请求，但令牌放入令牌桶是有一定的速率的，假设rate<100,不可能100个请求都通过。避免了计数器算法瞬间请求过大，压垮系统。

令牌桶和漏桶对比：

1. 令牌桶是按照固定速率往桶中添加令牌，请求是否被处理需要看桶中令牌是否足够，当令牌数减为零时则拒绝新的请求；
2. 漏桶则是按照常量固定速率流出请求，流入请求速率任意，当流入的请求数累积到漏桶容量时，则新流入的请求被拒绝；
3. 令牌桶限制的是平均流入速率（允许突发请求，只要有令牌就可以处理，支持一次拿3个令牌，4个令牌），并允许一定程度突发流量；
4. 漏桶限制的是常量流出速率（即流出速率是一个固定常量值，比如都是1的速率流出，而不能一次是1，下次又是2），从而平滑突发流入速率；
5. 令牌桶允许一定程度的突发，而漏桶主要目的是平滑流入速率；

两个算法实现可以一样，但是方向是相反的，对于相同的参数得到的限流效果是一样的

2 最快速度求两个数组之交集算法与hash

一个题目

      该题目来自58同城的二面，用最快速度求两个数组之交集算法。

比如A={6，2，4，1},B={2，9，4，3}，那么A&B={2，4}。

       算法一：在大多数情况，也就是一般的情况下，大家都能想出最暴力的解法，通常也就是采用遍历或者枚举的办法来解决问题。

      该题需要找出两个数组的交集，最简单的一个办法就是用A数组里面的所有数去匹配B数组里面的数。假设两个数组的大小都是n，那么这种遍历的时间复杂度为O(n^2)。这个也是最复杂的情况了。

       算法二：通常下，除了用暴力枚举的问题，还有另外一种外万金油的解法----预处理。其实思想和C语言中的预处理一样，对数据记性归一化处理。说白了，在这里就是对数组排序。我们知道数组排序的算法时间复杂度最低是O(nlogn)，可以看到数量级已经低于算法一的时间复杂度。

       那么在排好序好，怎么得到数组的交集呢？

       假设我们已经有了两个排好序的数组：

       A={1，2，4，6}

       B={2，3，4，9}

      那么我们只要分别对A和B设置两个指针i,j（或者直接说是下标），进行循环，伪代码如下：

int count()
{
total=i=j=0;
while(i<n && j<n)
{
if(a[i]<b[j]) i++;
else if(a[i]>b[j])j++
else
    total++;
}
    return total;
}

时间复杂度为O(n)

综合排序的时间复杂度则整体复杂度为：O(nlogn)

      算法三：如果只是会了上面两种，还只能说是计算机的菜鸟，而且一般面试或者笔试题也不会这么简单。那么比O(nlogn)时间复杂度更低的是多少呢？一般就是O(n)。我们可以思考一下计数排序的算法。也就是把两个数组A和B都遍历到一个新的数组里，然后在统计重复的数字即可，这个时间复杂度就是O(n)。当然，计数排序是有条件的，也就是要求数组内数字的范围是已知并且不是很大。

      算法四：上面的算法实现简单，也很容易达到题目的要求，但是还是有一些瑕疵，也就是非完美方案，同样根据算法三我们可以想出用哈希函数或者哈希表来解决问题。也就是将数组A哈希到哈希表中，然后继续将数组B哈希到哈希表中，如果发生哈希碰撞则统计加1，最后可以得出数组的交集。时间复杂度也就是哈希所有元素的复杂度O(n)。

那么什么是哈希呢？

         Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

       HASH主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值.也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系。例如字符串hello的哈希算法

char* value = "hello"; int key = (((((((27* (int)'h'+27)* (int)'e') + 27) 　* (int)'l') + 27) * (int)'l' +27) * 27 ) + (int)'o' ; 。

数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：

 

      HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解，一个线性的数组怎么实现按键值对来存取数据呢？这里HashMap有做一些处理。

    1.首先HashMap里面实现一个静态内部类Entry 其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基 础就是一个线性数组,这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。

     2.既然是线性数组，为什么能随机存取？这里HashMap用了一个小算法，大致是这样实现：

 

1.	存储时:  
2.	  
3.	int hash = key.hashCode();--> 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值  
4.	  
5.	int index = hash % Entry[].length;  
6.	  
7.	Entry[index] = value;  
8.	  
9.	取值时:  
10.	  
11.	int hash = key.hashCode();  
12.	  
13.	int index = hash % Entry[].length;  
14.	  
15.	return Entry[index]  

       到这里我们轻松的理解了HashMap通过键值对实现存取的基本原理

 3.疑问：如果两个key通过hash % Entry[].length得到的index相同，会不会有覆盖的危险？

      这里HashMap里面用到链式数据结构的一个概念.上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。打个比方, 第一个键值对A进来,通过计算其key的hash得到的index=0，记做:Entry[0] = A.一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。

      到这里为止，HashMap的大致实现，我们应该已经清楚了。

      当然HashMap里面也包含一些优化方面的实现，这里也啰嗦一下。

      比如：Entry[]的长度一定后，随着map里面数据的越来越长，这样同一个index的链就会很长，会不会影响性能？

      HashMap里面设置一个因素（也称为因子），随着map的size越来越大，Entry[]会以一定的规则加长长度。

解决hash冲突的办法

      1）开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）

      2）再哈希法

      3）链地址法

      4）建立一 公共溢出区

java 中hashmap的解决办法就是采用的链地址法。

3 用Java实现最快速度的数组交集

      算法一、暴力破解法，遍历两个数组，比较值。借用第三个数组来装载相同的值。时间复杂度为O(n).

public static int[] intersect(int[] arr1,int[] arr2){
    int N=0;
    if(arr1.length>arr2.length){
        N=arr2.length;
    }else{
        N=arr1.length;
    }
    int[] n=new int[N];
    int k=0;
    for(int i=0;i<arr1.length;i++){
        for(int j=0;j<arr2.length;j++){
            if(arr1[i]==arr2[j]){
                n[k++]=arr1[i];
            }
        }
    }
    n= Arrays.copyOf(n,k);
    return n;
}

4 判断两个链表是否相交

JAVA堆和栈比较

两个链表，判断是否相交，找出相交的第一个点？

    首先应该清楚两个单链表相交要么都是无环链表，要么都是有环链表，不存在一个有环链表和一个无环链表相交，因为两个链表一旦相交则后续的链表都应该是相同的

（1）将其中任意一个链表的环打破，即让尾结点指向null（记下保存原本应当指向的位置），然后判断第二个链表是否含有环，若第二个链表无环则相交，否则不相交

（2）利用判断单链表是否有环的方法，对链表使用两个快慢指针进行判断是否有环，两个指针的碰撞点即在环上，那么判断链表二的环上是否包含该碰撞点就可以判断两个链表是否相交了

1、两个无环链表相交

    如果两个单链表有共同的节点，那么从第一个节点开始，后面的节点都会重叠，直至链表结束，因为两个链表中有一个共同节点，则从这个节点里的指针域指向下一个节点的地址就相同，所以相交以后的节点就会相同，直至链表结束，总的模型就像一个“Y”

解法：

（1）暴力解法

    从头开始遍历一个链表，遍历第一个链表中的每个节点时，同时从头到尾遍历第二个链表，看是否有相同的节点，第一次找到相同的节点即第一个交点；若遍历结束未找到相同的节点，即不存在交点，时间复杂度为O(n^2)

（2）使用栈

    我们可以从头遍历两个链表。创建两个栈，第一个栈存储第一个链表的节点，第二个栈存储第二个链表的节点，直至链表的所有节点入栈，通过取两个栈的栈顶元素节点判断是否相等即可判断两个链表是否相交。从第一个相交节点之后，后续节点均相交直至链表结束。出栈直至两个节点不相同时，则这个节点的后一个节点是第一个相交节点

（3）遍历链表记录长度

    同时遍历两个链表到尾部，同时记录两个链表的长度。若两个链表最后的一个节点相同，则两个链表相交。有两个链表的长度后，我们就可以知道哪个链表长，设较长的链表长度为len1,短的链表长度为len2。

    则先让较长的链表向后移动(len1-len2)个长度。然后开始从当前位置同时遍历两个链表，当遍历到的链表的节点相同时，则这个节点就是第一个相交的节点。（第三种方法其实是缩短了链表比较的长度）时间复杂度为O(len1+len2)

（4）哈希表法

    既然连个链表一旦相交，相交节点一定有相同的内存地址，而不同的节点内存地址一定是不同的，那么不妨利用内存地址建立哈希表，如此通过判断两个链表中是否存在内存地址相同的节点判断两个链表是否相交。具体做法是：遍历第一个链表，并利用地址建立哈希表，遍历第二个链表，看看地址哈希值是否和第一个表中的节点地址值有相同即可判断两个链表是否相交。时间复杂度O(length1 + length2)

2、两个链表都为有环情况

（1）第一个交点在环开始之前

（2）第一个交点在环入口处

 （3）第一个交点在环内

判断相交方法：

       针对（1）和（2）两种情况我们可以采用和上述无环链表的判断方法一样，针对第三种有环链表，我们可以分别找到链表一和链表二的环入口节点，各自的环入口节点即为各自第一次相交的节点

5 java计算字符串中出现次数最多的字符

      昨天在做作业的时候发现了一个有趣的题目，也就是标题这个题目，然后就自己捣鼓了一个算法，就是为了计算字符串中出现次数最多的字符。这个算法有一个值得注意的点就是如果同种字符出现次数相同，那就取最早出现的那种

public class MostStrings {

    public static Object[] paixu(String arr) {

        /*
         * 思路就是：相同的字母放在一排，然后在排另一种字母的时候就在上一种字母下标的下一位开始作比较。
         * 设计原因：避免不必要的重复比较
         */
        char list[] = arr.toCharArray();// 把字符串转换成字符数组
        int index = 0;// 记录每一种字母最后一个索引
        int maxIndex = 0;// 记录字母出现的个数
        int max = 0;// 中间级
        char maxValue = ' ';// 出现次数最多的值
        for (int i = 0; i < list.length - 1; i++) {
            if (i <= index) {// 这个判断是很重要的，为了保持i和index在比较完一种字符之后还能保持相同，保证算法的正确性
                i = index;
            } else {
                index = i;
            }
            for (int j = i + 1; j < list.length; j++) {
                if (list[i] == list[j]) {
                    index++;
                    maxIndex++;
                    char record = list[index];// 记录该位置的值
                    list[index] = list[j];// 交换位置
                    list[j] = record;// 交换位置
                }
            }
            if (maxIndex > max) {// 记录出现次数最多的值和出现的次数
                maxValue = list[i];
                max = maxIndex;
            }
            maxIndex = 0;// 初始化出现次数
        }
        for (int i = 0; i < list.length; i++) {// 打印最后结果
            System.out.print(list[i]);
        }
        System.out.println();
        Object obj[] = { maxValue, max + 1 };
        return obj;
    }

    // 测试代码
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        System.out.println("输入全字母的字符串：");
        String arr = sc.next();
        System.out.println("当前的字符串是：" + arr + " 长度是：" + arr.length());
        Object obj[] = paixu(arr);
        System.out.println("最早出现次数最多的字母：" + obj[0]);
        System.out.println("出现的次数：" + obj[1]);

    }

}

 效果

输入全字母的字符串：
adarwrwetetsdSS$35347437231251
当前的字符串是：adarwrwetetsdSS$35347437231251 长度是：30
aaddwwrrtteesSS$33337755221144
最早出现次数最多的字母：3
出现的次数：4
当然也可以是其他字符串。

 当然也可以是其他字符串。

 

背景

每一个对外提供的API接口都是需要做流量控制的，不然会导致系统直接崩溃。很简单的例子，和保险丝的原理一样，如果用电符合超载就会烧断保险丝断掉电源以达到保护的作用。API限流的意义也是如此，如果API上的流量请求超过核定的数值我们就得对请求进行引流或者直接拒绝等操作。

限流算法

既然要限流，就得提到限流算法了，一般有漏桶算法和令牌桶算法两种限流算法。

漏桶算法

漏桶算法(Leaky Bucket)是网络世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）时经常使用的一种算法，它的主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。漏桶算法提供了一种机制，通过它，突发流量可以被整形以便为网络提供一个稳定的流量。

漏桶可以看作是一个带有常量服务时间的单服务器队列，如果漏桶（包缓存）溢出，那么数据包会被丢弃。 在网络中，漏桶算法可以控制端口的流量输出速率，平滑网络上的突发流量，实现流量整形，从而为网络提供一个稳定的流量。

如图所示，把请求比作是水，水来了都先放进桶里，并以限定的速度出水，当水来得过猛而出水不够快时就会导致水直接溢出，即拒绝服务。

可以看出，漏桶算法可以很好的控制流量的访问速度，一旦超过该速度就拒绝服务。

令牌桶算法

令牌桶算法是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。从原理上看，令牌桶算法和漏桶算法是相反的，一个“进水”，一个是“漏水”。

 

算法描述：

•  假如用户配置的平均发送速率为r，则每隔1/r秒一个令牌被加入到桶中（每秒会有r个令牌放入桶中）；
• 假设桶中最多可以存放b个令牌。如果令牌到达时令牌桶已经满了，那么这个令牌会被丢弃；
• 当一个n个字节的数据包到达时，就从令牌桶中删除n个令牌（不同大小的数据包，消耗的令牌数量不一样），并且数据包被发送到网络；
• 如果令牌桶中少于n个令牌，那么不会删除令牌，并且认为这个数据包在流量限制之外（n个字节，需要n个令牌。该数据包将被缓存或丢弃）；
• 算法允许最长b个字节的突发，但从长期运行结果看，数据包的速率被限制成常量r。对于在流量限制外的数据包可以以不同的方式处理：（1）它们可以被丢弃；（2）它们可以排放在队列中以便当令牌桶中累积了足够多的令牌时再传输；（3）它们可以继续发送，但需要做特殊标记，网络过载的时候将这些特殊标记的包丢弃。
   

Google的Guava包中的RateLimiter类就是令牌桶算法的解决方案。

漏桶算法和令牌桶算法的选择

漏桶算法与令牌桶算法在表面看起来类似，很容易将两者混淆。但事实上，这两者具有截然不同的特性，且为不同的目的而使用。

漏桶算法与令牌桶算法的区别在于，漏桶算法能够强行限制数据的传输速率，令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。

需要注意的是，在某些情况下，漏桶算法不能够有效地使用网络资源，因为漏桶的漏出速率是固定的，所以即使网络中没有发生拥塞，漏桶算法也不能使某一个单独的数据流达到端口速率。因此，漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常，漏桶算法与令牌桶算法结合起来为网络流量提供更高效的控制。

参考资料：https://blog.csdn.net/SunnyYoona/article/details/51228456