寻求适配特定整数密钥的高效哈希函数，提升Julia字典性能

问题背景 #

在Julia程序中处理大量含重复密钥的键值对，需合并相同密钥的对应值：

• 密钥为二进制长度固定、1的个数（汉明重量）固定的整数
• 值为复数，实际用于表示稀疏向量
• 此前采用排序合并法（排序密钥并同步置换值后累加），尝试Julia原生Dict逐个添加键值对，但性能提升有限，希望找到适配该场景的高效哈希方案。

测试代码 #

using SparseArrays
using StatsBase
using TimerOutputs

n_qubits = 30
N_e = 10
function get_basis(n_qubits::Int64, N_e)
    basis_num::Int64 = factorial(big(n_qubits))/factorial(big(N_e))/factorial(big(n_qubits-N_e))
    basis_set = Array{Int64, 1}(undef, basis_num)
    count::Int64 = 0
    for i in 0:(2^n_qubits-1)
        if count_ones(i) == N_e
            count += 1
            basis_set[count] = i
        end
    end
    return basis_set
end

basis_num = 2^16
basis = get_basis(n_qubits, N_e)
sp_len = min(basis_num, length(basis))
idx = sample(1:length(basis), sp_len)
sp_row::Vector{Int64} = basis[idx]
sp_val::Vector{ComplexF64} = rand(sp_len) + rand(sp_len) * im


function get_dict(dict_size::Int64)
    @time res_dict::Dict{Int64, ComplexF64} = Dict{Int64, ComplexF64}(zeros(UInt8,dict_size), zeros(Int64,dict_size), zeros(ComplexF64,dict_size), 0, 0, 0, 1, 0)
    @time for _ in Base.OneTo(10)
        for i in eachindex(sp_row)
            if sp_row[i] in keys(res_dict)
                res_dict[sp_row[i]] += sp_val[i]
            else
                setindex!(res_dict::Dict{Int64, ComplexF64}, sp_val[i]::ComplexF64, sp_row[i]::Int64)
            end
        end
        empty!(res_dict)
    end
    println()
end

get_dict(2^19)
for i in 10:22
    println(i)
    # get_dict(2^i - 1)
    get_dict(2^i)
    # get_dict(2^i + 1)
end


println()

@time for _ in Base.OneTo(10)
    sparsevec(sp_row, sp_val)
end
@time for _ in Base.OneTo(10)
    sparsevec(sp_row, sp_val)
end
@time for _ in Base.OneTo(10)
    sparsevec(sp_row, sp_val)
end

测试输出 #

10
  0.000005 seconds (4 allocations: 25.391 KiB)
  0.019551 seconds (23 allocations: 8.302 MiB)

11
  0.000006 seconds (5 allocations: 50.438 KiB)
  0.016879 seconds (17 allocations: 4.102 MiB)

12
  0.000092 seconds (6 allocations: 100.359 KiB)
  0.019492 seconds (18 allocations: 8.204 MiB)

13
  0.000160 seconds (6 allocations: 200.359 KiB)
  0.017443 seconds (12 allocations: 3.907 MiB)

14
  0.000302 seconds (7 allocations: 400.281 KiB)
  0.018941 seconds (12 allocations: 7.813 MiB)

15
  0.000591 seconds (7 allocations: 800.281 KiB)
  0.016249 seconds (6 allocations: 3.125 MiB)

16
  0.001143 seconds (7 allocations: 1.563 MiB)
  0.016624 seconds (6 allocations: 6.250 MiB)

17
  0.002178 seconds (7 allocations: 3.125 MiB)
  0.013382 seconds

18
  0.004379 seconds (7 allocations: 6.250 MiB)
  0.011950 seconds

19
  0.008678 seconds (7 allocations: 12.500 MiB)
  0.012182 seconds

20
  0.032966 seconds (7 allocations: 25.000 MiB, 47.46% gc time)
  0.013622 seconds

21
  0.033038 seconds (7 allocations: 50.000 MiB)
  0.015635 seconds

22
  0.089011 seconds (7 allocations: 100.000 MiB, 24.47% gc time)
  0.021704 seconds


  0.137010 seconds (1.43 k allocations: 30.063 MiB, 41.84% compilation time)
  0.079798 seconds (130 allocations: 30.003 MiB)
  0.080075 seconds (130 allocations: 30.003 MiB)

优化方案 #

1. 自定义适配汉明重量特性的哈希函数 #

利用密钥汉明重量固定的特性，基于置位的位置构造哈希，减少冲突：

import Base: hash

function hash(x::Int64, h::UInt)
    # 提取所有1的二进制位置
    bits = bitpositions(x)
    h_val = h
    # 对位置序列迭代哈希
    for b in bits
        h_val = hash(b, h_val)
    end
    return h_val
end

该方案避免原生哈希对全整数域的无差别处理，针对同汉明重量密钥的结构优化哈希分布。

2. 预分配最优大小的Dict #

从测试结果看，Dict大小在2^17-2^19区间时，循环处理时间最优（0.011-0.012秒）。过大的Dict会引发内存分配和GC开销（如2^22时GC占比24.47%）。建议根据唯一密钥的预估数量，将Dict初始大小设为该数量的1.2-1.5倍，避免动态扩容开销。

3. 用get!替代in判断优化查找逻辑 #

原代码中sp_row[i] in keys(res_dict)的判断会额外遍历密钥集合，改用get!可一步完成查找、插入与更新：

for i in eachindex(sp_row)
    get!(res_dict, sp_row[i]) do
        zero(ComplexF64)
    end += sp_val[i]
end

该写法减少一次哈希查找，提升循环效率。

4. 尝试专用哈希结构 #

对于固定类型的整数密钥与复数值，可尝试第三方包的专用哈希结构：

• StaticArrays.jl的StaticDict：适合小容量场景，减少动态调度开销
• HashDict.jl：针对整数密钥优化的哈希实现，性能优于原生Dict

5. 排序法的补充优化 #

若哈希法提升有限，可优化排序合并逻辑：用sortperm获取排序索引后批量累加，避免数组同步置换的开销：

perm = sortperm(sp_row)
sorted_rows = sp_row[perm]
sorted_vals = sp_val[perm]
result = Dict{Int64, ComplexF64}()

current_key = sorted_rows[1]
current_val = sorted_vals[1]
for i in 2:length(sorted_rows)
    if sorted_rows[i] == current_key
        current_val += sorted_vals[i]
    else
        result[current_key] = current_val
        current_key = sorted_rows[i]
        current_val = sorted_vals[i]
    end
end
result[current_key] = current_val

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