对于普通编程语言的哈希表实现来说，什么大小算是太大？
比如我想写一个程序来玩“相声词”游戏。用户输入一个单词后，程序需要在字典中查找该单词是否存在。为了避免不断地读取文件，将10万个以上的单词加载到哈希表中是否明智呢？
3个回答
6
好的，有专门针对这种数据的数据结构和算法。例如 Patricia Trie 或基数树，它们对于字符串的空间利用率比哈希表高得多，但是，作为一棵树，查找的计算复杂度为 O(log n)，构建的时间复杂度为 O(n log n)。然而，由于你是从文件中加载它，因此可以以 O(n) 的方式编写文件，以便能够快速加载。
C# 中的哈希表（Dictionary）是这样实现的，它没有上限，除了使用内部 32 位整数寻址（它肯定不能超过 20 亿个项）。
对于字典，100000 项并不算太多。对于垃圾回收器可能更具问题的语言来说，你将有 100000 个已分配的字符串，这会给你的 GC 带来一些压力。只有运行应用程序才能获得有关实际应用程序内存占用的更多信息。
如果内存真正成为问题，请寻找 Patricia Trie 和基数树，它们非常适合存储单词词典。但是你可以先使用字典，看看你的应用程序会使用多少内存。
粗略计算一下，考虑到字符串是 Unicode 编码的，考虑到英文平均单词长度为 5.1 个字母（我在网上读到的），并考虑每个字符串需要 32 个字节（用于对象和长度），则每个字符串至少需要 (100000 * (32 + 5 * 2)) 字节的内存，即 4200000 字节的内存，这是一个非常小的数量。
C# 中的哈希表（Dictionary）是这样实现的，它没有上限，除了使用内部 32 位整数寻址（它肯定不能超过 20 亿个项）。
对于字典，100000 项并不算太多。对于垃圾回收器可能更具问题的语言来说，你将有 100000 个已分配的字符串，这会给你的 GC 带来一些压力。只有运行应用程序才能获得有关实际应用程序内存占用的更多信息。
如果内存真正成为问题，请寻找 Patricia Trie 和基数树，它们非常适合存储单词词典。但是你可以先使用字典，看看你的应用程序会使用多少内存。
粗略计算一下，考虑到字符串是 Unicode 编码的，考虑到英文平均单词长度为 5.1 个字母（我在网上读到的），并考虑每个字符串需要 32 个字节（用于对象和长度），则每个字符串至少需要 (100000 * (32 + 5 * 2)) 字节的内存，即 4200000 字节的内存，这是一个非常小的数量。
- Salvatore Previti
2
感谢您的回复和建议。我不确定哈希表是否存在物理限制或者是否存在一定程度上的退化，以至于您可能不想使用它们。我认为这主要取决于语言的实现方式。 - Jimmy Zelinskie
一个只因为100,000个字符串而开始崩溃的垃圾回收器将是一个相当糟糕的回收器。 - Hot Licks
0
除了物理限制（RAM）和实现限制（Java哈希映射 vs C#哈希映射 vs STL或Boost等）之外；我认为哈希表大小的上限“应该”取决于哈希算法。 原始意图是：随着集合大小的增长，哈希映射实现常量查找时间。如果您有一个好的哈希算法，那么可以为大量值生成唯一的键；但如果您有一个糟糕的哈希算法，那么当您开始出现冲突时（例如，两个唯一的输入进入您的哈希算法生成相同的值），您的查找时间就会崩溃，并且你需要使用技巧来避免冲突。
但这不应该是您寻找的答案。 我只是提出这个观点，以增加讨论中尚未解决的另一个要点。 我认为您应该研究@Salvatore Previti的回答。 鉴于您面临的问题，他提到的解决方案似乎更适合。
- Dave
-1
“太大”？这就像在问，“什么是最好吃的食物？”
哈希表越大，占用的内存空间就越多，但速度就会更快。你必须决定哪个更重要，是空间还是时间。
哈希表越大，占用的内存空间就越多，但速度就会更快。你必须决定哪个更重要，是空间还是时间。
- Michael Lorton
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接