英文:
What makes HashMap.containsKey() have a constant time complexity while ArrayList.contains() has a linear time complexity in Java?
问题
In other words, how can Map.containsKey() search without iterating over the elements in proper sequence like List.contains() does, which is what makes List.contains() have a linear time complexity?
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.contains(5); // 线性时间复杂度
Map<Integer, Character> map = new HashMap<>();
map.put(1,'a');
map.put(2,'b');
map.put(3,'c');
map.put(4,'d');
map.put(5,'e');
map.containsKey(5); // 仅常数时间复杂度
英文:
In other words, how can Map.containsKey() search without iterating over the elements in proper sequence like List.contains() does, which is what makes List.contains() have a linear time complexity?
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.contains(5); // Linear Time Complexity
Map<Integer, Character> map = new HashMap<>();
map.put(1,'a');
map.put(2,'b');
map.put(3,'c');
map.put(4,'d');
map.put(5,'e');
map.containsKey(5); // Only Constant Time Complexity
答案1
得分: 1
这仅仅是这些数据结构的结构方式。
更简单的情况是列表。列表基本上是一组对象，它们指向它们的前一个和下一个元素。没有单个列表元素知道其他所有元素的位置，只知道它的邻居。因此，如果您想要确定特定值是否存在，您必须遍历整个列表并读取它们的值。这意味着操作是O(n)，即线性时间。
对于Map，它们通常使用哈希来总结键，并告诉数据结构将键和值放在后备存储中（实际包含键和值的数据结构）。
这的典型示例是一个列表的数组。您可以使用int arrayIndex = hash(key) % backingArray.length创建数组索引。然后，您执行backingArray[arrayIndex].contains(value)。由于两个键具有相同的arrayIndex的可能性较小，因此此contains调用通常在O(1)时间内完成，因为列表只有一个元素，但由于在最坏情况下可能存在多个元素，因此在真正的最坏情况下它实际上是O(n)的时间。
如果哈希函数正确分布键，Map.containsKey只需要O(1)时间。
英文:
This is just how those data structures are, well, structured.
The simpler case is the List. The List is basically a bunch of objects that point to their previous and next elements. No single List element knows where all of the other elements are, just its neighbors. So, if you want to figure out if a specific value is present, you have to go through the entire List and read their values. This means the operation is O(n), or linear, in time.
For a Map, they typically use a hash to summarize a key and to tell the data structure where to put the key and value in the backing storage (the data structure that actually contains the keys and values).
The typical example of this is an array of Lists. You create an array index using int arrayIndex = hash(key) % backingArray.length. Then, you do backingArray[arrayIndex].contains(value). Since it is unlikely for two keys to have the same arrayIndex, this contains call usually happens in O(1) time since the List only has one element, but since it's possible for there to be multiple elements in a worst-case scenario, it's actually O(n) in time for a true worst-case scenario.
Map.containsKey is only O(1) in time if the hashing function properly distributes the keys.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论