2

単語とそれに対応する整数インデックスをハッシュマップに保存する必要があります。ハッシュマップは同時に更新されます。

例： ハッシュマップには次のキーと値のペアが含まれますwordList。{a,b,c,a,d,e,a,d,e,b}

a:1
b:2
c:3
d:4
e:5

このためのコードは次のとおりです。

public class Dictionary {

private ConcurrentMap<String, Integer>  wordToIndex;
private AtomicInteger                   maxIndex;

public Dictionary( int startFrom ) {
    wordToIndex = new ConcurrentHashMap<String, Integer>();
    this.maxIndex = new AtomicInteger(startFrom);
}


public void insertAndComputeIndices( List<String> words ) {

    Integer index;
    //iterate over the list of words
    for ( String word : words ) {
        // check if the word exists in the Map
        // if it does not exist, increment the maxIndex and put it in the
        // Map if it is still absent
        // set the maxIndex to the newly inserted index

        if (!wordToIndex.containsKey(word)) {
            index = maxIndex.incrementAndGet();

            index = wordToIndex.putIfAbsent(word, index);
            if (index != null)
                maxIndex.set(index);
        }
    }
}

私の質問は、上記のクラスがスレッドセーフかどうかです。基本的に、この場合の不可分操作は、をインクリメントしmaxIndex、単語がない場合はハッシュマップに単語を配置することです。

この状況で並行性を実現するためのより良い方法はありますか？

4

4 に答える 4

3

いいえそうではありません。2つのメソッドAとBがあり、どちらもスレッドセーフです。もちろん、スレッドが関数呼び出しの間に別のメソッドを中断する可能性があるため、シーケンスでAとBを呼び出すこともスレッドセーフであることを意味するわけではありません。これがここで起こることです：

    if (!wordToIndex.containsKey(word)) {
        index = maxIndex.incrementAndGet();

        index = wordToIndex.putIfAbsent(word, index);
        if (index != null)
            maxIndex.set(index);
    }

スレッドAは、wordToIndexに「dog」という単語が含まれていないことを確認し、if内で続行します。スレッドBは、「dog」という単語を追加する前に、「dog」がマップにないこと（Aはまだ追加していない）を検出するため、if内でも続行します。これで、「犬」という単語を2回挿入しようとしています。

もちろん、putIfAbsentは1つのスレッドだけがそれを追加できることを保証しますが、あなたの目標は2つのスレッドが同じキーで同時にifに入らないようにすることだと思います。

于 2011-11-21T17:04:18.307 に答える
3

明らかに、別のスレッドがmaxIndexインクリメントしてからクロバリングされるのを見ることができます。

これがマップで行われているすべてであると仮定すると（特に、削除なし）、単語をマップに入れて、それが成功した場合にのみインクリメントしてみることができます。

    Integer oldIndex = wordToIndex.putIfAbsent(word, -1);
    if (oldIndex == null) {
        wordToIndex.put(word, maxIndex.incrementAndGet());
    }

（または、単一putの場合は、の代わりにある種の可変タイプを使用しますInteger。）

于 2011-11-21T17:11:44.330 に答える
0

AtomicIntegerは、使用を検討する必要があるものです。

transactionそして、synchronized(this)ブロック内で発生する必要があるすべてのコードをラップする必要があります。

于 2011-11-21T17:19:31.290 に答える
0

他の答えは正しいです---あなたのクラスにはスレッドセーフではないフィールドがあります。まず、あなたがすべきことは、

スレッドを実装する方法

1）スレッドセーフコードの要件ではありませんが、内部のすべてがプライベートであることを確認します。

2）アクセサメソッドのいずれかを見つけ、グローバルオブジェクトの状態が変更されるたびに（または少なくともIFブロックが同期されている場合）それらが同期されていることを確認します。

3）デッドロックまたは不良カウントをテストします。これは、10000のねじ山挿入後にmaxIndexの値が正しいことを確認することにより、単体テストで実装できます。

于 2011-11-21T17:25:13.343 に答える