Javaの文字列の内部表現の変更

エントリー

これは私の最初の記事の翻訳です。 奇妙なことに、Javaに専念することにしました。 この記事では、Javaで発生した文字列データ型の変更について説明します。



重要：17の更新では、Java 7はまだ記事について何も変更していません。

文字の文字配列の分割[]

Stringクラスの現在の実装には、4つのインスタンスフィールドがあります。文字列文字を含む文字のchar []値配列、intオフセットは値配列で使用される最初の文字のインデックス、int countは使用される文字数、int hashはこの文字列の計算されたハッシュコードのキャッシュされた値です。 ご覧のとおり、ほとんどの場合、文字列の値はoffset = 0およびcount = value.lengthになります。 このルールの唯一の例外は、viaString.substringメソッドまたはこのメソッドを使用するメソッド（splitなど）を呼び出して文字列を作成する場合に可能です。



String.substringは、文字のchar []内部配列を元の文字列と共有する文字列を作成します。

1. 一緒に使用してメモリを節約します。
2. String.substringメソッドの実行時間を一定にします（O（1））。

同時に、このような実装では、メモリリークが発生する可能性があります。大きな文字列から小さな部分文字列を抽出し、大きな文字列が不要になった場合でも、元の文字列の大きな文字配列へのリンクがあります。 これを回避する唯一の方法は、コンストラクターnew String（String）を呼び出すことです。これにより、文字の配列のコピーを強制的に作成します。つまり、小さな「親」から小さな文字列を切断します。



Java 1.7.0_06では、オフセットフィールドとカウントフィールドがStringクラスから削除されました。 これは、文字の配列を共有できなくなったことを意味します。 これで、上記のメモリリークを忘れて、新しいString（String）コンストラクターを再び使用することはできなくなります。 欠点として、String.substringメソッドは、以前の定数とは対照的に線形の複雑さを持つようになったことを常に覚えておく必要があります。

ハッシュロジックの変更

同じ更新でStringクラスに導入された別の変更：新しいハッシュアルゴリズム。 オラクルによると、新しいアルゴリズムはハッシュコードのより良い分布を提供し、ハッシュベースのコレクション（HashMap、Hashtable、HashSet、LinkedHashSet、WeakHashMap、ConcurentHashMap）のパフォーマンスを改善するはずです。 記事の冒頭で説明した変更とは異なり、これらの変更は実験的なものであり、デフォルトではオフになっています。



お気づきかもしれませんが、これらの変更は、コレクションキーが文字列である場合にのみ当てはまります。 これらの変更を有効にするには、システムプロパティjdk.map.althashing.thresholdの値を負でない値に設定する必要があります（デフォルトでは-1です）。 この値は、コレクションのサイズのしきい値であり、その後、新しいハッシュアルゴリズムが使用されます。 小さな修正：ハッシュアルゴリズムは、十分なメモリがない場合にのみ変更されます。 コレクションがサイズ= 160およびjdk.map.althashing.threshold = 200で再配布された場合、コレクションサイズが320に増加した場合にのみハッシュ方法が変更されます。



Stringクラスにはhash32（）メソッドがあり、その結果はint hash32フィールドにキャッシュされます。 同じ文字列に対するhash32（）メソッドの結果は、JVMの起動によって異なる場合があります（実際、System.currentTimeMillis（）とSystem.nanoTimeの2つの呼び出しを初期化に使用するため、実際にはほとんど異なります）。 その結果、同じコレクションに対する反復は、プログラムの起動ごとに異なる場合があります。 実際、私はこの方法に少し驚いた。 hashCodeメソッドの実際の実装が十分に機能する場合、なぜ必要なのでしょうか？ hash32（）メソッドを使用して取得される衝突の数を確認することにしました。 String.hash32（）メソッドはパブリックではありませんが、HashMapクラスの実装を見て、それを呼び出す方法を決定しました。 回答：sun.misc.Hashing.stringHash32（文字列）。 100万行を含むテストでは、String.hashCodeメソッドを使用した複数の衝突と比較して、メソッドは304の衝突を返しました。 私たちはさらなる改善を待つべきだと思います。

新しいハッシュロジックは、マルチスレッドコードに深刻な影響を与える可能性があります

Oracleは、HashMap、Hashtable、HashSet、LinkedHashSet、WeakHashMapの各クラスでハッシュを実装するときにミスを犯しました。 ConcurentHashMapのみにこのエラーは含まれません。 問題は、すべての非並列クラスにフィールドがあることです：

/** *            . */ transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは、上記のコレクションを作成するたびに、sun.misc.Hashing.randomHashSeedメソッドが呼び出されることを意味します。 次に、randomHashSeedメソッドはjava.util.Random.nextIntメソッドを呼び出します。 ご存じのように、Randomクラスはマルチスレッドにあまり適していません。プライベートクラスのAtomicLongシードフィールドが含まれています。 アトミックは平均的な負荷の下ではうまく機能しますが、重い負荷の下では不十分です。



その結果、ほとんどすべての既知のパーサー（パーサー）が影響を受けるクラスの少なくとも1つを使用するため、HTTP / JSON / XMLを処理する多くの負荷の高いWebアプリケーションがこのエラーの影響を受ける可能性があります。 これらのパーサーはすべて、ネストされたマップコレクションを作成できます。これにより、毎秒作成されるマップコレクションの数が増えます。

この問題を解決するには？

1. ConcurrentHashMapパス：システムプロパティjdk.map.althashing.thresholdが定義されている場合にのみrandomHashSeedメソッドを呼び出します。 ただし、これはJDKカーネル開発者のみが利用できます。

 /** *            . */ private transient final int hashSeed = randomHashSeed(this); private static int randomHashSeed(ConcurrentHashMap instance) { if (sun.misc.VM.isBooted() && Holder.ALTERNATIVE_HASHING) { return sun.misc.Hashing.randomHashSeed(instance); } return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

2.ハッカーの方法：クラスsun.misc.Hashingを変更します。 非常にがっかりしました。 それでもこれを行うことにした場合は、これを行うことができます。java.util.Randomクラスはfinalではありません。 たとえば、定数値を返すことにより、それを展開してnextIntメソッドをオーバーライドできます。 次に、Randomから継承したクラスに設定して、フィールドsun.misc.Hashing.Holder.SEED_MAKERを変更する必要があります。 このフィールドがプライベートで静的であり、最終的なものであることを心配しないでください-リフレクションが役立ちます。

まとめ

• Java 1.7.0_06以降、String.substringメソッドは、作成する文字列ごとに常にchar []文字の新しい配列を作成します。 これは、このメソッドが以前のバージョンのように定数と比較して線形の複雑さを持つことを意味します。 この変更の結果、文字列は以前よりも4バイト少なくなり、String.substringメソッドに起因するメモリリークが確実に排除されます。
• 同じ更新から開始して、hash32と呼ばれるハッシュの2番目のメソッドがStringクラスに登場しました。 このメソッドはパブリックではなく、sun.misc.Hashing.stringHash32（String）メソッドを呼び出すことによってのみリフレクションなしでアクセスできます。 このメソッドは、サイズがシステムプロパティjdk.map.althashing.thresholdの値を超える場合、ハッシュベースのコレクションによってJDK 7で使用されます。 これは実験的な方法であり、コードで使用することはお勧めしません。
• Java 1.7.0_06以降、すべての標準の非マルチスレッドコレクションには、新しいハッシュアルゴリズムによる望ましくない副作用があります。 このエラーは、毎秒多くのマップコレクションを作成するマルチスレッドアプリケーションでのみ発生します。

自分から

Javaの文字列が文字の配列を共有しているという事実は、それらが永続的であることを示唆しています。 永続構造は、変更時に以前のバージョンをすべて保持する構造と呼ばれることが知られています。 これは、部分文字列メソッドの実行時間を一定にするために使用されるメモリ量を削減する最適化として、明示的に行われました。 ただし、この最適化の利点はそれほど大きくないため、このアイデアはJavaのバージョン7で放棄されました。



.NETでは、文字列は最初は永続的ではありませんでした。 エリック・リッパートによる興味深い記事へのリンクがありますが、その理由について詳しく説明しています。



読んでくれてありがとう。

この記事がお役に立てば幸いです。