想象一个程序，它采用长度为 p 的字符串作为参数，并使用仅使用英文字母表的 26 个字母作为键的哈希映射，通过对每个出现的字母加 1 来对每个字母进行计数。我见过这种类型的程序在空间复杂度方面被描述为 O(1)（参见下面的引用）。原因是，由于我们知道密钥集的大小是有上限的，因此空间复杂度是恒定的。
来自技术面试手册：
通常您需要计算字符串中字符的频率。 最常见的方法是在您的应用程序中使用哈希表/映射 选择的语言。如果您的语言有内置的 Counter 类，例如 Python，请问你是否可以使用它来代替。
如果您需要保留字符计数器，一个常见的错误是 假设计数器所需的空间复杂度为 O(n)。这 拉丁字符字符串的计数器所需的空间为 O(1) 不是 O(n)。这是因为上限是字符的范围， 通常是固定常数 26。输入集只是 小写拉丁字符。
我们怎么能这么说呢，在我看来，内存中的地图大小显然会与p的大小成比例增长？如果我们给程序提供长度为 p+1 的输入，那么映射的大小（特别是包含输入中字符计数的整数，即映射本身）一定会比我们提供一个更大输入长度 p?
正如你所说，哈希映射将有最多 26 个条目/字符，每个条目/字符都包含一个整数，可能占用 4 到 8 个字节- 4 个字节已经可以达到：2,147,483,647 作为一个整数.
考虑一下，无论你的字符串参数 (p) 有多长，条目的上限仍然是哈希映射的 26 个字符。因此，空间复杂度不会随着 p 大小而增长，这意味着它不是线性的：O(1)。
:)