Car*_*los 5 lookup performance hashtable avl-tree data-structures
我有x(百万)正整数,其值可以与允许的值一样大(+2,147,483,647).假设它们是唯一的,那么将它们存储为查找密集型程序的最佳方法是什么.
到目前为止,我想到了使用二进制AVL树或哈希表,其中整数是映射数据(名称)的关键.但是我不确定我是否可以使用哈希表来实现如此大的密钥(除了容易发生冲突之外,还不会产生> 0.8的加载因子吗？)
我可以得到一些关于哪种数据结构可能适合我的情况的建议
结构的选择在很大程度上取决于您可用的内存量.我假设你根据描述你需要查找但不要循环它们,找到最近的或其他类似的操作.
Best可能是一个分段哈希表.通过将哈希冲突进入桶,并保持独立的数组在桶键和值,你既可以减少表合适的大小和搜索桶时占用CPU缓存加速的优势.桶内的线性搜索甚至可能比二进制搜索更快!
AVL树是只读被读取密集型而不是数据集漂亮,并要求下令枚举,找到最近的和类似的操作,但他们工作的烦人量的正确实施.你可以用B树,因为CPU缓存行为获得更好的性能,不过,特别是高速缓存无视B树算法.