像 HashMap 这样的数据结构将根据键的相等性检索数据。
如果我想根据比较结果检索数据，我应该使用什么数据结构？
问问题
361 次
2 回答
1
通常，您应该使用平衡二叉树。在 C++ 中，您可以通过std::map. 在 Java 中，它被称为 TreeMap。可悲的是，Python 在标准库中没有任何内容。
对于不寻常的情况，其他结构（例如 Splay Tree 甚至简单的链表）可能会更好。这仅取决于您的需求。
于 2012-09-18T05:12:15.250 回答
1
正如已经回答的那样，平衡树是好的。
不过，您没有提及任何有关插入速度或内存要求的信息。排序数组的搜索速度也很快（二分搜索），但插入速度很慢。
我假设正在谈论使用字符串进行索引。最快的查找是字典（在我的基准测试中，是 C++ 映射的两倍），但它的存储量很大。
使用字典，每个节点都有一个指针数组（指向节点）：每个可能的字符串字符都有一个指针。要插入，您遍历字符串中的每个字符，并为该字符添加一个节点（如果尚不存在），遍历该节点并继续，直到您位于字符串的末尾。然后，您将数据存储在该节点上。这个数据结构还有一个额外的好处，就是当你有一个部分完成的键时，你可以选择构建单词完成列表。
于 2012-09-18T05:24:43.977 回答