algorithm - 一组给定操作的最佳数据结构 - 添加、检索最小值/最大值和检索特定对象

Question

我正在寻找支持以下操作的最佳(时间和空间)最佳数据结构:

1. 将人员(姓名、年龄)添加到人员的全局数据存储中
2. 获取最小和最大年龄的人
3. 根据姓名搜索人员的年龄

这是我能想到的:

• 保留一个Persons数组，当要添加一个新Person时，继续添加到数组末尾
• 保留人名与年龄的哈希值，以帮助获取具有给定姓名的人的年龄
• 为具有最小和最大年龄的人维护两个对象 minPerson 和 maxPerson。如果需要，在添加新人员时更新此项。

现在，虽然我为了更好地执行 (3) 而保留一个散列，但我认为如果散列中有很多冲突，这可能不是最好的方法。此外，添加一个 Person 将意味着添加到哈希的开销。

这里有什么可以进一步优化的吗？

注意:我正在寻找最好的(平衡的)方法来在最少的时间和空间内支持所有这些操作。

Answer 1

您可以去掉数组，因为它没有提供其他两个结构不能做的任何事情。

否则，哈希表 + 最小值/最大值可能对您的用例表现良好。事实上，这正是我要使用的。

至于摆脱哈希表，因为糟糕的哈希函数可能会导致冲突:好吧，不要使用糟糕的哈希函数。我敢打赌，您选择的编程语言提供的默认字符串哈希函数开箱即用。