77

String の Java 6 ソース コードで、hashCode が 0 以外の値のみをキャッシュしていることに気付きました。パフォーマンスの違いは、次のスニペットで示されています。

public class Main{
   static void test(String s) {
      long start = System.currentTimeMillis();
      for (int i = 0; i < 10000000; i++) {
         s.hashCode();
      }
      System.out.format("Took %d ms.%n", System.currentTimeMillis() - start);
   }
   public static void main(String[] args) {
      String z = "Allocator redistricts; strict allocator redistricts strictly.";
      test(z);
      test(z.toUpperCase());
   }
}

これを ideone.com で実行すると、次の出力が得られます。

Took 1470 ms.
Took 58 ms.

だから私の質問は：

  • String の hashCode() が 0 をキャッシュしないのはなぜですか?
  • Java 文字列が 0 にハッシュされる確率は?
  • 文字列が 0 にハッシュされるたびにハッシュ値を再計算するというパフォーマンスの低下を回避する最善の方法は何ですか?
  • これは値をキャッシュするベストプラクティスの方法ですか? (つまり、1 つを除いてすべてをキャッシュしますか?)

お楽しみに、ここの各行は 0 にハッシュされる文字列です。

pollinating sandboxes
amusement & hemophilias
schoolworks = perversive
electrolysissweeteners.net
constitutionalunstableness.net
grinnerslaphappier.org
BLEACHINGFEMININELY.NET
WWW.BUMRACEGOERS.ORG
WWW.RACCOONPRUDENTIALS.NET
Microcomputers: the unredeemed lollipop...
Incentively, my dear, I don't tessellate a derangement.
A person who never yodelled an apology, never preened vocalizing transsexuals.
4

9 に答える 9

58

あなたは何も心配していません。この問題について考える方法を次に示します。

1 年中文字列をハッシュするだけのアプリケーションがあるとします。1,000 個の文字列がすべてメモリ内にあり、それらに対して hashCode() をラウンドロビン方式で 100 万回繰り返し呼び出し、別の 1,000 個の新しい文字列を取得してもう一度実行するとします。

また、文字列のハッシュ コードがゼロになる可能性が、実際には 1/2^32 よりもはるかに大きいとします。1/2^32 よりは多少大きいと思いますが、1/2^16 のようにそれよりもずっと悪いとしましょう (平方根! 今ではもっと悪い!)。

この状況では、オラクルのエンジニアがこれらの文字列のハッシュ コードをキャッシュする方法を改善することで、誰よりも多くの恩恵を受けることができます。それであなたは彼らに手紙を書いて、それを修正するように頼みます. そして、彼らは s.hashCode() がゼロのときはいつでも即座に戻るように魔法を働かせます(初めてでも! 100% 改善!)。そして、他のケースではパフォーマンスをまったく低下させることなくこれを行うとしましょう。

万歳！これで、あなたのアプリは...見てみましょう... 0.0015% 速くなりました!

以前は 1 日かかっていた作業が、23 時間 57 分 48 秒に短縮されました。

そして忘れてはならないのは、私たちは、多くの場合ばかげた程度にまで、疑いのすべての可能な利益を与えるようにシナリオを設定したことです.

これはあなたにとって価値があると思いますか？

編集:数時間前にこれを投稿して以来、プロセッサの 1 つを暴走させて、ハッシュ コードがゼロの 2 語のフレーズを探しました。これまでのところ、bequirtle zorillo、chronogrammic schtoff、contusive cloisterlike、creashaks organzine、drumwood boulderhead、electroanalytic exerciseable、および favosely nonconstruable が考え出されています。これは約 2^35 の可能性から外れているため、完全な分布で​​は 8 しかないと予想されます。明らかに、それが完了するまでに数倍になりますが、異常に多くなるわけではありません。さらに重要なことは、いくつかの興味深いバンド名/アルバム名を思いついたことです! 公正な盗みはありません！

于 2010-02-22T18:41:33.013 に答える
24

0 を使用して、「まだハッシュコードを計算していない」ことを示します。別のブール値フラグを使用すると、より多くのメモリが必要になります。(もちろん、ハッシュコードをまったくキャッシュしないこともできます。)

多くの文字列が 0 にハッシュされるとは思いません。おそらく、ハッシュ ルーチンが意図的に 0 を回避することは理にかなっているでしょう (たとえば、0 のハッシュを 1 に変換し、それをキャッシュします)。これにより、衝突が増加しますが、再ハッシュは回避されます。ただし、String hashCode アルゴリズムは明示的に文書化されているため、今それを行うには遅すぎます。

これが一般的に良いアイデアであるかどうかについては、これは確かに効率的なキャッシング メカニズムであり、0 のハッシュで終わる値の再ハッシュを回避するように変更することで (編集を参照)、さらに改善される可能性があります。そもそもこれを行う価値があると Sun が信じるようになったデータ - これまでに作成された文字列ごとに余分な 4 バイトを占めていますが、ハッシュされることはよくあることですが、めったにありません。

編集: KevinB が他の場所のコメントで指摘しているように、上記の「0 を回避する」提案は、非常にまれなケースに役立つため、正味のコストがかかる可能性がありますが、ハッシュ計算ごとに追加の比較が必要です。

于 2010-02-22T11:22:02.480 に答える
19

これまでの他の回答に欠けている重要な点があると思います。ゼロ値が存在するため、マルチスレッド環境で hashCode キャッシュ メカニズムが確実に機能します。

cachedHashCode 自体と、cachedHashCode が計算されたかどうかを示す isHashCodeCalculated ブール値のような 2 つの変数がある場合、マルチスレッド環境で動作するにはスレッド同期が必要になります。また、特に文字列は複数のスレッドで非常に一般的に再利用されるため、同期はパフォーマンスに悪影響を及ぼします。

Java メモリ モデルについての私の理解は少し大雑把ですが、大まかに何が起こっているかを次に示します。

  1. 複数のスレッドが変数 (キャッシュされた hashCode など) にアクセスする場合、各スレッドが最新の値を参照できるという保証はありません。変数がゼロから始まる場合、A はそれを更新 (ゼロ以外の値に設定) し、その後すぐにスレッド B がそれを読み取りますが、スレッド B はまだゼロ値を見ることができます。

  2. 複数のスレッドからの共有値へのアクセス (同期なし) には別の問題があります。部分的にしか初期化されていないオブジェクトを使用しようとしてしまう可能性があります (オブジェクトの構築はアトミック プロセスではありません)。long や double などの 64 ビット プリミティブのマルチスレッド読み取りおよび書き込みも、必ずしもアトミックであるとは限りません。そのため、2 つのスレッドが long または double の値を読み取って変更しようとすると、1 つのスレッドが奇妙なものや部分的に設定されたものを見ることになる可能性があります。 . とにかくそのようなもの。cachedHashCode と isHashCodeCalculated のように、2 つの変数を一緒に使用しようとすると、同様の問題が発生します。スレッドは、これらの変数の 1 つの最新バージョンを簡単に参照できますが、別の変数の古いバージョンを参照できます。

  3. これらのマルチスレッドの問題を回避する通常の方法は、同期を使用することです。たとえば、キャッシュされた hashCode へのすべてのアクセスを同期ブロック内に配置したり、volatile キーワードを使用したりできます (ただし、セマンティクスが少し混乱するため注意してください)。

  4. ただし、同期は速度を低下させます。文字列 hashCode のようなものは悪い考えです。文字列は HashMap のキーとして頻繁に使用されるため、マルチスレッド環境を含め、hashCode メソッドが適切に機能する必要があります。

  5. int などの 32 ビット以下の Java プリミティブは特殊です。たとえば、long (64 ビット値) とは異なり、int (32 ビット) の部分的に初期化された値を読み取ることは決してありません。同期せずに int を読み取ると、最新の設定値を取得できるかどうかはわかりませんが、取得する値が、スレッドまたは別のスレッド。

java.lang.String の hashCode キャッシング メカニズムは、上記のポイント 5 に依存するように設定されています。java.lang.String.hashCode() のソースを見ると、よりよく理解できるかもしれません。基本的に、複数のスレッドが一度に hashCode を呼び出すと、hashCode が複数回計算される可能性があります (計算された値がゼロの場合、または複数のスレッドが一度に hashCode を呼び出して両方がゼロのキャッシュ値を参照する場合)。 () は常に同じ値を返します。そのため、堅牢であり、パフォーマンスも優れています (マルチスレッド環境でボトルネックとなる同期がないため)。

前述したように、Java メモリ モデルについての私の理解は少し大雑把ですが、上記の要点は理解できたと確信しています。最終的には、同期のオーバーヘッドなしで hashCode をキャッシュするための非常に賢いイディオムです。

于 2010-09-18T18:30:45.933 に答える
8

実装がキャッシュされた値 0 を「キャッシュされた値がまだ初期化されていない」と解釈するため、0 はキャッシュされません。代替手段はjava.lang.Integer、値がまだキャッシュされていないことを意味する null を使用することでした。ただし、これは追加のストレージ オーバーヘッドを意味します。

文字列のハッシュ コードが 0 として計算される確率については、確率は非常に低く、次の場合に発生する可能性があります。

  • String は空です (ただし、このハッシュ コードを毎回再計算すると実質的に O(1) になります)。
  • オーバーフローが発生し、最終的に計算されたハッシュ コードが 0 になります ( e.g. Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0)。
  • 文字列には Unicode 文字 0 のみが含まれます。これは「紙テープの世界」以外では意味のない制御文字であるため、ほとんどありません (!):

ウィキペディアから：

コード 0 (ASCII コード名 NUL) は特殊なケースです。紙テープでは、穴が開いていない場合です。これは、特に意味のない埋め込み文字として扱うと便利です。

于 2010-02-22T11:23:12.123 に答える
6

これは、セキュリティの脆弱性に関連する良い質問であることがわかりました。

「文字列をハッシュするとき、Java はハッシュ値もハッシュ属性にキャッシュしますが、それは結果が 0 以外の場合のみです。したがって、ターゲット値 0 は、キャッシュを防ぎ、再ハッシュを強制するため、攻撃者にとって特に興味深いものです。」

于 2012-01-07T08:04:08.223 に答える
0

皆さん、長さがゼロの場合、とにかくゼロになるため、0を保持します。

そして、len がゼロであり、ハッシュコードもそうでなければならないことを理解するのにそれほど時間はかかりません。

だから、あなたのコードレビューのために！これがJava 8の栄光です。

 public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

ご覧のとおり、文字列が空の場合、これは常にゼロを返します。

  if (h == 0 && value.length > 0) ...
于 2015-04-25T09:16:06.183 に答える
0
  • String の hashCode() が 0 をキャッシュしないのはなぜですか?

値 0 は、「ハッシュ コードがキャッシュされていない」という意味で予約されています。

  • Java 文字列が 0 にハッシュされる確率は?

Javadoc によると、文字列のハッシュコードの式は次のとおりです。

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

は文字列の i 番目の文字、 は文字列intの長さです。(空の文字列のハッシュは、特殊なケースとしてゼロと定義されています。)s[i]n

私の直感では、上記のハッシュコード関数は、値の範囲全体に文字列ハッシュ値を均一に広げintます。ランダムに生成された文字列がゼロにハッシュされる確率が 2^32 分の 1 であることを意味する一様な広がり。

  • 文字列が 0 にハッシュされるたびにハッシュ値を再計算するというパフォーマンスの低下を回避する最善の方法は何ですか?

最善の戦略は、問題を無視することです。同じ String 値を繰り返しハッシュしている場合、アルゴリズムに奇妙な点があります。

  • これは値をキャッシュするベストプラクティスの方法ですか? (つまり、1 つを除いてすべてをキャッシュしますか?)

これは、スペースと時間のトレードオフです。私の知る限り、代替手段は次のとおりです。

  • 各 String オブジェクトにフラグを追加して、cachedすべての Java String が余分な単語を取るようにします。

  • メンバの最上位ビットをhashキャッシュ フラグとして使用します。そうすれば、すべてのハッシュ値をキャッシュできますが、可能性のある文字列ハッシュ値は半分しかありません。

  • 文字列のハッシュコードをまったくキャッシュしないでください。

Java 設計者は Strings を正しく選択したと思います。また、彼らの決定の妥当性を確認する広範なプロファイリングを行ったと確信しています。ただし、これが常にキャッシングを処理する最善の方法であるとは限りません。

(ゼロにハッシュされる 2 つの「一般的な」文字列値があることに注意してください。空の文字列と、NUL 文字だけで構成される文字列です。ただし、これらの値のハッシュコードを計算するコストは、典型的な文字列値のハッシュコード。)

于 2010-02-22T14:20:36.020 に答える