language-agnostic - 哪种数据结构适合这种情况？

Question

当只需要功能时，我正在尝试决定使用哪种数据结构来存储键值对

• 插入
• 抬头

具体来说，我不需要能够删除对或遍历键/值/对。

键是整数元组，值是指针（引用等）。我只存储了几百万对，分布在（许多）对象上。

目前我正在考虑使用

• 哈希表
• kd树
• b树

我倾向于哈希表（对于O(1)插入/查找时间），但我想确认我的倾向。

您会推荐哪种结构（上述结构或其他结构），为什么？如果您推荐一个哈希表，我应该为每个对象创建一个单独的表，还是只创建一个表并将对象的 id 作为键元组的一部分？

Answer 1

哈希表将是这里的最佳选择，因为对您而言重要的所有操作都是 O(1)（因此您不必担心创建多个哈希表）。

Answer 2

我是哈希表的忠实粉丝，因为它们很简单，并且几乎所有主要语言都有可用的实现。O(1) 插入/查找是一个特别好的特性。

您可能应该使用单个表来节省内存。众所周知，哈希表在内存方面效率低下，使用单个表将有助于将其最小化。

Answer 3

哈希表在这里很有用，我认为没有理由拥有多个表。

Answer 4

大多数树的查找时间为 O(n ln n)，但哈希表的查找时间为 O(1)，所以这是您要使用的。这也很常见，并且通常实现高度优化以启动。