Java Treemap 插入与 HashMap 插入的复杂性

Complexity of Treemap insertion vs HashMap insertion

提问by luckysing_noobster

I am confused with the time complexity of these two algorithms.

我对这两种算法的时间复杂度感到困惑。

//time complexity O(nlog(n))
public void usingTreeMap(){
    Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
    for (int i = 0; i < 10; i++) {
        map.put(i, i);
    }
}
//time complexity O(n)
public void usingHashMap(){
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < 10; i++) {
        map.put(i, i);
    }
}

Is the time complexity to the usingTreeMap algorithm correct.I do know in treemap the insertion time is log(n) but if we iterate over an array of 10 elements does it become nlog(n).

usingTreeMap 算法的时间复杂度是否正确。我知道在树图中插入时间是 log(n)，但是如果我们遍历 10 个元素的数组，它会变成 nlog(n)。

回答by user207421

Is the time complexity to the usingTreeMap algorithm correct.

usingTreeMap 算法的时间复杂度是否正确。

The time complexities of the basic TreeMapoperations are specified correctly in the Javadoc.

TreeMapJavadoc 中正确指定了基本操作的时间复杂度。

I do know in treemap the insertion time is log(n)

我知道在树图中插入时间是 log(n)

Correct.

正确的。

but if we iterate over an array of 10 elements does it become nlog(n).

但是如果我们迭代一个包含 10 个元素的数组，它会变成 nlog(n)。

If this means inserting those 10 elements the time complexity is M*log(N)where Mis the size of the array and Nis the size of the TreeMap.If it doesn't mean that, the question is unclear.

如果该装置插入的那些10种元素的时间复杂度是M*log(N)其中M是阵列的尺寸和N是的大小TreeMap.，如果它并不意味着，问题是不清楚。

回答by Audible

It might not be. (i.e. when 4 elements out of 10 have same key, then N will be 7), so I believe more duplicate keys, better time for the insertion.

可能不是。（即当 10 个元素中有 4 个具有相同的键时，N 将是 7），所以我相信更多的重复键，插入的更好时间。

回答by displayName

Complexity with HashMap

HashMap 的复杂性

In the case of HashMap, the backing store is an array. When you try to insert ten elements, you get the hash, compute the specific array index from that hash, and since it's an array in the back, you inject in O(1).

在 HashMap 的情况下，后备存储是一个数组。当您尝试插入 10 个元素时，您会获得哈希值，从该哈希值计算特定的数组索引，由于它是后面的数组，因此您需要在 O(1) 中注入。

• For first element, time taken to insert = O(1)
• For second element, time taken to insert = O(1)
• .
• .
• For n^thelement, time taken to insert = O(1)

• 对于第一个元素，插入时间 = O(1)
• 对于第二个元素，插入时间 = O(1)
• .
• .
• 对于^第n^个元素，插入所需的时间 = O(1)

So, total time for insertion of n elements in a HashMap = n * O(1) = O(n)

因此，在 HashMap 中插入 n 个元素的总时间 = n * O(1) = O(n)

---

---

Complexity with TreeMap

TreeMap 的复杂性

In this case, the backing store is a Tree. For a tree with total kelements, on an average, the time to find the location is O(Log k).

在这种情况下，后备存储是一棵树。对于一棵共有k 个元素的树，平均而言，找到位置的时间是 O(Log k)。

• Time to insert first element = O(1)
• Time to insert second element = O(Log 1) = 0 = O(1)
• Time to insert third element = O(Log 2)
• .
• .
• Time to insert n^thelement = O(Log (n-1))

• 插入第一个元素的时间 = O(1)
• 插入第二个元素的时间 = O(Log 1) = 0 = O(1)
• 插入第三个元素的时间 = O(Log 2)
• .
• .
• 插入^第n^个元素的时间= O(Log (n-1))

Total time = Log 1 + Log 2 + Log 3 + ... + Log (n-1)

总时间 = Log 1 + Log 2 + Log 3 + ... + Log (n-1)

Now, Log 1 <= Log n, Log 2 <= Log n ... Log (n-1) <= Log n, leading us to n-1 values each of which is less than or equal to Log n.

现在，Log 1 <= Log n，Log 2 <= Log n ... Log (n-1) <= Log n，导致我们得到 n-1 个值，每个值都小于或等于 Log n。

This means that the timing for insertion in a treemap sum to a value <= (n-1) * Log (n-1), leading to the complexity of O(n Log (n)).

这意味着在树图中插入的时间总和为 <= (n-1) * Log (n-1)，导致 O(n Log (n)) 的复杂性。

---

---

_{One of the properties of logs is Log a + Log b = Log (ab). Using that, the insertion time in case of TreeMap sums to a lesser-known running time value of O(Log(n!)). But, since, O(Log(n!)) is bound by O(n Log(n)), the time complexity of insertion of n elements in a TreeMap is loosely written O(n Log(N)).}

_{日志的属性之一是Log a + Log b = Log (ab)。使用它，在 TreeMap 的情况下插入时间总和为 O(Log(n!)) 的鲜为人知的运行时间值。但是，由于O(Log(n!)) 受 O(n Log(n)) 约束，因此在 TreeMap 中插入 n 个元素的时间复杂度被松散地写为 O(n Log(N))。}

回答by Michael Hinds

Insertion time complexity is typically defined on a per instance basis.

插入时间复杂度通常是在每个实例的基础上定义的。

Averagecase:

平均情况：

• HashMap O(1)
• TreeMap O(logn) -- since the underlying structure is a red-black tree

• 哈希映射 O(1)
• TreeMap O(log n) -- 因为底层结构是一棵红黑树

Worstcase:

最坏情况：

• Hashmap O(n) -- in the case of a hashing collision
• TreeMap O(logn)

• Hashmap O( n) -- 在散列冲突的情况下
• 树图 O(log n)

In your code above since you are inserting multiple items, we need to distinguish how many elements are in the maps (n) vs. how many elements are being added to the maps (m). If the maps are initially empty, then your runtime above is correct. If they already have some elements, then the runtimes would be:

在上面的代码中，由于您插入了多个项目，我们需要区分地图中有多少元素 ( n) 与有多少元素被添加到地图 ( m)。如果地图最初是空的，那么上面的运行时是正确的。如果他们已经有一些元素，那么运行时将是：

                                Avg      Worst
Insert m elements into HashMap: O(m)     O(mn)
Inset m elements into TreeMap:  O(mlogn) O(mlogn)