如果我必须知道键才能在散列图中获取值(时间复杂度为 O(1)),为什么它与在知道索引(也为 O(1))的情况下获取数组中的值有什么不同)?
换句话说,hashmap 被认为具有 O(1) 的查找复杂度,但这是因为 key 是已知的。当索引已知时,这与数组相同——如果我不知道索引,它将是 O(n),这与不知道键相同,然后对于 hashmap 也是 O(n) (包含值(对象值)方法)。
因此,我不明白为什么 hashmap 被认为对查找更有效。
最佳答案
我认为理解这一点的一个好方法是使用实际用例。假设您要存储学生姓名和他的分数。
所以有2个字段。
String name
Integer marks
现在您想根据学生姓名查找分数。
在数组方式中,您将创建一个包含信息并将它们放入数组中的类。
现在要检查学生姓名的标记,您需要迭代整个数组,或者您需要知道特定姓名存储在哪个索引处。这两个都是 O(N) 复杂度。
或者您可以将其存储在 map 中,键为 name,值为 marks。您可以在 O(1) 复杂度中按名称查找 map 。
TL;DR; 您需要查看您的用例,然后决定是否可以使用数组(基于有序索引的查找)或者您实际上需要一个 Map 来进行查找。
关于java - HashMap 和数组在查找时间复杂度上的区别,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57279745/