jam*_*o00 1 c++ algorithm hash hashtable data-structures
我有类型的ID值unsigned int.我需要在恒定时间内将Id映射到指针.
主要分布:
ID的值范围为0到uint_max.大多数密钥将聚集到一个组中,但会有异常值.
执行:
我想过使用C++ ext hash_map的东西,但我听说当密钥具有巨大的潜在范围时,它们的性能不会太差.
我还想过使用某种形式的链式查找(相当于递归地将范围细分为C chucks).如果范围中没有键,则该范围将指向NULL.
N =键范围
等级0(分为C = 16,所以16件)= [0,N/16),[N/16,2*(N/16)),...
1级(分为C = 16,所以16*16件)= ...
是否有其他人对如何更有效地实施此映射有想法？
更新:
通过常量,我只是意味着每个键查找不会受到项中值的显着影响.我并不是说它必须是一个单一的操作.
GMa*_*ckG 11
使用哈希映射(unordered_map).这给出了~O(1)查找时间.你"听到"它很糟糕,但你是否尝试过,测试它,并确定它是一个问题？如果没有,请使用哈希映射.
在代码接近完成后,对其进行概要分析并确定查找时间是否是程序缓慢的主要原因.机会是,它不会.