并发hashmap大小（）方法复杂度

Question

我想知道ConcurrentHashMap上调用的size()方法是否与通常的HashMap的size()方法具有相同的复杂度。

Answer 1

它不是。在我的版本的JDK，HashMap.size()有O(1)的复杂性，而ConcurrentHashMap.size()在最好的情况下有遍历段。在最糟糕的情况下，它会锁定所有细分市场，在多线程场景中这可能是一项非常昂贵的操作。

当然，这是更快的的是一个不同的问题完全。答案在很大程度上取决于有多少线程访问地图，以及他们正在做什么。

Answer 2

size()的上HashMap的复杂性是O(1)，由于尺寸被存储在字段。如果我们看一下size()上ConcurrentHashMap实施，我们看到，这是更大（> O（1））

参考（OpenJDK的-6）

• HashMap#size()
• ConcurrentHashMap#size()

Answer 3

中的ConcurrentHashMap大小（）方法的复杂性本质上是一个O（N）的操作（主要是改变与段的数量），其可以在故见urce。 HashMap是一个O（1）操作。

/** 
* Returns the number of key-value mappings in this map. If the 
* map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns 
* <tt>Integer.MAX_VALUE</tt>. 
* 
* @return the number of key-value mappings in this map 
*/ 
public int size() { 
    final Segment<K,V>[] segments = this.segments; 
    long sum = 0; 
    long check = 0; 
    int[] mc = new int[segments.length]; 
    // Try a few times to get accurate count. On failure due to 
    // continuous async changes in table, resort to locking. 
    for (int k = 0; k < RETRIES_BEFORE_LOCK; ++k) { 
     check = 0; 
     sum = 0; 
     int mcsum = 0; 
     for (int i = 0; i < segments.length; ++i) { 
      sum += segments[i].count; 
      mcsum += mc[i] = segments[i].modCount; 
     } 
     if (mcsum != 0) { 
      for (int i = 0; i < segments.length; ++i) { 
       check += segments[i].count; 
       if (mc[i] != segments[i].modCount) { 
        check = -1; // force retry 
        break; 
       } 
      } 
     } 
     if (check == sum) 
      break; 
    } 
    if (check != sum) { // Resort to locking all segments 
     sum = 0; 
     for (int i = 0; i < segments.length; ++i) 
      segments[i].lock(); 
     for (int i = 0; i < segments.length; ++i) 
      sum += segments[i].count; 
     for (int i = 0; i < segments.length; ++i) 
      segments[i].unlock(); 
    } 
    if (sum > Integer.MAX_VALUE) 
     return Integer.MAX_VALUE; 
    else 
     return (int)sum; 
} 

Answer 4

这是因为在同时可变结构调用大小（）本质上是一个毫无意义的事情做一个不相干的问题。所有它会告诉你的是的大小是，除了可能记录它之外，你实际上不能对这些信息做任何事情。

如果你尝试和使用大小（）没有锁定，您将有竞争条件的结构。

Answer 5

在JDK 8新实现的ConcurrentHashMap.size()使用冷却算法他们那种从复制粘贴LongAdder。

实际上，ConcurrentHashMap.size()的复杂度几乎是恒定的（nerd语言中的“O（1）”），并且与HashMap.size()相比的实时成本可以忽略不计。不要相信我？打开我的基本test project并自己跑步。我目前的机器上没有安装JDK 7，与Java 1.8相比，使用Java 1.7获得关于时间成本的反馈会很酷。