学习笔记

位运算

主要用途

• 判断奇数还是偶数

判断最后一位是1还是0

• 乘以2

左移一位

• 除以2

右移一位

• 将最后一个1变为0

x & (x-1)

• 判断是否是2的整数次幂

x & (x-1) 是否为0

布隆过滤器

特点： 查询高效O(1)、占用空间少、某个值一定不存在或者可能存在

LRU算法

最近最少使用（被淘汰）算法，依赖局部性原理，即数据最近被访问过，那么将来被访问的概率会很大 使用hash和双向链表实现

• 新的元素插入到链表最前
• 命中缓存的元素移动到链表最前
• 链表满时，依次从最后移除元素

排序

不同排序算法的时空复杂度(来源：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html)