深入拆解：Hash函数、Bitmap位图、BloomFilter布隆过滤器

Hash函数

byte[] hash(String inData)

hash函数的特点：

（1）输入域可以是无穷大的。

（2）输出域是有限的，比如输出长度固定为64bit、128bit、256bit、512bit等等，以达到压缩数据、提取指纹的目的。

（3）没有任何随机机制，相同的输入得到相同的输出。

（4）有可能出现输入不同输出相同（Different in–>Same out），这种情况叫做哈希碰撞。

（5）最重要的特点：输出值尽可能均匀散列（离散性和均匀性，其实是一回事）到输出域上。

- 输入的微小差别，在结果集上会放大到相隔很远；

- 结果集近乎均匀分布。

（6）结果集模一个数M（%），取模的结果在0~M-1上也会比较均匀地分布；

（7）如果因为结果集有限发生大量碰撞，则碰撞的“厚度”也是几乎相等的；

常见的hash函数：

md5

sha1

通过位运算（取模、移位、异或），以及乘以一个素数等方式，实现的哈希函数。

HashMap put时间复杂度分析

一般认为，HashMap的put和get、remove操作时间复杂度都是O(1)，即常数时间复杂度。

可能有人会说，不对呀，比如put操作的时候，HashMap容量不够会有扩容操作，将会重新计算已放入Map中数据的Key的hash值。

好，我们以put操作为例，来分析扩容操作的整体时间复杂度。

假设一开始容量为1，分析连续put进N条不同记录的情况。容量不够的话，容量扩大到原来的2倍。
扩容操作总共进行log2(N)次。
第一扩容需要重新计算hash的次数为1，
第二次，为2
第三次，为4
...
第logN次，为N/2。
总共为（1+2+4+...+N/4+N/2）≈ N
           

即放入N个元素，总共的扩容操作是额外计算N次hash值？，所以平均到每一次是O(1)。

Bitmap位图

计算机中最小的信息单位是比特(bit)。一个bit中只能是0或者1，如果用0代表false，1代表true的话，用1个bit就能够代表某个事物是否出现过。这样用M个比特就能够表达M个事物是否出现过。

这就是位图，通过查找某个bit是1还是0，来表达是出现过，还是没出现过。

这样做的好处是，能够以极低的存储空间表达很大的数据量（M可以很大）。

举个例子，1G大概是10亿bit，那么100亿的数据，只需要10G。

BloomFilter布隆过滤器

布隆过滤器：类似于黑名单，是没有删除行为的黑名单。

预期数据量的上限为n，可以接受的误判率为p。

则可以算出需要的bit数m，以及需要的独立hash函数个数。

（未完待续）