数据结构

哈希表

也称为散列表，用于实现键值对的存储和查找。hash值的计算通常通过与运算hash&(m-1)方式实现，其桶的数量必须为2的次幂数（也可以通过取模hash%m计算hash值）。哈希函数将键映射到索引的位置，时间复杂度为O(1)（最坏O(n)），常见的有开放地址法和链表法两种：

• 开放地址法：当发生哈希冲突时，尝试在哈希表中寻找下一个可用的位置，直到找到一个空闲的位置为止。常见的探测方法包括线性探测、二次探测和双重哈希等。
• 链表法：使用链表来存储哈希冲突的键值对，将冲突的键值对插入到链表的末尾。

树

B+树

多路平衡查找树，具有以下特点：

• 每个节点有多个子节点以控制树高
• 非叶子节点只存储键值信息，数据都存在叶子节点中
• 所有叶子节点之间都有链指针

红黑树

自平衡二叉树，通过插入/删除时旋转保证树节点的平衡。查找时间复杂度为O(log n)

lsm-tree

日志结构合并树，适用于写多读少问题。

跳跃表

基于多指针有序链表实现，查找时，从上层指针开始查找，找到对应的区间之后再到下一层去查找。

与红黑树等平衡树相比，跳跃表不需要进行旋转等操作来维护平衡性，插入速度非常快速； 更容易实现； 支持无锁操作。

布隆过滤器

通过一系列hash运算与二进制数组比对判断元素是否可能存在（不能判断元素一定存在），具有空间效率高、时间效率高的特点。