suke 置顶2019-02-01老师能对限流相关的算法和数据结构多讲一讲么作者回复: 这是我之前开源的限流框架，你可以看看，比较详细了。而且里面还有一篇我发到infoq上的文章，讲设计思路。
https://github.com/wangzheng0822/ratelimiter4j 1 20
2019-02-01春节还想着加福利，这是一种什么精神。 1 25
2019-02-19感觉限流的思想中可以参考一下tcp的拥塞控制算法 12
2019-04-111. 还可以采用双向链表，每次请求往链表尾插入一个时间，插入之前先从链表头删除一秒之前的节点，之后看下链表的size是否大于等于N，大于等于N则拒绝本次访问，否则允许本次访问并插入链表尾；占用的空间比循环链表要大
2. 假设有n个规则，每个规则的单词个数平均为m，则时间复杂度为O(m*logn), 空间复杂度O(n*m)
时间复杂度分析下：平均搜索m层，每一层最多有n个单词，由于是采用有序数组存储，查找时间复杂度为O(logn),所以总的时间复杂度为O(m*logn) 11
2019-04-01思考题1：可以用优先级队列（根据请求时间构建小顶堆），最早的请求时间的放在堆顶。然后每次进来一个请求，就判断这个时间跟堆顶的时间差是否小于1S，并且堆的大小小于请求限制的次数，如果是就插入队列，如果不是，就限制。 8
2019-03-16思考题1
还可以使用一个固定大小的小顶堆，以时间戳作为排序依据。
每次有请求时相当于要在小顶堆内插入数据，如果堆顶数据的时间跟本次时间差距小于1s，且堆已满的情况下，不允许继续插入。每次插入数据的时候，删除1s外的数据，重新排序，确定新的堆顶。
不过感觉跟循环队列比，都是劣势；插入数据，删除数据，时间复杂度都要更高。而且每次删除数据后还要重新排序一遍确定新的堆顶。 6
2019-02-15鉴权的精确匹配用散列表的时间复杂度是O(1)，比顺序匹配O(n)和二分查找的效率都高啊。为什么不选用呢？作者回复: 小数据量的情况下，散列表在存储和匹配上并不一定比二分查找高呢
3
2019-02-01给老师点个赞，敬业精神值得学习，春节期间也是给自己充电的好时期，加油。 3
2019-02-01读您的文章就是一种享受!!! 3
2019-02-07请教老师一个问题哈，为啥鉴权算法里，每个应用的规则要放到有序数组呢，放hash set会更好吧?
比如一个应用有两个规则:/user/a和/user/b，把这俩规则放hash set岂不是时间复杂度更低、更好呢作者回复: hash set对于小数据量也不一定比有序数组效率高呢。毕竟hash set还要计算哈希值、处理冲突等。
2
2019-02-01老师用心了 2
2019-02-01太棒了，给老师点赞👍 2
2019-02-01给老师点赞 2- 2019-02-01哇，老师优秀又热心(✪▽✪)，期待老师的题目(๑˙ー˙๑) 2
2020-01-09重新来留个言，循环队列也可以用跳表或者红黑树来实现，跳表有前后指针，以long类型的时间作为索引，找到比当前k少一秒的元素（索引查找或者直接便利都可以），然后之前的元素也能删掉了。是否加入跳表就看size是否达到了k，有就加入，没有就拒绝。
红黑树同样以long类型的时间作为索引key，找到比新元素少一秒的key，红黑树天生就有一个可以找到floorkey(也就是小于等于查找元素的key)，然后依次找到其前驱节点，依次删除。查找前驱节点会比跳表的直接遍历要慢一点。
不过红黑树和跳表天生的有序性，也是实现这样一个限流容器的思路。展开 1
2019-06-11“不同的应用对应不同的规则集合。我们可以采用散列表来存储这种对。。。”，这里如果匹配规则很多的话，不会发生很多的冲突的吗？作者回复: 散列表本身就有解决冲突的机制的
1
2019-04-04想问下如何对接口做数据域权限检验。比如调用方有权限调用查询项目接口，但是对于请求参数，如项目ID，鉴权系统能够判断调用者是否有权限访问这个项目。作者回复: 可以把参数拼到url中 或者重新设计鉴权规则
1
2019-02-02期待老师的题目，最近也在刷LeetCode，结合的效果肯定好！！！编辑回复: 哈哈 看来会给你惊喜了
1
2019-02-02一直跟着走，回头再看几遍，真心赞 1
2019-02-01立个flag，正月初一到正月初七每天都做老师的题…… 1