网站建设工作量评估,wordpress的官网,房山网站建设,免费个人简历模板电子版可填写本章节是哈希的延申 可碧教你C——哈希http://t.csdnimg.cn/3R8TU 一文详解C——哈希 位图 位图是基于哈希表的原理产生的一种新的container——bitset
基于哈希映射的原理#xff0c;我们在查找的时候#xff0c;可以直接去定址到元素的具体位置#xff0c;然后直接访问该… 本章节是哈希的延申 可碧教你C——哈希http://t.csdnimg.cn/3R8TU 一文详解C——哈希 位图 位图是基于哈希表的原理产生的一种新的container——bitset
基于哈希映射的原理我们在查找的时候可以直接去定址到元素的具体位置然后直接访问该元素。但是如果没有哈希冲突我们甚至完全不需要检查哈希映射对应的元素是否为我们需要查找的元素直接判断这个位置有没有元素便可以知道该元素在不在哈希表里。
而判断某一个位置有没有元素只需要0和1便可以完成也就是无论被存储数据的大小每个数据只需要1个比特位的存储空间这无疑极大压缩了内存空间。而通过这种方式实现的数据结构便被称为——位图。
位图的结构
一般来说我们只有在内存空间不足以解决既有的问题下才会去考虑缩小数据空间的问题。同样内存的使用场景一般是在有着海量数据下我们要对某个数据进行查重才会使用位图。位图的原理是哈希表其构成当然离不开数组实际上位图和普通的哈希表构成几乎相同 只不过将数组的单元格变成了一个个的比特位。
但是C中并无法将单个比特位作为单元格我们只能通过某种方法间接去访问比特位
例如我们将每个单元格设为整型int然后每个整型int具有4字节32个比特位我们便可以通过相除的方式寻找具体的单元格再用除余的方式寻找比特位 这便是位图的最基本的结构:
class bitset
{private:vectorint _table;//可以是任何模板参数只需要该参数所占有的比特位//但是最好不要用指针因为在不同位的电脑上指针的比特位不同
}
位图的访问
位图的访问实际上是对比特位的访问。但是我们很难专门去访问某一个比特位我们只能采取异或的方法将其他位全置为0从而间接访问具体的一位的值。 通过以上两个式子我们很快就能找到解决方案
只要构建出一个辅助量其他位都为0只有被查找的那一位为1然后取最终得到的结果便只与需要查找的值有关了。如果该值为1则整个值非0返回true如果该值为0则整个值为0返回false。
下一个问题便是如何构建这一个辅助量这便需要用到移位运算符。 也就是说我们想访问哪一位就只需要移位多少位便可以达成条件。
//查找元素约等于find
bool test(int key)
{size_t plane key / 32;//第几辆飞机size_t seat key % 32;//第几个座位return _table[plane] (1 seat);//构建辅助量并
}
位图的插入和删除
位图的插入和删除实际上也是考虑如何在不影响其他比特位的情况下对某一具体比特位的操作。
插入就是将该位便为1删除就是将该位便为0这里又需要我们使用异或的性质 于是很容易想到
插入的时候我们使用|辅助量为其他位全为0修改位为1删除的时候我们使用辅助量其他位全为1修改位为0
位图的实现
位图不支持扩容。我们在使用位图的时候就必须传入位图需要的空间大小 class bitset
{
public:bitset(int n){_table.resize(n);}//将元素设为1约等于insertvoid set(int key){size_t plane key / 32;size_t seat key % 32;_table[plane] | (1 seat);}//将元素设为0约等于erasevoid reset(int key){size_t plane key / 32;size_t seat key % 32;_table[plane] ~(1 seat);}//查找元素约等于findbool test(int key){size_t plane key / 32;size_t seat key % 32;return _table[plane] (1 seat);}
private:vectorint _table;
}; 布隆过滤器
上面所述的位图都是在不考虑哈希冲突的情况下所实现但是实际上哈希冲突是不可能被避免的。 难道必须要在规定没有哈希冲突的情况下位图才有意义吗当然不是。我们不妨直面哈希冲突看看在有哈希冲突的情况下位图会产生什么影响。 哈希冲突会导致其他与其具有相同哈希映射值的元素也被视作为存在于哈希表中。 如果数据存在无论该位是否存在冲突则该位一定为1如果数据不存在则该为可能为0也可能会因其他数据的冲突导致该位为1
而反过来通过表中的状态判断数据是否存在于表中
如果表中存在无法判断该数据是否存在因为可能是其他的值产生的1如果表中不存在则该哈希映射值对应的所有元素一定都不存在
是不是就像大家平时上课签到一样 也就是说我们可以采用他的准确性——判断数据是否不在表中
最常见的应用场景便是取名查重。我们可以接受一个未被取的名字被视为已经占用但是不能接收重名此时采用这种过滤方式可以在满足条件的情况下尽可能节省空间。 多重过滤
尽管我们可以接受误判但是我们还是不想有太多类似于科比布莱恩特24这样因误判而导致可取名变少带来的产物那还有没有其他办法去尽量避免呢
既然一重过滤会导致误判那多重过滤是不是误判就减少了 只有三个毕业证都存在才表示学历是真真正正存在的。 而如果其中任何一个毕业证不存在则表示其学历是伪造的。
我们创建三个位图每个位图使用不同的哈希映射当一个数据插入到布隆过滤器时会映射到三个不同的位置上每个位图都会产生相应的插入结果。也就是说只有当三个位图都存在该数据才表示布隆过滤器存在该数据。 相应的如果任何一个位图中不存在某个数据则表示其他位图中该数据的存在时哈希冲突产生的。而因为采用了多种哈希映射三个位图的哈希冲突完全相同的可能性几乎为0也就避免了哈希冲突的存在。
class bloom_filter
{private:bitset _hash1;bitset _hash2;bitset _hash3;
}
布隆过滤器的问题
虽然布隆过滤器可以避免插入的哈希冲突但是还是有这样一个巨大的问题——删除。
我们想删除一个数据当然是将三个位图中所有对应的数据都删除。但是删除以后哈希冲突导致的其他数据也被删除了。这种改变是不可逆的因为我们并不知道到底有多少数据在该位上哈希冲突了。等到判断的时候因为该数据在某一个表中被误删导致就算该数据在其他两个表中仍存在也会被误判为不存在。
所以布隆过滤器一般是不允许删除的当然也有解决方法便是在每个位置上进行引用计数但是这便舍弃了布隆过滤器节省空间的初衷和优点。 哈希切割
哈希切割不是一个具体的container。哈希切割是利用哈希的思想对某些问题处理的方法。
假如某个数据库存有海量的数据一个服务器并没有办法很好处理这些数据要将这些数据分开到几个不同的服务器进行处理往往会面临几个需求
相同或类似的数据放在同一个服务器中每一个服务器的数据量尽量平均尽量不要浪费空间以减少服务器的数量 此时红黑树等容器便没有办法满足了。尽管一些有序容器可以处理数据的特征但是因为服务器的分离红黑树很难去跨设备访问其他数据所以这里大部分container都会罢工。
在这里我们就必须采取哈希的思想通过数据的除余将除余相同的数据放在同一个服务器中。这样重复的数据自然因除余相同被归类到了一个服务器里而类似的数据同样可以通过一些算法分割到相同的服务器中。
