algorithm - Lisp gethash 复杂性

Question

gethash 函数的时间复杂度是多少？例如，在 c++ 中，map 的搜索时间为 O(log(n))，而 unordered_map 的时间为 O(1) 。这两件事都写在描述中，但我找不到 Lisp 中 gethash 的任何此类引用。

实际上，这扩展到所有标准库函数。我在哪里可以找到它们的复杂性，或者我可以？谈论 sbcl，如果这很重要的话。

Answer 1

ANSI CL 标准没有指定算法复杂度的原因库函数是它不是它的工作。该标准描述了行为，并将性能留给特定于实现的文档。假定所有实现都将提供最佳的理论性能(否则没有人会使用它)。

要回答您的具体问题，gethash在所有实现中都是 O(1)。