我正在尝试决定下面使用哪种数据结构。
假设我有1000万个键，这些键包含指向包含某些数据的唯一对象的指针。
键是UUID，将它们视为16字节的二进制数组。UUID是使用高质量的随机数生成器生成的。
我一直在考虑以下问题，但我想知道在速度和内存消耗方面每种方法的优缺点。一些公平的估计，在64位平台上的最佳/最差/平均情况会很好。
我需要能够插入几乎不受限制的项目。
二叉树哈希表基数树(bit - based或2bit multi-way)
我需要的操作是:插入，删除，搜索
我喜欢基数树的想法，但它被证明是最难实现的，我还没有找到一个合适的实现，我可以纳入一个商业产品。
- 你不关心排序
- 您的密钥已经是随机的
- 1000万件
简答
哈希表可能最适合你的情况。
如果哈希是常量，哈希表(std::unordered_map)将是O(1)。在您的情况下，O(1)成立，因为您甚至不需要散列—只使用随机UUID的较低32位应该就足够了。查找的成本将类似于一个或两个指针间接指向。
二树(std::map)将是O(log2n)，因此对于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年mdash; 153 mib。
基数树每个元素有1个指针，每个空槽有1个指针。不幸的是，我认为如此大的随机键将导致您在树的边缘有非常多的空槽，因此它可能比上述任何一种都使用更多的内存。减小k可以降低这个开销，但同样会降低性能。
如果最小开销很重要，使用哈希表或二叉树。如果是优先级，则使用完整哈希表。
注意，std::unordered_map不允许您控制何时将调整大小，因此获得一个完整的将是困难的。Boost侵扰有一个非常好的unordered_map实现，可以让你直接控制它和许多其他东西。
我会先尝试std::map或std::unordered_map。
多年来，有许多聪明的人在开发和改进它们。
有什么理由不能使用std::map或std::unordered_map吗?
我只是做了一个快速计算，我认为你可能与标准树。1000万个密钥是一个合理的数字。用一个深度只有23个节点的平衡树来检查。对于基数树，你实际上有128位的密钥长度来检查。
您的密钥也可以非常便宜地表示和比较。使用两个64位值的元组(boost或0x)来获得相同的128位密钥。元组排序足以在映射中使用。因此，复制密钥很便宜，比较也很便宜。对于基数深度搜索，按原样比较整数可能比进行掩蔽和基于位的比较更便宜。
所以在这种情况下，映射很可能工作得很好。
*我在这里避免使用unordered_map，因为uid往往是结构化数据。这意味着标准哈希过程(用于哈希映射)的性能很容易很差。*
由于您使用的是随机uuid，散列可能很好——尽管如此大的散列表需要大量的内存开销来保持效率。
此外，给定完全随机的uuid，基数可能最终具有与树相同的平衡(因为键分布完全均匀)。因此，您可能不会节省甚至步骤，并且仍然会产生位操作的开销。但是有很多方法可以专门化和优化基数树，所以很难确定它是更快，还是总是更慢。
IMO基数树并不难实现。然而，一个简单的哈希表就足够了。只需分配2^16个对象列表的数组，并使用UUID的前2个字节来索引要插入对象的列表。然后你就可以搜索大约160个项目的列表了。
或者，分配一个包含20M指针的数组。要存储对象，只需在0-20M范围内对UUID进行哈希，找到第一个空闲(NULL)指针并将其存储在那里。搜索意味着从哈希值走到第一个NULL值。删除也很简单....try read http://en.wikipedia.org/wiki/Hash_function