동시 해시 맵 크기() 메서드의 복잡성

Question

ConcurrentHashMap에서 호출 된 size() 메서드가 일반적인 HashMap의 size() 메서드와 동일한 복잡성을 갖고 있는지 궁금합니다.

Answer 1

아니요. 내 버전의 JDK에서 HashMap.size()은 O(1) 복잡도를 가지고있는 반면, ConcurrentHashMap.size()인 경우는 세그먼트를 반복해야합니다. 최악의 경우 모든 세그먼트를 잠글 것이므로 다중 스레드 시나리오에서 상당히 비싼 작업이 될 수 있습니다.

물론 이 더 빠릅니다.은 전혀 다른 질문입니다. 대답은 주로 얼마나 많은 스레드가 맵에 액세스하고 있는지, 정확히 무엇을하는지에 따라 달라집니다.

Answer 2

size()의 HashMap은 크기가 필드에 저장되어 있기 때문에 O(1)입니다. 우리가 ConcurrentHashMap에 size()의 구현을 보면, 우리는 더 큰 것을 참조 (> O (1))

참조 (오픈 JDK-6)

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

Answer 3

ConcurrentHashMap에서 size() 메소드의 복잡도는 본질적으로 O (N) 조작입니다 (세그먼트 수와 주로 다름). 요. 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

동시에 변경할 수있는 구조체에서 size()를 호출하는 것이 본질적으로 무의미한 문제이므로 관련성이없는 질문입니다. 크기가 이고 크기가 인 모든 정보는 사용자에게 알려주며 실제로이 정보를 기록하지 않고는 아무 것도 할 수 없습니다.

구조를 잠그지 않고 size()를 사용하려고하면 경쟁 조건이 발생합니다.

Answer 5

에서 ConcurrentHashMap.size()의 새로운 구현 JDK 8들이 친절의 LongAdder에서 붙여 복사 멋진 알고리즘을 사용합니다.

실질적으로 ConcurrentHashMap.size()의 복잡도는 거의 동일하며 (괴상한 언어에서는 "O (1)") HashMap.size()과 비교하여 실시간 비용은 무시해도 좋습니다. 날 믿지 않니? 내 기본 test project을 열고 직접 실행하십시오. 현재 머신에 JDK 7이 설치되어 있지 않아 Java 1.8과 비교하여 Java 1.7에서 시간 비용에 대한 의견을 얻는 것이 좋습니다.