跳跃表(skiplist)简介 跳跃表(skiplist)是一种随机化的数据结构，其实就是给顺序单链表加了多个多层索引，高层次的索引跳跃节点大于底层的，增加是以随机化的方式进行的，在列表中查找的可以快速的跳过部分列表，提高查询效率。 跳跃表以有序的方式在层次化的链表中保存元素， 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成， 并且比起平衡树来说， 跳跃表的实现要简...

红黑树简介 红黑树一种自平衡的二叉树，先了解一下什么是二叉树把。 二叉树的性质 在二叉树的第I层上最多有2i-1(i>=1) 二叉树中如果深度为K，那么该二叉树最多有2k-1个节点（k>=1） n0 = n1+1 其中n0表示度数为0的节点数，n1表示度数为2的节点数 在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整 ...

布隆过滤器简介 布隆过滤器是一个位数组和哈希函数实现的一种数据结构，它相对于其他我们平常用的List，Set等更节省内存空间，不过它存在误判概率。理论情况下添加到集合中的元素越多，误报的可能性就越大。并且，存放在布隆过滤器的数据不容易删除。 例如申请100万个元素位数组只用10^6/8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空间，特别节省空间。...

堆的定义 堆在逻辑上是一种完全二叉树，物理结构上是一维数组，按照根节点大小分为最大堆和最小堆，如下图。最小堆：所有节点的左右孩子节点都大于或者等于父节点最大堆：所有节点的左右孩子节点都小于或者等于父节点 补充：完全二叉树的性质如果有一颗有n个节点的完全二叉树的节点按层次序编号，对任一层的节点i（0<=i<=n）有（注意i的取值）1.如果i=0，则节点是二叉树的根，无双亲，如果...