我想维护一个大型字典，有没有什么省内存的方法

[Phishion]

字典大概是下面这样的结构，我粗跑了一下，大概 100W 条数据，占用 400M 内存

{'dn0pFVBjQGwRYKCO2Ix45ibo6r9kW3Zedn0pFVBjQGwRYKCO2Ix45ibo6r9kW3Ze': 1, 'XuYRUn50f7j9zG2k8EZvoaWmeAdqTVrQXuYRUn50f7j9zG2k8EZvoaWmeAdqTVrQ': 2, 
....
't2n9wLoU53ql4hPMHi7pFaIEkCRxNuf0t2n9wLoU53ql4hPMHi7pFaIEkCRxNuf0',1000000}

有没有方法能大幅度减少内存的占用？

[leimao]

反正我觉得讨论这个怪怪的，可能我平时不做这方面的东西不 care 这个吧

[lujjjh]

既然没有人贴代码，我就先抛砖引玉了。19 MB，二分查找。

https://gist.github.com/lujjjh/fecf55f6827cce011bb71682e9b8594a

[leimao]

@lujjjh 一楼计算过最少 64MB，你 19MB 怎么出来的？

[lujjjh]

@leimao 思路在 #24 。虽然楼主并没有把需求描述清楚（只是要根据 key 查 value，还是也需要遍历），但是 100 万的量级显然可以假设是不需要遍历的，那么 key 就不需要存原始的字符串，存 hash 就可以了。

如果需要遍历，又要让内存小于 64 MB，就需要在 key 和 value 的编码方式上做手脚了。当然，楼主不介意 64 MB，只需要把我代码里对 key 做 MD5 的逻辑删除即可。

[tairan2006]

用时间换空间…

那你直接存 sqlite 里不就完了…

[ipwx]

@lujjjh 哈希只能是概率性不冲突啊，虽然概率小，但是不能保证程序**一定**正确不是么？

楼主没有讲可以概率性正确，你这就加上这个条件，这不好。

[est]

这字符一看就是 base64 转成二进制还能更小

[lujjjh]

@ipwx 没法保证程序**一定**正确，内存也有概率出错 :doge:

如果没有算错，任意一个字符串 MD5 跟这 100 万中至少一个发生冲突的概率大概在 2^(-108)，工程上基本没什么问题，即便安全性弱如 MD5，依旧很难找出特例。

当然，肯定是有场景不满足于这个概率的，但这种场景我想不会在意 64 MB 内存的。

[ipwx]

@lujjjh 虽然你说的对，这个场景的冲突概率很低，但是并没有低到 2^(-128)。这是典型的生日问题，因为你的问题不是给定某个特定川，表里面有川和它冲突的概率，而是表里面有任意两个串冲突的概率。

https://en.wikipedia.org/wiki/Birthday_problem#Probability_table

这里写出来结论了，超过 p=0.001 有任意两个串冲突，表里面需要有 8*10^17 个元素就行。

[lujjjh]

@ipwx 不同量级的数据解决方案是不同的，8*10^17 跟 10^6 量级相差巨大，最优的解决方案也不一样。

另外这里不适合直接套用生日问题的结论，因为表里的数据是已知的，表里面是否有冲突在建表的时候就可以知道。我计算的是在保证表里面的数据不存在冲突的情况下，查询任何一个 key'，其 hash(key') ∈ T 且 key' ≠ key 的概率。