Python 处理存储SHA哈希的大数组 查找首个重复值对应索引方案咨询

你当前使用的嵌套循环时间复杂度为O(n²)，300万数据量下运算量可达万亿级，再加上循环内的频繁打印操作（IO操作耗时远高于CPU运算），运行效率极低是必然结果。以下是两种适合百万级数据的高效方案：

方案1：哈希表遍历法（最优推荐） #

时间复杂度O(n)，仅需单次遍历数组，找到第一对重复索引后立刻终止，300万级数据通常几秒内即可跑完，核心逻辑是用字典存储每个哈希值第一次出现的索引：

def find_dup_index(hash_arr):
    # 字典key为哈希值，value为第一次出现的索引
    first_occurrence = {}
    for idx, val in enumerate(hash_arr):
        if val in first_occurrence:
            # 找到重复直接返回，不需要继续遍历
            return first_occurrence[val], idx
        first_occurrence[val] = idx
    # 你已经确认存在重复，该分支不会触发
    return -1, -1

# 调用示例
index1, index2 = find_dup_index(hash_value_array)
print(f"重复索引：{index1}、{index2}")

该方案的优势：

• 哈希表查找开销为O(1)，全程仅需遍历最多一轮数组
• 找到第一组重复值立刻终止，不需要处理剩余数据
• 无冗余IO操作，额外内存开销仅为存储已出现哈希值的字典，300万条记录仅占百MB级内存，普通设备完全可承载

方案2：排序对比法（内存紧张时可选） #

如果对内存占用有更高要求，可以选择O(n log n)时间复杂度的排序方案，额外开销仅为存储索引的数组：

def find_dup_index_sort(hash_arr):
    # 打包哈希值与原索引，避免排序后丢失原位置信息
    indexed_hash = [(val, idx) for idx, val in enumerate(hash_arr)]
    # 按哈希值排序，重复值会相邻
    indexed_hash.sort()
    # 遍历对比相邻元素即可找到重复
    for i in range(1, len(indexed_hash)):
        if indexed_hash[i][0] == indexed_hash[i-1][0]:
            return indexed_hash[i-1][1], indexed_hash[i][1]
    return -1, -1

原代码的核心问题 #

1. 嵌套循环时间复杂度过高，完全不适合十万级以上的数据量
2. 内层循环每次都执行打印操作，IO耗时是CPU运算的上千倍，进一步拖慢执行速度

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