Java 配列から HashMap へのアルゴリズムの説明

1. 配列とは何ですか?

どの本にこのような文章があったか忘れましたが、「すべてのデータ構造は配列の進化形である」。よく考えてみると、これは実際に理にかなっています。なぜなら、コンピューターのメモリは実際には線形のストレージスペースだからです。

Java サンプルコード:

 int []配列=新しいint [ 5 ]

オブジェクトヘッダーと配列の長さの情報を無視すると、JVM は実行時にヒープ内に 20 バイトのメモリを割り当てます。これは次のようになります。

このようなデータ構造は、配列の添え字を通じてデータに簡単にアクセスできますが、検索時に配列をトラバースする必要があり、平均時間計算量は O(n/2) です。

データ量が大きい場合や検索操作が頻繁に行われる場合、このようなトラバーサル操作はほとんど受け入れられません。では、どうすればより短時間でデータを素早く見つけることができるのでしょうか?

2.二分探索

配列内の要素がすでにソートされている場合、自然な方法はバイナリ検索を使用することです。

たとえば、長さが 1000 の整数配列があり、配列内の整数は小さいものから大きいものの順に並べられています。この配列に 6000 があるかどうかを知りたいとします。次に、まず配列[500]の数字が6000かどうかを確認します。配列[500]の数字が6000より小さい場合は、配列[750]の数字を確認します...。これを最大10回繰り返した後、結果を判定できます。

このアルゴリズムの時間計算量は O(logN) です。

ただし、ほとんどの場合、配列要素は順序付けられておらず、ソートに必要な時間計算量 O(NlogN) は通常、トラバースに必要な時間よりもはるかに長くなります。

つまり、問題は振り出しに戻ってしまいます。乱雑なデータの中からデータを素早く見つけるにはどうすればよいでしょうか?

3. 無知な思考

プログラミングを学び始めて間もなく、「Programming Pearls」を読んだことを今でも覚えています。そこには、次のような記述がありました。1970 年代に、マイク・レスクは電話会社の電話番号検索機能を作成しました。たとえば、数字キー 5375*6* に対応する LESK*M* を入力すると、エラー一致率はわずか 0.2% で、正しい電話番号またはオプションのリストが返されます。

これはどうすればできるのでしょうか?

当時はデータ構造やアルゴリズムについて何も知りませんでした。自分の無謀な思考の過程を思い出すと、今でもとても興味深いです。

1. 追加

すべての数字を足し合わせると（* キーは 11）、5375*6* の合計は 48 になります。ほとんどの入力の合計は 100 を超えません。つまり、数万の電話番号が配列の最初の 100 の位置に集中することになり、これは実現不可能です。

2. 掛け算

すべての数字を掛け合わせると、その積は 381150 になります。これは実現可能であるように思われますが、問題があります。lesk、lsek、slke... の積は同じであり、各数字キーは 3 つの文字に対応するため、重複の可能性が非常に高くなります。

3. 乗算の改善

① 同じ文字だが文字の順序が異なる文字列は、各数字にシーケンス番号を掛け、次に他の値を掛けることで競合を回避できます。

② 各数字キーは3つの英語の文字に対応しています。ユーザーが数字キーに文字の連続番号を入力しないと、それ以上正確に計算することはできません。考えられる唯一の方向性は、与えられた単語リストに基づいて確率統計を作成することであるため、考慮されません。

4. 場所の競合

改良された乗算方法を使用しても、異なる名前の文字を使用して計算された積が重複する可能性があります。競合が発生した場合はどうすればよいですか?

次の空いている位置に連続して保存しますか?考えてみれば、これはうまくいかないでしょう。次の空白位置が別の文字セットの産物である場合、二次的な競合が発生します。

幸いなことに、素数は存在します。

素数は 1 とそれ自身でしか割り切れないので、上記の乗算によって得られる積は素数にはならず、素数の位置に電話番号は格納されません。

したがって、現在の積から始めて、右側にある次の素数を検索します。素数の位置がまだ使用されている場合は、次に最も近い素数の検索を続けます...

今のところ、問題は解決したようです。

ユーザーが数字の文字列を入力すると、数式に従って積が計算され、添え字の位置にある電話番号が返されます。正しくない場合は、素数の添え字を持つ配列要素が空になるまで、次の素数を順番に検索し、最後に見つかった電話番号をすべて返します。ほとんどの場合、電話番号を見つけるのにかかる時間は O(1) だけです。

5. 配列が大きすぎる

唯一の問題は、上記のアイデアに従って作成された配列が大きすぎることです。名前は 10 文字です。各文字に対応する数字が 9 の場合、最終的な積はおよそ 9 の 17 乗になります。これは、サイズが 9^17 の配列を作成することを意味しますが、これは完全に不可能です。

6. 後日

配列の係数が大きすぎることを考慮しなくても、当時の私のプログラミングレベルでは、このようなプログラムを書くことはできなかったでしょう。

私がこの思考プロセスを復活させた理由は、自立して考えるプロセスがとても興味深く、価値があると考えているからです。考えてみてください。実際、既存のアルゴリズムはすべて、実際のエンジニアリングプロジェクトで段階的に解決策を模索した優れた専門家によって導き出されたものです。

したがって、工学において難しい問題に遭遇したとき、問題を細分化して考え、それぞれの小さな問題に対する解決策を模索する意欲があれば、多くのいわゆる難しい問題は解決できるのです。

その後、「データ構造とアルゴリズム分析。Java 言語の説明」を読んで、私のアイデアは実はオープンアドレッシングだったことに気付きました。

JDK の HashMap は個別のチェーンを使用します。相違点: 競合するデータを保存するためのバケットの概念が追加され、配列サイズを縮小するためにモジュロ演算が実行されました。

それでは、Java の HashMap について説明しましょう。

4. HashMapの構造とアルゴリズムの詳細な説明

HashMap の本質は依然として配列であり、以下に示す構造に似た、長さが不定の多次元配列です。

1. 簡単な紹介

HashMap 内の配列は、リンクリストのヘッドノードを保持します。

データを保存:

キーの hashCode を計算し、配列の長さでモジュロ演算を実行して、配列の添え字 (リンクリストのヘッドノード) を取得します。

位置が空の場合は、新しいリンクリストノードを生成し、配列に保存します。

位置が空でない場合は、リンクリスト内の各ノードをループします。同じキーを持つノードがすでに存在する場合は、古いノードを上書きします。同じキーを持つノードが存在しない場合は、新しいノードをリンクリストの末尾ノードとして使用します(注: JDK1.8 のソースコードを参照してください。新しいノードは、JDK1.6 のようにリンクリストの先頭ノードとして追加されるのではなく、常にリンクリストの末尾に追加されます) 。

データを検索:

キーの hashCode を計算し、配列の長さでモジュロ演算を実行して、配列の添え字 (リンクリストのヘッドノード) を取得します。リンクリストが空でない場合は、まず最初のノードを比較します。最初のノードキーが同じ (hashCode が同じで equals が true) 場合は、最初のノードの値を直接返します。最初のノードキーが異なる場合は、リンクリスト内の他のノードを順番に走査し、同じキーを持つノードの値を返します (同じキーを持つノードが見つからない場合は null を返します)。

HashMap にリンクリストを導入する目的は、前のセクションで説明した重複競合の問題を解決することです。

注記：

すべてのキーのハッシュコードが同じで、すべて 0 であると仮定すると、0%4 = 0 となり、すべての要素がリンクリスト 0 に保存されます。各データを保存および検索するには、リンクリスト 0 を走査する必要があります。そして、この時点で、HashMap は本質的にリンクリストに退化し、時間の計算量も設計された O(1) から O(n/2) に増加します。

HashMap の検索と保存の時間計算量を O(1) に可能な限り抑えるには、各リンクリスト内の要素を均等に分散する必要があります。つまり、各リンクリストには 1 つの要素のみが格納されます。

では、影響を与える要因は何でしょうか?

まず、キーのハッシュコードは重複できません。重複する場合は、少なくとも 2 つの要素を格納するリンクリストが必要です。
2 つ目はハッシュ関数の設計です。単純に剰余を求めると、剰余の中に多くの繰り返しが生まれます。
3 番目は、リンクリストのサイズです。長さ 10 の配列に 100 個の要素を分散する場合、計算方法に関係なく、複数の要素を格納するリンクリストが存在します。最適なケースは、各リンクリストに 10 個の要素が格納されることです。

これら 3 つの要素のアルゴリズム設計については、以下で詳しく説明します。

2. ハッシュコード生成

これは、String クラスの hashCode 生成コードです。

パブリックintハッシュコード() {
int h = ハッシュ;
h == 0 &&値.長さ > 0の場合{
char val[] =値;
( int i = 0 ; i <値.長さ; i++) {
        h = 31 * h + val[i];
      }
      ハッシュ = h;
    }
hを返します。
  }

Stringクラスの値はchar[]であり、charはUTF-8エンコーディングに変換できます。たとえば、「a」、「b」、「c」の UTF-8 コードはそれぞれ 97、98、99 です。上記のコードに従って「abc」を変換する式は次のとおりです。

h = 31 * 0 + 97 = 97;
h = 31 * 97 + 98 = 3105;
h = 31 * 3105 + 99 = 96354;

31 は比較的適切なサイズの素数であるため、乗算係数として使用されます。値が小さすぎると、ハッシュコードの計算に関係する項目の数が少ない場合に積が小さすぎます。偶数の場合は左シフトに相当し、乗算がオーバーフローすると、通常のビット情報の損失が発生します。これらは両方とも繰り返し率の増加につながります。

乗算係数として 32 (<< 5 に相当) を使用する場合、文字列 "abcabcabcabcabcabc" を例にとると、そのハッシュコードの各ステップの計算結果は次のようになります。

上図に示すように、文字列の末尾の 3 文字ごとに繰り返しハッシュコードが生成されます。これは偶然ではありません。他の英語の文字を使用した場合でも、重複が発生する可能性があります。素数を使用すると、重複の可能性が大幅に減少します。興味があれば、上の図を参考にして左シフト操作を実行すると、これが偶然ではないことがわかります。

ハッシュコードの生成ルールや注意点については、「Effective Java」という書籍に詳しく解説されていますので、興味のある方はご覧ください。

ソースコードの hashCode() メソッドから、String クラスのオブジェクトが計算された hashCode を保存していることがわかります。hashCode() メソッドが呼び出された場合、2 回目の呼び出しでは再生成されず、計算された hashCode が直接返されます。

String オブジェクトは常に、String クラスによってプライベートに管理される定数プールに格納されます。new キーワードが明示的に使用されていない場合、定数プール内に同じ値を持つオブジェクトが既に存在する場合は、既存のオブジェクトへの参照が常に返されます。したがって、多くの場合、hashCode を生成するというコストのかかる操作を実際に実行する必要はありません。

3. ハッシュ関数の設計

これで、重複率が非常に低い hashCode を取得できました。何か足りないものはありますか?

摂動関数

静的最終intハッシュ（オブジェクトキー） {
整数h;
戻り値(key == null ) ? 0 : (h = key.hashCode()) ^ (h >>> 16 );
  }

次の図は、文字列「abcabcabcabcabc」を例として、上記の方法を使用して計算されたプロセスと結果を示しています。

最初に 16 ビットを符号なし右シフトしてから XOR 演算を実行するのはなぜですか?下の図のバイナリ AND 演算を見ると理解できるでしょう。

2 進数の最後の 4 ビットが変更されない限り、前の 2 進ビットがどのように変更されても同じ結果が表示されることがわかります。上位ビットが変化しても下位ビットが変化しないため、計算結果が同じになる状況を防ぐには、上位ビットの変化を含める必要があります。この効果は、整数のバイナリビットの上位半分と下位半分に対して XOR 演算を実行することで実現できます。

AND 演算を使用する理由は何ですか?

ハッシュ関数の計算式はhashCode % tableSizeなので、tableSizeが2のn乗(n ≥ 1)のときはhashCode & (tableSize – 1)と等しくなります。

摂動関数の最適化前: 1954974080 % 16 = 1954974080 & (16 – 1) = 0
摂動関数が最適化された後: 1955003654 % 16 = 1955003654 & (16 – 1) = 6

これが摂動関数が必要な理由です。

ソースコードの説明

コードを説明する前に、JDK 1.8 では、競合が多数発生した場合の検索効率を解決するために赤黒木が導入されたことを付け加えておきます。したがって、リンクリスト内のデータが一定のサイズに達すると、リンクリストは赤黒木に変換されます。したがって、jdk1.8 では、HashMap の検索とデータ保存の最大時間計算量は、実際には赤黒木の時間計算量 O(logN) になります。

以下は、HashMap にデータを保存するメソッドのソースコードです。上記の説明の後では、このコードを理解するのは非常に簡単だと思います。

最終的な V putVal ( intハッシュ、 K キー、 V値、 boolean onlyIfAbsent、 boolean evict ) {
    Node<K,V>[] tab; //HashMap配列
    Node<K,V> p; //保存するデータを初期化する
int n; //配列の容量
int i; //配列の添え字

/* 配列が空または 0 の場合、容量を 16 に初期化します */
if ((tab = table) == null || (n = tab.length) == 0 ){
      n = (タブ = resize()).length;
    }

/* ハッシュ関数を使用して配列の位置を取得します (空の場合は、新しいノードを配列に保存します) */
if ((p = tab[i = (n - 1 ) & hash]) == null ){
      tab[i] = newNode(ハッシュ、キー、値、 null );
    }

/* 配列の位置にすでに値がある場合は、次のメソッドを使用してデータを保存します*/
それ以外{
      Node<K,V> e; //新しい値を保存するための一時ノード
      K k; // キーを比較するために使用する一時変数

//ヘッドノードのハッシュ値と新しいノードのキーが同じで、キー値が等しい場合、eは古いノードに割り当てられます
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){の場合
        e = p;
      }

//ヘッドノードが赤黒ツリーノードの場合、eはツリーノードとして保存されます
そうでない場合( p TreeNode のインスタンス) {
      e = ((TreeNode<K,V>)p).putTreeVal( this 、タブ、ハッシュ、キー、値);
      }

// ヘッドノードが新しいノードと異なり、ヘッドノードが赤黒木ノードでない場合は、リンクリスト内のすべてのノードをループします。
それ以外{
( int binCount = 0 ; ; ++ binCount ) {
((e = p.next) == null の場合) {
//リンクリストの最後まで同じキーを持つノードが見つからない場合は、新しいノードをリンクリストの最後のノードとして追加します
            p.next = newNode(ハッシュ、キー、値、 null );

//リンクリスト内のノード数が 8-1 以上の場合は、赤黒木に変換します。赤黒木に変換されるノードの最小数は 8 です。
binCount >= TREEIFY_THRESHOLD - 1 の場合{
              treeifyBin(タブ、ハッシュ);
            }
壊す;
          }
//ループ中に新しいキーと古いキーの値が同じ場合は、次の場所にジャンプします: 古い値を上書きするかどうか
e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){の場合
壊す;
          }
          p = e;
        }
      }

//古い値を上書きするかどうか
e != null の場合
        V 古い値 = e.value ;
//新しい値が空でない場合（古い値を変更できるか、古い値が空の場合）、古いノードの値を上書きします
if (!onlyIfAbsent || oldValue == null ) {
          e.値=値; 	
        }
        afterNodeAccess(e); //コールバック関数。ここでは空の関数ですが、このメソッドはlinkedHashMapで実装されています。
return oldValue; //古い値を返す
      }
    }

//コレクションのトラバース中に他のスレッドがコレクションを変更するかどうかを比較して判断するために使用されます。詳細については、オンラインで「fail-fast fast failure メカニズム」を検索してください。
    ++modCount;

// キーの数が許容容量を超える場合は、容量を拡張します。 HashMap で許容される容量は配列の長さ * フィルファクターです (デフォルトは 0.75)
if (++サイズ > 閾値){
    サイズを変更します。
    }

//コールバック関数。ここでは空の関数ですが、このメソッドはlinkedHashMapで実装されています。
    afterNodeInsertion(削除);
nullを返します。
  }

簡略化された擬似コード

  putval(キー、値){
    インデックス = キー.ハッシュコード % テーブルサイズ;
if ( null == テーブル[インデックス]){
      table[index] =新しいノード(キー、値);
    }それ以外{
      firstNode = テーブル[インデックス];
      次のノード = firstNode.next;
nextNode.hasNextNode() が次のノードにある間
//同じキーを持つ古いノードが見つかった場合は、古いノードを上書きします
if (キー == nextNode.key){
          nextNode =新しいノード(キー、値);　
壊す;
        }
//キューの最後に同じキーを持つ古いノードが見つからない場合は、最後のノードの最後に新しいノードを追加します
(nextNode.next == null )の場合{
          nextNode.next =新しいノード(キー、値);
壊す;
        }
        次のノードを次に示します。
      }
    }
  }