size - 哈希表的最大大小应该是多少？

Question

对于散列表的平均编程语言实现来说，多大是太大？

假设我想创建一个玩游戏的程序 Shiritori .用户输入一个词后，如果该词存在，程序需要查字典。为了防止持续的平面文件读取，在程序启动时将 100,000 多个单词加载到哈希表中是一个明智的解决方案吗？

Answer 1

那么对于这种数据有专门的数据结构和算法。
例如，Patricia Trie 或基数树的空间效率远高于字符串的哈希表，但当然，作为一棵树，查找计算复杂度为 O(log n)，构建复杂度为 O(n log n)。由于您是从文件中加载它，因此您可以以可以在 O(n) 中加载它的方式编写文件。

C# 中的哈希表(字典)以这样一种方式实现，它没有上限，除了它使用内部 32 位整数寻址(它肯定不能超过 20 亿个项目)。

100000 项对于字典来说不算多。
对于带有垃圾收集器的语言来说，更大的问题可能是您将有 100000 个分配的字符串，这对您的 GC 来说是一些压力。
只有运行它，您才能获得有关实际应用程序内存占用的更多信息。

如果内存是一个真正的问题，请寻找 Patricia Trie 和 Radix Tree，非常适合存储单词词典。
但是您可以开始使用字典并查看您的应用程序获得了多少内存。

做一个粗略的计算，将字符串视为 unicode，并考虑到英语中的平均单词是 5.1 个字母(我在网上阅读)并考虑每个字符串加上 32 个字节(用于对象和长度)，您将获得最少的内存(100000 * (32 + 5 * 2)) 内存用于 4200000 字节的字符串，这是一个非常小的数量。