gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-04 00:46:53 25 4
gpt4 key购买 nike

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

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

最佳答案

那么对于这种数据有专门的数据结构和算法。
例如,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 字节的字符串,这是一个非常小的数量。

关于size - 哈希表的最大大小应该是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7857088/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com