3

size()で呼び出されるメソッドが通常のHashMapConcurrentHashMapのメソッドと同じ複雑さであるかどうか疑問に思います。size()

4

5 に答える 5

9

JDK 8でのConcurrentHashMap.size（）の新しい実装は、 LongAdderからコピーして貼り付けたクールなアルゴリズムを使用しています。

事実上、の複雑さConcurrentHashMap.size()はほぼ一定であり（オタク言語では「O（1）」）、比較した場合のリアルタイムコストHashMap.size()はごくわずかです。私を信じないの？基本的なテストプロジェクトを開いて、自分で実行してください。現在のマシンにJDK7をインストールしていません。Java1.8と比較して、Java1.7の時間コストに関するフィードバックを得るのはすばらしいことです。

于 2014-04-10T18:42:08.773 に答える
5

サイズがフィールドに格納されるため、size()onの複雑さHashMapはです。onO(1)の実装を見ると、それが大きいことがわかります（> O（1））size()ConcurrentHashMap

リファレンス（openjdk-6）

于 2012-05-25T12:48:26.700 に答える
4

そうではありません。私のバージョンのJDKではHashMap.size()複雑O(1)さがありますConcurrentHashMap.size() が、最良の場合はセグメントを反復処理する必要があります。最悪の場合、すべてのセグメントがロックされます。これは、マルチスレッドシナリオではかなりコストのかかる操作になる可能性があります。

もちろん、どちらが速いかはまったく別の問題です。答えは、マップにアクセスしているスレッドの数と、それらが何をしているのかによって大きく異なります。

于 2012-05-25T12:48:21.393 に答える
0

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;
}
于 2012-05-25T12:50:14.513 に答える
0

同時に変更可能な構造でsize（）を呼び出すことは本質的に無意味なことなので、これは無関係な質問です。サイズが何であるかがわかるだけで、ログに記録する以外に、この情報を実際に使用することはできません。

構造をロックせずにsize（）を使用しようとすると、競合状態になります。

于 2012-05-26T10:50:50.850 に答える