TreeMap 中的二进制搜索

Question

我有两个 TreeMap

第一张地图是：

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 的大 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

如果您要从树图中检索值的键已知。我建议宁愿使用 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 中检索值，并且 return 第一个值与第二个 hashMap 中的值相乘。

TreeMap 中的二进制搜索

binary search in the TreeMap

java

search

hashmap

binary-search

binary-search-tree