空间换算：
无标题.png
1 Byte = 8 Bits
1 KB = 1024 Bytes
1 MB = 1024 KB
1 GB = 1024 MB
2^2 = 4;
2^4 = 16;
2^8 = 256;
2^10 = 1024;
2^16 = 65 536
2^20 = 1 048 576
2^32 = 4 294 967 296
基本方法
1. hash法
Hash一般被称为散列，它是以一种映射关系，即给定一个数据元素，其关键字为key，按一个确定的散列函数计算出hash(key)，把hash(key)作为关键字key对应元素的存储地址（或称散列地址），再进行数据元素的插入和检索操作。简而言之，散列函数就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
散列表是具有固定大小的数组，其中，表长应该为质数。散列函数是用于关键字与存储地址之间的一种映射关系，但是，不能保证每个元素的关键字与函数值是一一对应的，因为极有可能出现对应于不同的元素，却计算出相同的函数值，这就是哈希冲突。
1.1 常用散列函数的构建方法：
1.1.1 直接寻址法
h(key) = key 或者 h(key) = a * key + b;
1.1.2 取模法
h(key) = key mod p;
1.1.3 数字分析法
1.1.4 折叠法
1.1.5 平方取中法
1.1.6 保留余数法
h(key) = key % p;
1.1.7 随机数法
h(key) = random(key);
1.2 常用的解决冲突办法
1.2.1 开放地址法
当发生地址冲突时，在散列表中再按照某种方法继续探测其他的存储地址，知道找到空闲的地址为止。
1.2.2 链地址法
1.2.3 再散列法
当发生冲突时，使用第二个、第三个...散列函数计算地址，直到无冲突为止。时间消耗会增加。
1.2.4 建立一个公共溢出区
优缺点：
Hash主要是用来进行“快速存取”，在O(1)时间复杂度里就可以查找到目标元素，或者判断其是否存在。Hash数据结构里的数据对外是杂乱无序的，因此其具体存储位置及各个存储元素位置之间的相互关系是无法得知的，但是却可以在常数时间里判断元素位置及存在与否。在处理海量数据的过程中，使用Hash方法一般可以快速存取、统计某些数据，将大量数据进行分类，例如提取某日访问网站次数最多的IP地址等。
2. Bit-map法
bit-map(位图)法的基本原理是使用位数组来表示某些元素是否存在。
bit-map法的结果是生成一个N位长的串，每位上以“1”或“0”表示需要的集合中的数。
image.png
例：对10亿个IPV4的IP地址进行排序，每个IP只会出现一次。
思路：可以通过简单的规则将10亿IP地址全部转换成32位的无符号整数，将这10亿整数排序后，然后再转回IP地址即可；更优的思路是申请长度为32位的bit类型的数组，然后将其对应到相应的位上，相比前一种方法，这个方法更节省空间。
m7.png
4Byte * 10亿 = 40 0000 0000Byte = 40 0000 0000 / 1024 /1024 /1024 GB = 3.725G
m8.png
上图计算得到的大小跟我算的不太一样？
2^32 bit = 4 294 967 296bit = 4 294 967 296bit / 8 /1024/1024 M = 512M
3. Bloom Filter法
以一个例子来说Bloom Filter（布隆过滤器）；
位运算1.png
最差情况下使用hash表或者数据表存储，空间要求高：
位运算2.png
64Byte*100亿 = 6400 0000 0000 /1024/1024/1024G = 596.046G
当遇到下面这几种情况，可以使用布隆过滤器：
位运算3.png
布隆过滤器的特定：
位运算4.png
对于上面题目的解决方案：
建立一个bitarray数组，长度为m；
有k个hash函数，输出域>=m，每个hash函数是优秀的且相互独立；
对每个URL通过k个hash函数，计算求得k个hash值，对每个hash值对应到bitarray上，进行涂黑，如果已经是黑色，则保持不变；0daybank
文章评论