Python字典性能对比C++哈希表及SipHash碰撞生成求助

架构老林

2026-9-27

问题背景

我有一个Python字典，键为小写英文字母组成的字符串，值为整数。该字典共有5e6个唯一键，所有键都是长度恰好为10的字符串。出乎我意料的是，字典查找耗时很短，我原本预期执行时间在4s以上，但实际未超过2.5s。

我将Python代码转换为C代码，使用与字典对应的map容器进行测试，先后尝试了map、unordered_map和gp_hash_table，结果所有C实现的耗时都超过2s。

我使用如下生成器生成唯一字符串：

from sys import stdout

def increment(l):
    n = len(l)
    i = n - 1
    while i >= 0 and l[i] == 'z':
        l[i] = 'a'
        i -= 1
    l[i] = chr(ord(l[i]) + 1)

print(5 * 10**6)

string = ['a' for i in range(10)]

for i in range(5 * 10**6):
    stdout.write(''.join(string) + '\n')
    increment(string)

string = ['a' for i in range(10)]

print(10**6)
for i in range(5 * 10**6):
    stdout.write(''.join(string) + '\n')
    increment(string)

使用命令python3 Test.py > Strings.txt将该程序的输出存储到名为Strings.txt的文件中，文件内容格式如下：

5000000
aaaaaaaaaa
aaaaaaaaab
aaaaaaaaac
aaaaaaaaad
aaaaaaaaae
aaaaaaaaaf
...
...
...
aaaaakymlr
1000000
aaaaaaaaaa
aaaaaaaaab
aaaaaaaaac
...
...
...
aaaaakymlq
aaaaakymlr

上述场景中使用的C++代码如下：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N = 0;
    cin >> N;
    map<string, int> freq;
    // unordered_map<string, int> freq;
    // gp_hash_table<string, int> freq;
    for(int i = 0; i < N; i++) {
        string s;
        cin >> s;
        freq[s]++;
    }
    int Q = 0;
    cin >> Q;
    for(int i = 0; i < Q; i++) {
        string s;
        cin >> s;
        cout << freq[s] << '\n';
    }
    return 0;
}

我使用的Python3代码如下：

from collections import defaultdict
from sys import stdin, stdout

input = stdin.readline

freq = defaultdict(int)
for i in range(int(input())):
    freq[input()] += 1

for i in range(int(input())):
    stdout.write(str(freq[input()]) + '\n')

代码执行结果如下：

suman@Skynet:~/Documents/String_Pairs$ python3 Test.py > Strings.txt

suman@Skynet:~/Documents/String_Pairs$ time python3 Dict.py < Strings.txt > P_out.txt

real    0m3.145s
user    0m2.662s
sys     0m0.164s
suman@Skynet:~/Documents/String_Pairs$ time python3 Dict.py < Strings.txt > P_out.txt

real    0m2.772s
user    0m2.568s
sys     0m0.204s


suman@Skynet:~/Documents/String_Pairs$ g++ -o exe Map.cpp -O2 -std=c++17
suman@Skynet:~/Documents/String_Pairs$ time ./exe < Strings.txt > Cpp_out.txt

real    0m2.346s
user    0m2.265s
sys     0m0.080s
suman@Skynet:~/Documents/String_Pairs$ time ./exe < Strings.txt > Cpp_out.txt

real    0m2.513s
user    0m2.417s
sys     0m0.096s


suman@Skynet:~/Documents/String_Pairs$ g++ -o exe Unordered_Map.cpp -O2 -std=c++17
suman@Skynet:~/Documents/String_Pairs$ time ./exe < Strings.txt > Cpp_out.txt

real    0m2.769s
user    0m2.660s
sys     0m0.108s
suman@Skynet:~/Documents/String_Pairs$ time ./exe < Strings.txt > Cpp_out.txt

real    0m2.806s
user    0m2.690s
sys     0m0.116s


suman@Skynet:~/Documents/String_Pairs$ g++ -o exe gp_hash_table.cpp -O2 -std=c++17
suman@Skynet:~/Documents/String_Pairs$ time ./exe < Strings.txt > Cpp_out.txt

real    0m2.099s
user    0m1.686s
sys     0m0.412s
suman@Skynet:~/Documents/String_Pairs$ time ./exe < Strings.txt > Cpp_out.txt

real    0m2.009s
user    0m1.605s
sys     0m0.404s
suman@Skynet:~/Documents/String_Pairs$

现在我困惑的点在于，Python3的运行速度通常比C慢5倍，但在哈希表操作场景下性能却与C相近。请问有没有办法可以击败Python哈希表的时间复杂度？非常感谢各位的帮助。

更新1

我更新了测试代码，排除了字符串读取的耗时：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using namespace chrono;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N = 0;
    cin >> N;

    vector<string> words(N);

    for(int i = 0; i < N; i++) {
        cin >> words[i];
    }

    // map<string, int> freq;
    // unordered_map<string, int> freq;
    gp_hash_table<string, int> freq;

    auto start = high_resolution_clock::now();
    for(string word : words) {
        freq[word]++;
    }

    auto end = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(end - start);
    cout << duration.count() / 1e6 << '\n';



    int Q = 0;
    cin >> Q;
    vector<string> queries(Q);
    for(int i = 0; i < Q; i++) {
        cin >> queries[i];
    }

    vector<int> results(Q);
    start = high_resolution_clock::now();
    for(int i = 0; i < Q; i++) {
        results[i] = freq[queries[i]];
    }
    end = high_resolution_clock::now();
    duration = duration_cast<microseconds>(end - start);
    cout << duration.count() / 1e6 << '\n';

    for(int i = 0; i < Q; i++) {
        cout << results[i] << '\n';
    }

    return 0;
}

对应的Python代码如下：

from collections import defaultdict
from time import time
from sys import stdin, stdout

input = stdin.readline

freq = defaultdict(int)

strings = []

for i in range(int(input())):
    strings.append(input())

start = time()
for string in strings:
    freq[string] += 1
end = time()
print("%.4f" %(end - start))

queries = []
output = []

for i in range(int(input())):
    queries.append(input())

start = time()

for query in queries:
    output.append(freq[query])

end = time()

print("%.4f" %(end - start))

stdout.write('\n'.join(map(str, output)))

即便排除IO耗时，Python的运行速度仍然快于C++。测试结果如下：
Cpp_out.txt（map、unordered_map和gp_hash_table的耗时均大于2s）：

2.28297
0.109844
1
1
...
...
...

P_out.txt：

1.7818
0.1977
1
1
...
...

更新2

我再次修改了代码，排除了读写耗时，且在C代码中全量使用引用传递。此时C的哈希性能优于Python3的结果符合预期，基准测试结果如下：

// CPP Code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using namespace chrono;

struct djb2 {
    unsigned long operator()(const string& str) const {
        unsigned long hash = 5381;
        for (auto c : str)
            hash = ((hash << 5) + hash) + c;
        return hash;
    }
};


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N = 0;
    cin >> N;

    vector<string> words(N);

    for(int i = 0; i < N; i++) {
        cin >> words[i];
    }

    // map<string, int> freq;
    // unordered_map<string, int> freq;
    gp_hash_table<string, int> freq;

    auto start = high_resolution_clock::now();
    for(const string &word : words) {
        freq[word]++;
    }

    auto end = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(end - start);
    cout << duration.count() / 1e6 << '\n';



    int Q = 0;
    cin >> Q;
    vector<string> queries(Q);
    for(int i = 0; i < Q; i++) {
        cin >> queries[i];
    }

    vector<int> results(Q);
    start = high_resolution_clock::now();
    for(int i = 0; i < Q; i++) {
        results[i] = freq[queries[i]];
    }
    end = high_resolution_clock::now();
    duration = duration_cast<microseconds>(end - start);
    cout << duration.count() / 1e6 << '\n';

    for(int i = 0; i < Q; i++) {
        cout << results[i] << '\n';
    }

    return 0;
}

# Python3 Code
from collections import defaultdict
from time import time
from sys import stdin, stdout

input = stdin.readline

freq = defaultdict(int)

strings = []

for i in range(int(input())):
    strings.append(input())

start = time()
for string in strings:
    freq[string] += 1
end = time()
print("%.4f" %(end - start))

queries = []
output = []

for i in range(int(input())):
    queries.append(input())

start = time()

for query in queries:
    output.append(freq[query])

end = time()

print("%.4f" %(end - start))

stdout.write('\n'.join(map(str, output)))

Cpp_out.txt：

1.60026
0.071471

P_out.txt：

1.7849
0.1987

可见C++的gp_hash_table性能优于Python3的哈希表。

我查阅了Python3的哈希表实现，其字符串哈希使用了SipHash算法。我想要生成可以最大化哈希碰撞次数的字符串，本质类似碰撞攻击，需求是至少有5000个唯一字符串可以生成相同的哈希值。请问有没有相关的资源可以提供？

解答

哈希表性能优化方案

你已经通过修复C遍历过程中的值拷贝问题、使用gp_hash_table开放寻址哈希表的方式实现了性能反超，这符合预期。Python的字典底层是经过多年优化的C实现，普通C标准库哈希容器如果没有针对性优化（避免冗余拷贝、选用开放寻址实现、适配场景的哈希函数），性能确实可能落后于Python字典。
如果需要进一步提升性能，还可以针对你的场景做定制优化：你的键是固定10位的小写字母，每个字母仅需5bit存储，10位总共仅需50bit，可以直接编码为64位整数作为哈希表的键，完全跳过字符串哈希和字符串比较的开销，性能还能有数倍提升。

生成Python字符串哈希碰撞的方案

Python 3.x默认使用SipHash算法计算字符串哈希，且进程启动时会随机生成哈希种子，碰撞字符串仅对同一哈希种子的进程有效，无法跨进程通用。
要生成满足需求的碰撞字符串，可按以下步骤操作：

固定Python哈希种子：设置环境变量PYTHONHASHSEED为固定数值（如0），保证每次启动Python的哈希计算结果一致。
针对固定种子暴力碰撞：由于你的字符串是固定10位小写字母，用生日攻击的思路生成大量随机字符串，计算哈希值并记录反向映射，普通消费级硬件几分钟内就能收集到超过5000个哈希值相同的唯一字符串。
如果要针对未知哈希种子生成通用碰撞，目前公开的SipHash碰撞攻击算力门槛较高，普通硬件很难快速生成大规模碰撞。

内容的提问来源于stack exchange，提问作者Sai Suman Chitturi

Python字典性能对比C++哈希表及SipHash碰撞生成求助

更新1 #

更新2 #

哈希表性能优化方案 #

生成Python字符串哈希碰撞的方案 #

更新1

更新2

哈希表性能优化方案

生成Python字符串哈希碰撞的方案