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

[Phishion]

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

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

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

[levelworm]

小白求问：
1. 32 位可以吗？
2. 如果用 binary 可以吗？

[Phishion]

谢谢大伙儿，我研究研究

[mattx]

@cmdOptionKana
@DevRoss
@no1xsyzy
@ZhangZisu 使用 文件数据库是否内存会更少，leveldb lmdb sqlite 之类的。

[lujjjh]

看要根据 key 查 value，还是需要遍历，如果只需要根据 key 查 value：
1. 用 md5(s) 代替 s，碰撞理论上可忽略，64 bytes → 16 bytes (binary)
2. map<md5(s), int> 变成 [md5(s), int]，按照 md5(s) 排序，100 万条数据二分查找 20 次以内

[lujjjh]

更正 [md5(s), int] → [(md5(s), int)]，或者写成 list<(md5(s), int)>

[no1xsyzy]

突然想到
>>> sys.getsizeof("")
49
>>> sys.getsizeof(1)
28
这个开销本身就有点高啊，单建立对象的开销就比你要存的内容高了……

@ericls 你是不是直接 sys.getsizeof([...big list...]) 了？ Python 下对容器对象用这个方法只会计算容器本身和其中存储的引用的大小，而不包括被引用对象的大小。
>>> sys.getsizeof(["a"*2**10])
64
>>> sys.getsizeof("a"*2**10)
1073

[no1xsyzy]

@mattx 显然的，就是进一步用时间换空间了，你不嫌慢放对象存储甚至冷存储都没关系（

[ipwx]

@ZhangZisu 我觉得楼主这个需求，trie 树不太好用。因为楼主的字符串是真随机，trie 树每层都会分出一堆节点，基本是个满 K 叉树，比一个大哈希表用更多内存

[ericls]

@no1xsyzy TIL. Thanks!

[aijam]

可以试试这个
https://github.com/google/pygtrie

```
>>> t = pygtrie.CharTrie()
>>> t['dn0pFVBjQGwRYKCO2Ix45ibo6r9kW3Zedn0pFVBjQGwRYKCO2Ix45ibo6r9kW3Ze'] = 1
>>> t['XuYRUn50f7j9zG2k8EZvoaWmeAdqTVrQXuYRUn50f7j9zG2k8EZvoaWmeAdqTVrQ'] = 2
>>> t['dn0pFVBjQGwRYKCO2Ix45ibo6r9kW3Zedn0pFVBjQGwRYKCO2Ix45ibo6r9kW3Ze']
1
>>> t['XuYRUn50f7j9zG2k8EZvoaWmeAdqTVrQXuYRUn50f7j9zG2k8EZvoaWmeAdqTVrQ']
2
```

[ZhangZisu]

@ipwx 对，是一个大哈希表更好。

如果完整建 trie 是难以承受的。如果只建前几层，后面挂链表遍历，空间时间权衡一下应该也还行。

[ericguo]

这不就是 GDBM 的作用么。。https://cloud.tencent.com/developer/section/1366972

[des]

@ZhangZisu 后边挂链表的话，前面还是用 hashcode 比较好
因为如果字符串不随机的话，有可能会出现超长链表

[wellsc]

@Phishion 肯定比 Python 的字典省资源，还有 redis 自己的高可用方案

[jorneyr]

自己实现一个 LRU 缓存算法，不需要一次把所有的都加入内存

[ipwx]

@ZhangZisu 但其实哈希表用平方探测不是只要两倍内存就基本能保证性能么。。而且两倍的是哈希表节点而不是字符串。用上 StringPool + string_view 咱觉得基本就是最好的方案了。

@Phishion 咱多少觉得，楼主有种 XY Problem 的感觉。到底什么场景下 400MB 的表都会 concern ？是不是和多进程有关？ Linux fork 的话，因为内存使用是 COW 的，所以可以主进程创建完整个表，然后子进程就不用创建第二份了。

那如果是设备内存太小，或者本身楼主要处理的不是 400MB 而是 40GB 这种场景，那可能就需要使用 disk-backend 的数据结构了。比如 B-Tree 。

[MoYi123]

用 karp-rabin 怎么样? 一个字符串可以压成 int32. 缺点是会丢失原始字符串.

[kksco]

用 go 。。python 分配一个变量就 24 byte 打底了，太恐怖了

[leimao]

这。。。query complexity 和 memory complexity 你鱼和熊掌想要兼得是不可能的。memory 用的最少的就是一个 list，只不过你 query 起来很慢。你想要追求一个平衡点，那你就自己写个 hash table 手动把这个 hash table 的 size 弄的小一些，这样 hash conflicts 几率就高了，牺牲了 query 效率换取了部分内存。

[leimao]

我自己虽然在 Python 和 C++都没写过，但印象中 C++可以自己写 hash，你可以查查相关资料。最简单的就是你这个 hash table size 只有 1，直接退化成 list 。