我正在寻找可能利用我用例的特定标准的关联数据结构的输入。
目前我正在使用红/黑树来实现将键映射到值(在我的例子中是整数到地址)的字典。
在我的用例中，元素的最大数量是预先知道的 (1024)，我只会插入和搜索。搜索发生的频率是插入的 20 倍。在过程结束时，我清除结构并再次重复。在使用期间不能有分配——只有最初的预先分配。不幸的是，STL 和最新版本的 C++ 不可用。
有什么见解吗？
最佳答案
我最终从一个例子中实现了一个简单的线性探测 HashTable here .我用了MurmurHash3哈希函数，因为我的数据是随机的。
我通过以下方式修改了哈希表:
- 大小是一个模板参数。在内部，尺寸增加了一倍。实现需要 2 次方大小，传统上调整大小为 75% 占用。因为我知道我要填满哈希表，所以我先发制人地将它的容量加倍以保持它足够稀疏。当添加少量对象时，这可能效率较低，但一旦容量开始填满，效率会更高。由于我无法调整它的大小，所以我选择开始时将它的大小加倍。
- 我不允许存储值为零的键。这对我的应用程序来说没问题，而且它使代码保持简单。
- 所有调整大小和删除操作都已删除，取而代之的是执行内存集的单个清除操作。
- 我选择内联插入和查找函数，因为它们非常小。
它比我之前的红/黑树实现更快。我可能要做的唯一更改是重新访问散列方案，看看源 key 中是否有有助于制作更便宜的散列的内容。
Billy ONeal 建议，给定少量元素 (1024)，在固定数组中进行简单的线性搜索会更快。我听从了他的建议并实现了一个并排比较。在我的目标硬件(大约是第一代 iPhone)上，哈希表的性能优于线性搜索，比例为二比一。在较小的尺寸(256 个元素)下，哈希表仍然更胜一筹。当然，这些值取决于硬件。缓存行大小和内存访问速度在我的环境中很糟糕。然而，其他寻求此问题解决方案的人最好听从他的建议并首先尝试分析它。
关于c++ - 高效的数据结构，通过查找和插入将整数映射到整数，无分配和固定上限，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27070713/