我希望创建一个库，用户需要执行的功能之一是存储和检索数据以及索引。我不知道他们会做更多的事情：插入、阅读/写作、删除或随机搜索。
您将使用哪种数据结构才能获得最佳性能？您建议的数据结构在每种情况下如何比较性能？
思考哈希表还是 avl 树？还是类似数据结构的组合？数组链表？
如果它自我优化，那么它会看到用户正在执行更多的插入或读取或随机搜索，因此未来的插入会为此进行优化，那将是很酷的。
没有一个最好的数据结构可以做到这一点，否则我保证每个人都会使用它。但是，有几个非常合理的选择可用。
要考虑的第一个问题是您需要如何处理数据？如果您只是存储项目并在以后查找它们，并且您需要做的就是添加、删除和查找项目，那么您可能希望更多地关注各种风格的哈希表。另一方面，如果您正在寻找按排序顺序处理项目的能力，那么哈希表可能已经淘汰，您可能应该更多地关注平衡树。
下一个问题是您要存储的数据类型。如果每个项目都有一些关联的键，它是哪种键？哈希表和 BST 通常都很棒，但也存在更专门的数据结构，专门用于字符串键(tryes(和其他类型的整数。
从那里你应该考虑你存储了多少数据。如果您存储几百兆字节并且东西可以舒适地放入RAM，则可能不需要在这里做任何特殊的事情。但是，如果您拥有大量数据并且某些内容不适合RAM，则需要研究外部数据结构，例如B树。
另一个需要考虑的问题是您想要什么样的性能保证。随着项目数量的增加，大多数哈希表都需要某种动态调整大小，这可能会导致不频繁但昂贵的重建操作，从而减慢速度。如果您绝对需要实时性能，这将对您不起作用。如果你对此感到满意，那就去做吧！
假设你已经把范围缩小到"哈希表"或"平衡的BST"。现在您必须选择要使用的类型！对于哈希表，线性探测哈希表或链式哈希等简单结构通常需要进行一些性能调整才能实现最大效率。在某些情况下，像布谷鸟哈希这样的新方法可以提供更好的内存性能，而像谷歌的flat_hash_map这样的工程方法则针对x86架构进行了极大的优化。对于 BST，如果你的查找比插入或删除多得多，你可能想要像 AVL 树这样的东西，因为 AVL 树的高度很低，但如果插入和删除更常见，你可能也想查看红/黑树，如果你真的有很多删除，也许可以查看更现代的树，如 RAVL 或 WAVL 树。
所有这些都是说答案是"视情况而定"。您对特定应用程序的了解越多，您就能选择更好的数据结构。而且，可悲的是，没有一个数据结构来统治它们。:-)