algorithm - 什么是对这些特征进行分组的良好数据结构？什么算法可以用于插入和检索？

Question

我有一个包含 50 个主题的列表。我还有一份 1000 所学校的名单，这些学校将至少教授一门或多门这些科目。每次我搜索一所学校时，我都在考虑将这所学校与其教授的科目缓存起来。以最佳方式保存这些数据的好方法是什么？

Answer 1

我建议您使用哈希表，使用 school 作为键，使用 subjects 作为元素。哈希表的插入、删除和搜索操作可能具有复杂性，具体取决于您处理额外冲突的方式(许多键可以在同一索引中进行哈希处理)。但是在您的问题中，冲突是不可避免的(许多学校共享科目)，例如，使用带有双哈希的开放寻址可以减少额外的冲突，但不会减少问题中的隐式冲突。如果您想自己实现，请使用良好的哈希函数(键在索引上的均匀分布)和一个简单的冲突列表，可以使您在 O(1) 中实现插入，在 O(50) 中实现删除(搜索主题及其删除)并在 O 中搜索(50) 在最坏的情况下，我认为这对问题来说是好的(并且实现起来简单且快速)。更多关于哈希表和如何实现它的信息:https://en.wikipedia.org/wiki/Hash_table