logo标签列表

在Shell脚本中，关联数组的时间复杂度是什么？

algorithmshellscriptingassociative-arraytime-complexity
3

我想了解当在shell脚本中使用关联数组时，它是如何构建/实现的。

此外，我想知道基于shell脚本的关联数组的时间复杂度是否是最优的，因为我们可以使用字母和数字作为它们各自的键。

编辑：它们使用什么哈希函数？

以ksh为例，确切地说是ksh93。虽然这是一个非常通用的问题，我想问所有的shell。 - tomkaith13
你不能要求它返回“所有的shell” - 这取决于具体的实现。 - Brian Roach
@Brian：好的，那么我想了解具体的ksh93。 - tomkaith13
1个回答
3

如果您正在使用关联数组，那么您不是通过“使用字母和数字作为它们各自的键”来访问它；您正在使用字符串-任何数字都是字符表示形式，而不是实际索引。

除非查看源代码，否则我找不到任何具体内容，但根据大多数帐户，内部实现为哈希表（而不是树），因此您的访问和插入平均时间将为O（1）。这不能更加优化。

@Brian：那么查找函数如何处理字符串呢？假设其中一个键是“我是查找键”，另一个键是“我是另一个查找键”。内部数据结构如何容纳这样一个大字符串？其次，字符串大小是否有限制？ - tomkaith13
你可能想要阅读关于哈希表的维基百科条目，以了解它的工作原理。至于键的长度，那将是特定于ksh93，我找不到任何列出它的东西。我想象它会相当长，而且它可能会截断任何太长的内容。 - Brian Roach
@Brian：非常感谢你的帮助。我熟悉哈希表，并正在尝试查找Solaris中的关联数组实现。我真的不知道应该在哪里寻找它。这就是我在StackOverflow上提出这个问题的原因。我正在尝试找到开发人员用于将键映射到其各自的内存位置的哈希函数。再次感谢。 - tomkaith13
我在谷歌上搜索了很久都没有找到。最好的方法是下载ksh的源代码并查看它。现在可以在http://www.kornshell.com/software/上获取。 - Brian Roach
1
回答你的第一个问题（抱歉，我错过了）-它不存储字符串，因此不必容纳任何内容。它只是对字符串进行哈希处理，以获得数组范围内的数字结果。他们说数组限制为4096个项目，因此哈希算法将产生介于0和4095之间的某些结果。 - Brian Roach
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接