求一种数据结构能够存储大量字符串分类信息(类似bloomfilter, 但是要存储的数据更多)

Question

有>1000w的md5串, 每个串属于一个分类(分类不超过20). 需要服务端提前把串的分类信息存储到文件, 下发给客户端, 客户端拿到某个md5串之后, 去下发的文件中查找分类信息.

想过使用多个bloomfilter的方式, 但是如果要保证<0.01%的错误率, 1mb的文件最多存储40w个串， 有没有更好的数据结构能够存储更多的串.

Answer 1

抛个砖吧。MD5有128位。1e7个MD5每个只取前若干位也能保证基本不重复。由

$$\frac{10^7}{2^k}<0.01\%$$

得k>=38，即取前38位即可（认为MD5有充分好的散列特性）。再加上所属类别的位数比如4位（16种），得到一个42位的结构。将此结构体数组（长度1e7）按id排序和二分查找。

struct {
  unsigned id: 38
  unsigned category: 4    
} file [10^7];

不考虑字节对齐，这个数组空间是(38+4)*10^7/8/1024/1024 = 50 MB。稍微扩充下空间要求就上百兆了。

update

可否考虑把分类信息和md5存储在一起（扩充或者借位），省去了下发分类文件。