计数数组与简易哈希

哈希表的本事是「由 key 一步定位」,而数组下标天生就是一步定位。开全局 int cnt[100],扫到数 x 就 cnt[x]++——不用先查「x 在不在」,全局数组每格天生是 0,直接加就行,比哈希表还省一步。还有个附带好处:按下标扫 cnt,输出天然从小到大有序,这是哈希表给不了的。

计数数组的前提是值域开得下:key 大到 10 亿时,int 数组要约 4GB,直接爆内存。这时用哈希函数 hash(key) = key % 模数 把大 key 折进小桶;两个 key 算到同一个桶叫哈希冲突,用拉链法把它们挂成一条链,查找时先 % 定位到桶、再沿链比对。实战里模数取大质数(如 100003)让 key 摊得更开。C 没有链表容器,链常用数组模拟(head 数组 + nxt 数组)。

能开数组就开数组:一行代码、稳定 O(1)、自带有序。值域开不下、或 key 是负数/超大数,才动用约 20 行的拉链哈希,或者先 qsort 排序让相同值相邻、一趟数过去。机试时间宝贵,判断的第一步永远是看值域。