计数数组和桶数组有什么区别？什么时候可以用数组代替哈希表？

简化版

计数数组用下标表示值或类别，用元素值表示出现次数；桶数组用下标表示范围或分组，用桶里内容保存数据。值域较小、可映射成整数下标时，数组常比哈希表更快、更省常数开销。

详细版

计数数组和桶数组都利用“下标可直接定位”的特点。

计数数组适合统计字符、数字频次，例如 26 个小写字母。
桶数组适合按范围分组，例如分数段、年龄段、哈希桶。
如果 key 的值域小且连续，可以直接用数组下标作为 key。
数组方案访问 O(1)，常数小；但值域太大时会浪费空间。
哈希表更通用，适合 key 稀疏、范围大或不是整数的情况。

完整版教学

一、为什么数组有时能替代哈希表

哈希表的核心也是把 key 映射到位置，但它要经过哈希计算、冲突处理、扩容等步骤。如果 key 本身就是一个小范围整数，比如字符 'a' 到 'z'，那就没必要再绕一层哈希表。直接用 count[charCode - 97] 就能定位频次。数组的优势来自更简单的寻址路径和更好的缓存局部性。

const count = new Array(26).fill(0);
for (const ch of s) {
  count[ch.charCodeAt(0) - 97]++;
}

记忆钩子：能把 key 稳定映射成“小整数下标”时，数组就是最轻量的哈希表。

二、计数数组的本质

计数数组的下标表示某个值，数组元素表示这个值出现了多少次。例如 count[3] = 5 表示数字 3 出现了 5 次。它适合频次统计、计数排序、字符构成判断、出现次数比较等问题。计数数组不是只能统计次数，也可以存布尔值、最后出现位置、最早出现位置等，只要下标语义清楚即可。

nums: [2, 3, 2, 5, 3, 2]
count[2] = 3
count[3] = 2
count[5] = 1

三、桶数组的本质

桶数组更强调“分组”。每个下标不是一个精确值，而可能是一段范围或一个分组。例如成绩 0–59 放桶 0，60–69 放桶 1，70–79 放桶 2。桶里可以存数量，也可以存列表。桶思想常用于桶排序、Top K、频率分组、分段统计等场景。它牺牲一些精确映射，换取按范围聚合处理。

结构	下标含义	元素含义
计数数组	精确值或类别	次数/状态
桶数组	范围或分组	一组元素或统计值
哈希表	任意 key 的哈希位置	key-value

四、带数字比较空间代价

如果统计小写字母，计数数组只要 26 个格子，非常划算。如果统计用户 ID，而 ID 最大可能是 10 亿，但实际只有 1000 个用户，开长度 10 亿的数组就荒唐了。此时哈希表更合适，因为它只为实际出现的 key 存储数据。选择数组还是哈希表，核心不是复杂度都写 O(1)，而是看值域大小和稀疏程度。

26 个字母：数组 26 格，非常合适
ID 范围 0..1,000,000,000：数组巨大，哈希表更合适

五、为什么数组常数更小

数组下标访问通常是一次边界检查和地址计算，内存连续，CPU 缓存友好。哈希表要计算哈希值，定位桶，再处理冲突，内存布局也更分散。在高频统计场景里，数组可能明显快于哈希表。面试时如果只说“都是 O(1)”是不够的，应该补上常数成本和缓存局部性的差异。

数组：base + index * elementSize
哈希表：hash(key) -> bucket -> compare key -> handle collision

六、工程上怎么避免下标错误

使用计数数组时，最容易错的是映射公式。比如字符频次要确保字符范围真的是小写字母，否则 ch - 'a' 可能越界。数字有负数时，要加 offset，比如值域 [-100,100] 可以映射到 [0,200]。如果值域无法提前确定，坐标压缩或哈希表会更稳。数组方案越快，越要求你把下标映射设计清楚。

// 值域 [-100, 100]
const offset = 100;
const count = new Array(201).fill(0);
count[x + offset]++;

七、常见误区与追问

误区：数组代替哈希表一定更省空间。 值域大而稀疏时，数组会浪费大量空间。
误区：桶数组和计数数组完全一样。 计数数组多用于精确值频次，桶数组多用于范围或分组。
误区：只要是数字 key 就该用数组。 还要看值域是否小、是否连续、是否可控。
追问：有负数怎么用计数数组？ 可以加 offset，把负数范围平移到非负下标。
追问：为什么数组常数小？ 下标寻址简单且连续内存缓存友好，哈希表有哈希和冲突处理开销。

八、加强记忆

计数数组和桶数组可以记成“用下标表达含义”。如果下标代表精确值，元素存次数，就是计数数组；如果下标代表范围或分组，元素存一组数据，就是桶数组。面试里先讲适用条件：小值域、可映射、连续，再讲哈希表边界：大范围、稀疏、非整数，这样选择理由就很清楚。

简化版

详细版