文章目录1. 写在前面
2. 数组存储我们当然可以使用有序数组,二叉搜索树,哈希表等等来存储所有的用户id。但是无论是有序数组还是二叉搜索树,这两种数据结构都是基于二分查找的思想从中间元素开始查起的。所以在查询用户id是否存在时,这两种数据结构的检索时间都是 O(logn)。
那应该怎么做呢? 我们可以直接使用一个足够大的数组来存储用户id,如果该用户存在,就在该用户id的位置标识为 1 ,否则就是默认的 0 也就是不存在。但是这个也会有问题,如果我们的用户id范围很广, 那么我们怎么优化存储空间呢?接下来就介绍一下位图了。 3. 位图存储3.1 位图简介首先我们需要优化存储的数据结构,不是int, 如果我们使用bit类型来存储,就是原来的32倍了,非常亏贼!而这种以bit为单位构建数组的方案就叫做bitmap,也就是位图。 如果你在好奇这个32是怎么算的?我们原来是用一个int类型取表示是否存在这个值,我们假设是在32位的机子上,这个int类型就是4个byte。而我们现在用的是bit来作为存储运算,1 byte = 8 bit,所以就是原来的 1/4*8 ,就是1/32倍。
其实有一个点很好想到,我们都知道一个数组的空间其实就是 当然如果我们数组压缩到很小的时候,就容易发生哈希冲突,如果两个元素,A和B都映射到同一个地方了,那么就无法判断是A存在,还是B存在了,那应该如何解决哈希冲突呢?一般会有两种方法,开放寻址法,链表法 3.2 链表法数组的每个成员是一个链表。该数据结构所容纳的所有元素均包含一个指针,用于元素间的链接。我们根据元素的自身特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。 先调用这个元素的 hash 方法,然后根据所得到的值计算出元素应该在数组的位置。如果这个位置上没有元素,那么直接将它存储在这个位置上;如果这个位置上已经有元素了,那么与新元素进行比较:相同的话就不存了,否则,将其存在这个位置对应的链表中。 3.3 开放寻址法当发生哈希冲突时,重新找到空闲的位置,然后插入元素。寻址方式有多种,常用的有线性寻址、二次方寻址、双重哈希寻址等等 线性寻址就是如果冲突了,就从冲突位置线性顺序向下继续寻找空位置。 二次寻址就是每次向上找两格,冲突就向下找两格,再冲突就是向上找四个,-2,+2,-4,+4这样的上下的找,直到找到不冲突为止。 双重哈希寻址就是使用多个hash函数获取多个哈希值。 而这种方法也称为双散列。可以使用两个哈希寻址,也可以使用多个哈希来寻址,那这是不是就有点像
这个X,Y,Z其实就是我们的网址。这样我们就可以快速判断网页是否已经被爬取了。 还有一种位图的优化:Roaring Bitmap 后续在合并多个postingsList会有作用。 |
|