Mat*_*att 2 c++ binary-tree hashtable data-structures radix-tree
我正在尝试决定使用哪种数据结构.
假设我有1000万个键,其中包含指向包含某些数据的唯一对象的指针.
密钥是UUID将它们视为16字节二进制数组.UUID是使用高质量的随机数生成器生成的.
我一直在考虑以下内容,但想知道速度和内存消耗方面的优缺点是什么.一些公平的估计,64位平台上的最佳/最差/平均情况会很好.
我需要能够插入几乎无限的项目.
二叉树哈希表基数树(基于位或2位多路)
我需要的操作是:插入,删除,搜索
我喜欢基数树的想法,但它被证明是最难实现的,我没有找到一个合适的实现,我可以将其纳入商业产品.
简短的回答
哈希表可能是最适合您的情况.
速度
如果散列是常量,则散列表(std::unordered_map)将为O(1).在你的情况下,O(1)成立,因为你甚至不需要哈希 - 只需使用随机UUID的低32位应该足够好.查找的成本将类似于一个或两个指针间接.
二叉树(std::map)将为O(log 2 n),因此对于1000万个项目,您将进行24次比较和24次潜在的缓存未命中.即使对于n = 4,000,它也会使用12次比较,因此很快就会变得比哈希表差得多.
基数树将为O(k),因此您将有最多k个比较和k个潜在的高速缓存未命中.在极不可能的最佳情况下,基数树将与哈希表一样快.更糟糕的是(假设k =有点合理的16,对于256路树),它的性能优于二叉树,但远比哈希表差.
因此,如果速度是最重要的,请使用哈希表.
高架
如果已满,则每个项目的典型哈希表将有大约1-3个开销指针.如果不满,你可能每个空槽浪费1个空格指针.你应该能够保持它几乎满,同时仍然比二叉树快,因为你有一个非常随机的键,但为了最大可能的速度,你当然希望给它足够的余量.对于32位计算机上的1000万个项目,预计全表的开销为38-114MiB.对于半满表,预计76-153MiB.
红黑树是最常见的std::map实现,每个项目有3个指针+ 1个bool.一些实现利用指针对齐来将bool与其中一个指针合并.根据实现以及哈希表的完整程度,红黑树的开销可能略低.预计114-153MiB.
基数树每个项目有1个指针,每个空槽有1个指针.不幸的是,我认为这么大的随机密钥会让你在树的边缘有很多空插槽,所以它可能会比上面的任何一个使用更多的内存.减少k可以降低这种开销,但同样会降低性能.
如果最小开销很重要,请使用哈希表或二叉树.如果是优先级,请使用完整哈希表.
请注意,std::unordered_map它不会让您控制何时调整大小,因此获得一个完整将很困难. Boost Intrusive有一个非常好的unordered_map实现,可以让你直接控制它和许多其他东西.