杂:位图与布隆过滤器
我们经常有这样的需求:判断一个订单是否存在,判断一个URL路径是否访问过。常规情况下我们可以将存在的订单ID或者已经访问过的URL做成集合,然后通过判断是否在集合中来确认是否存在或者是否访问过。那么我们也同样的可以想到通过hash算法将已存在的订单ID或者已经访问过的URL做映射到一个array的index上,通过检查对于index的值是否为true来判断是否存在。
我们经常有这样的需求:判断一个订单是否存在,判断一个URL路径是否访问过。常规情况下我们可以将存在的订单ID或者已经访问过的URL做成集合,然后通过判断是否在集合中来确认是否存在或者是否访问过。那么我们也同样的可以想到通过hash算法将已存在的订单ID或者已经访问过的URL做映射到一个array的index上,通过检查对于index的值是否为true来判断是否存在。
索引是用来加速查找的数据结构。不同的需求会使用不同的数据结构来构建索引。比如HashMap、Btree、SkipList都是经典的索引数据结构。
递归的思想是将大问题分解成小问题处理,大问题的处理逻辑与小问题的处理逻辑一致。其分解过程可以被表示成一棵树结构,这棵树被称为递归树。
我们在算法设计之初通常只会考虑单线程执行的情况。在实际生产中却有很多情况下可以做并行化优化。
递归是一极其常用的技巧。在我们的实际生产中也会经常用到,比如树遍历(地址,类目之类的)。