使用哈希表求两数组交集：应插入哪个数组？含冲突场景分析

这是个非常经典的哈希表应用问题，我来帮你拆解清楚两种场景下的最优策略：

一、无哈希冲突的理想场景 #

在假设完全没有哈希冲突的前提下，最优选择是将规模更小的数组插入哈希表，核心原因在于空间效率的大幅优化：

• 哈希表的构建时间和空间复杂度均为O(n)（n为插入数组的大小）。当两个数组规模悬殊时，比如一个是100元素，另一个是100万元素，用小数组构建哈希表仅需占用100个键值对的空间，而如果插入大数组，需要的空间会是前者的1万倍，内存浪费极其严重。
• 遍历大数组查询哈希表的时间复杂度是O(m)（m为大数组的大小），整体时间复杂度依然是O(n+m)，和反过来的操作时间复杂度一致，但空间成本的差距是决定性的。
• 举个直观例子：如果小数组是[1,3,5]，大数组是包含百万次重复的[1,1,3,3,5,5,...]，把小数组存入哈希表后，遍历大数组时只需做简单的O(1)查询，就能快速筛选出交集元素，内存占用可以忽略不计。

二、存在哈希冲突的实际场景 #

实际工程中哈希冲突几乎无法避免（完美哈希仅适用于特定场景），这时候依然优先选择将小数组插入哈希表，原因如下：

• 更低的负载因子，减少冲突概率：哈希表的负载因子（已存元素数/哈希表容量）是影响冲突频率的核心指标。用小数组构建哈希表时，我们可以设置略大于数组大小的哈希表容量（比如比小数组大20%-50%），将负载因子控制在较低水平（通常推荐0.7以下），从而大幅降低冲突发生的概率，让查询和插入的平均时间更接近O(1)。
• 冲突处理成本更低：构建哈希表时，插入小数组的元素遇到冲突的次数更少，无论是用链表法还是红黑树法处理冲突，开销都远小于插入大数组的情况。如果插入大数组，负载因子会快速升高，冲突链会变得更长，甚至触发哈希表的扩容操作，进一步增加时间成本。
• 开放寻址法的额外优势：如果哈希表采用开放寻址法解决冲突，负载因子过高会导致探测次数激增（最坏情况退化为O(n)）。用小数组构建哈希表能维持低负载因子，探测次数极少，性能更稳定。

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