哪种数据结构适合这种情况？
功能时，我试图决定使用哪种数据结构来存储键值
- 当只需要插入
- 查找
对具体来说，我不需要能够删除对，或迭代键/值/对。
键是整数元组，值是指针（引用，等等）。我只存储了分布在（许多）对象上的几百万对。
目前，我正在考虑使用
- 哈希表、
- kd 树
- 、b 树
，我倾向于使用哈希表（对于 O(1) 插入/查找时间），但我想确认我的倾向。
您会推荐哪种结构（上述结构或其他结构）？为什么？如果您推荐哈希表，我应该为每个对象创建一个单独的表，还是只创建一个表并使用对象的 id 作为键元组的一部分？
I'm trying to decide which datastructure to use to store key-value pairs when only features needed are
- insertion
- lookup
Specifically, I don't need to be able to delete pairs, or iterate through keys/values/pairs.
The keys are integer tuples, the values are pointers (references, whatever). I'm only storing a couple million pairs spread out over (many) objects.
Currently I'm considering using either
- a hash table
- a kd-tree
- a b-tree
I'm leaning toward the hash table (for the O(1) insertion/lookup time), but I wanted to confirm my leanings.
Which structure (of those above or other) would you recommend and why? If you would recommend a hash table, should I create a separate table for each object, or just create a single table and use the object's id as part of the key tuple?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
哈希表将是这里的最佳选择，因为对您来说重要的所有操作都是 O(1) （因此您不需要担心创建多个哈希表）。
A hashtable will be the best choice here as all the operations that matter to you are O(1) (and as such you shouldn't need to worry about creating multiple hashtables).
我是哈希表的忠实粉丝，因为它们很简单，并且几乎每种主要语言都有可用的实现。 O(1) 插入/查找是一个特别好的功能。
您可能应该使用单个表，以节省内存。众所周知，哈希表在内存方面效率低下，使用单个表将有助于最大限度地减少这种情况。
I'm a big fan of hash tables, since they are easy and there are implementations available for pretty much every major language out there. The O(1) insertion/lookup is an especially good feature.
You should probably use a single table, to save on memory. Hash tables are notoriously inefficient memory-wise, and using a single table would help to minimize that.
哈希表在这里很有用，我认为没有理由拥有多个表。
Hash tables would be usefull here and I see no reason to have more than one table.
大多数树的查找时间为 O(n ln n)，但哈希表的查找时间为 O(1)，所以这就是您要使用的查找时间。这也很常见，并且通常对启动进行了高度优化。
Most trees have an O(n ln n) lookup time, but hashtables have an O(1) lookup time, so that's the one you want to use. It's also very common, and often the implementation is highly-optimised to boot.