java - TreeMap 中的二分查找

Question

我有两个 TreeMap

第一张 map 是:

Map<String, Double> m1 = new TreeMap();

第二个是:

Map<String,double []> m2 = new TreeMap();

我想在第一个映射中搜索第二个映射中的键，然后将第一个映射的值乘以第二个映射值的列表(对于相似的键)。

下面的代码对我来说效果很好，但是当TreeMaps很大时，搜索需要更多时间，我想提高速度，我该如何进行二分搜索。另一个问题，最快的搜索方法是 TreeMap 还是 HashMap？

double[] finalSum = new double[N];

for ( Map.Entry<String,Double> entry : m1.entrySet() ) {
     if ( m2.containsKey(entry.getKey()) ) {
         //if the key is common in map1 and map2, compare the values
         double y=entry.getValue();
         double j[]=m2.get(entry.getKey());
         for (int u=0;u<j.length;u++){
             finalSum[u] += y * j[u];
         }}}

提前致谢:)

Answer 1

HashMap 和 TreeMap 的 Big-O 表示法:

                     get      containsKey next     Notes
HashMap               O(1)     O(1)        O(h/n)   h is the table capacity
TreeMap               O(log n) O(log n)    O(log n) 
ConcurrentHashMap     O(1)     O(1)        O(h/n)   h is the table capacity 

如果您想要从 TreeMap 中检索其值的键已知。我建议宁愿使用 HashMap，因为 Hashmap 的 Big-O 是 O(1) 来获取元素，与 TreeMap 相比，它是 O(log n)。

I want to search the Key in first map to the second one, and then multiply the value of the first map to the list of second map values (for the similar keys).

通过使用 HashMap，您可以使用键从两个 HashMap 中检索值，并返回第一个值与第二个 hashMap 中的值的乘积。