为何统计英文字母的哈希表程序空间复杂度并非线性？

空间复杂度分析的核心是看存储结构的规模随输入增长的趋势，重点是「需要多少个存储单元」，而不是单个单元里存的数值有多大。

你提到的这个场景里，哈希表的键集合固定是26个英文字母——不管输入字符串长度p是1还是100万，哈希表始终只需要维护26个键值对的位置。每个计数用的整数，在绝大多数编程语言里，占用的内存空间是固定的：比如用32位整型的话，永远占4字节；就算是支持动态扩容的数值类型，实际场景中也不会因为输入长度线性增长就无限扩容，而且复杂度分析通常默认采用固定大小的数值类型来评估。

举个直白的例子：输入长度100时，哈希表有26个计数槽位；输入长度100万时，还是这26个槽位。只是槽位里的数值从1变成了几千，但存储这些槽位的总内存空间并没有随p成比例增长——它始终是个固定的常数。所以这类程序的空间复杂度是O(1)完全没问题。

简单说，你混淆了「数值的大小」和「内存占用的规模」——数值本身多大，不直接等于它占用的内存空间，而复杂度分析关注的是存储结构的元素数量，而非元素内部数值的大小。

内容的提问来源于stack exchange，提问作者lordgort