Python中求两个无序列表公共元素：字典法与哈希表法哪种更优？

你提到了两个用于找出无序列表公共数字的Python实现，咱们先把代码摆出来，再逐一分析各自的优劣：

def common_by_dictionary(a1,a2):
    d1 = {}
    for i in a1:
        if not(i in d1):
            d1[i]=1
    for i in a2:
        if (i in d1):
            d1[i]=0
    c = []
    for i in d1:
        if(d1[i]==0):
            c.append(i)
    print(c)

def common_by_hashmap(a1,a2):
    h = [0]*1000
    for i in a1:
        if not (i in h):
            h[i]=1
    c = []
    for i in a2:
        if(h[i]==1):
            c.append(i)
    print(c)

common_by_dictionary([1,3,4,6,7,9,12,5],[1,2,4,5,9,10,3])
common_by_hashmap([1,3,4,6,7,9,12,5],[1,2,4,5,9,10,3])

先拆解两个函数的核心逻辑 #

• common_by_dictionary：用Python原生字典（本质是哈希表）实现，先遍历第一个列表，把所有唯一元素存入字典（键为元素，值设为1）；再遍历第二个列表，遇到字典里存在的元素就把对应值改成0；最后收集所有值为0的键，得到两个列表的去重公共元素。
• common_by_hashmap：用固定长度的列表模拟哈希表，先遍历第一个列表，把元素对应的索引位置设为1（这里有个逻辑陷阱，后面细说）；再遍历第二个列表，把对应索引位置为1的元素加入结果，得到的是包含重复元素的公共列表（如果第二个列表有重复公共元素）。

对比维度分析，哪个更优？ #

1. 通用性：common_by_dictionary完胜 #

• common_by_dictionary支持所有可哈希类型：不仅是整数，字符串、不可变元组等都能作为列表元素，而且没有数值范围限制——哪怕你的列表里有10000、-5这样的数，也不会报错。
• common_by_hashmap局限性极强：只能处理0到999之间的整数，如果元素超过这个范围，直接抛出IndexError索引越界；而且只能处理整数类型，其他类型根本无法作为列表索引使用。

2. 逻辑正确性：common_by_dictionary更可靠 #

• common_by_dictionary的逻辑完全正确：字典的键天然去重，最终得到的是两个列表的交集（去重），符合大多数场景的需求。
• common_by_hashmap存在两个明显问题：
  • 错误的判断条件：if not (i in h)是检查元素i是否存在于列表h中，而不是检查对应索引位置是否为0。比如如果h里有某个位置被设为1，当a1里出现另一个值为1的元素时，i in h会返回True，不会重复赋值，这部分碰巧没问题，但逻辑本质是错的——正确的判断应该是if h[i] == 0。
  • 结果包含重复元素：如果第二个列表里有重复的公共元素（比如a2=[1,1]），结果会把1加入两次，这未必是用户想要的；而common_by_dictionary只会保留一个。

3. 时间与空间复杂度：各有特点，但common_by_dictionary更实用 #

• 时间复杂度：两者都是O(n+m)（n是a1长度，m是a2长度），属于线性时间，效率相近。不过common_by_hashmap里的i in h是O(1000)的常数时间（因为列表长度固定），而字典的i in d1是O(1)平均时间，实际运行效率差异不大。
• 空间复杂度：common_by_hashmap是O(1)固定空间（1000个元素的列表），但这是以牺牲通用性为代价的；common_by_dictionary是O(k)空间（k是a1的唯一元素数量），空间随数据规模动态变化，更灵活。

结论 #

毫无疑问，common_by_dictionary是更优的方案——它通用性强、逻辑正确、能适应绝大多数场景；而common_by_hashmap只适用于非常狭窄的特定场景（元素是0-999的整数，且需要保留重复的公共元素），还存在潜在的逻辑bug和索引越界风险。

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