HashMap はいつ、どのようにしてバケットをリンクリストから Red Black Trees に変換するのでしょうか? [重複] 質問する

Question

ある場合少なくとも1つのバケットに8つのエントリ（TREEIFY_THRESHOLD）があり、バケットの合計数が64（）を超えるMIN_TREEIFY_CAPACITY場合、その単一のバケットは完璧にバランスのとれた赤黒の木のノード。

UNTREEIFY_THRESHOLDまた、エントリ ( == 6)を削除するときに発生する縮小にも注意する必要があります (必要な場合) 。

キーが - であるべきだというのは正しいのですComparableが、必ずしもそうである必要はありません。同じであれば問題ありませんが (同じである場合hashCode)、そうでない場合は、次のように使用されます。

 static int tieBreakOrder(Object a, Object b) {
        int d;
        if (a == null || b == null ||
            (d = a.getClass().getName().
             compareTo(b.getClass().getName())) == 0)
            d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                 -1 : 1);
        return d;
 }

そのため、classNameはString比較に使用され、それが失敗した場合は、System.identityHashCode（Marsaglia XOR-Shiftアルゴリズム）を使用して決定されます。左そして右。

質問への回答は、これが発生するのはHashMapいつですか - resize が呼び出されるときです。サイズを変更する必要がある場合、バケットの数が 2 倍に増える (エントリが移動するかどうかで 1 ビット多く考慮される) か、特定のバケットがツリーに変換されるなど、いくつかのことが起こります。このプロセス (これも本当に気になる場合) は非常に遅く、Java HashMap は「最初はとても遅い、次はとても速い、次はとても遅い、次はとても遅い」と言う人もいます (私はまだこれを嘲笑と見ていますが、PauselessHashMap実装はあります)。

これには 2 つの興味深い点があります。まず、最初に正しいサイズを選択しますMap(大まかな見積もりでもかまいません)。

 new HashMap<>(256); // choosing the size

これにより、一部のサイズ変更を回避できます。

2 つ目は、への変換がなぜTree重要なのかということです (データベースインデックスとそれがなぜ重要なのかを考えてくださいBTREE...)。 INTEGER.MAX_VALUE エントリ (理論上) を持つ完全なツリーでエントリを見つけるには、何ステップかかりますか。最大 32 までです。

Answer 1