アルゴリズムのハッシュ表/JAVA

文書ディレクトリ

@[toc]

1.3ハッシュ表

1.3.1 hashCodeとequals

1.3.2ファスナー法処理衝突

1.3.3線形検出法に基づくハッシュテーブル

1.3.4ハッシュテーブルと他のアルゴリズムの比較

1.3ハッシュ表
ハッシュ表とは何か、ハッシュ表は配列に似たデータ構造であり、Keyの値によって対応するValueを直接見つけることができる.ハッシュ・テーブルと配列の違いは、配列が下付き文字で直接データにアクセスでき、下付き文字は整数(int)のみであり、ハッシュ・テーブルは任意のデータ型をKeyとすることができることである.
ハッシュ・テーブルを使用して2つのセクションに分けられます.最初のステップは、ハッシュ関数で検索されたKeyを配列のインデックスに変換することです.もちろん、理想的には異なるキーを異なるインデックスに変換することが理想的ですが、これは現実的には実現しにくいので、2番目のステップは、2つの異なるキー対が同じKeyに対応する問題を解決し、衝突衝突衝突を処理することです.衝突衝突を処理する最も一般的な方法はファスナー法と線形検出法である.
1.3.1 hashCodeとequals
衝突衝突の2つの処理を学習する前にhashCodeとequalsを深く理解する必要がある.
Javaの構文規定では、すべてのデータ型が32ビットの整数を返すhashCode()メソッドを継承します.hashCode()の戻り値はメモリ内のアドレス(実際にはメモリ内の仮想アドレスが変換された整数であり、異なる仮想マシンと環境で得られた結果が一致しない)と見なすことができ、equalsは値が等しいかどうかを比較する(基本タイプを除く).ではhashCodeはequalsと何の関係があるのでしょうか.

両オブジェクトのhashCode比較の結果は等しく,equals比較の結果は必ずしも等しくない

.

両オブジェクトのequals比較の結果は等しく,hashCode比較の結果は必ずしも等しくない

.

両オブジェクトのhashCode比較の結果は等しくなく、equals比較の結果は必ず等しくない

両オブジェクトのequals比較の結果は等しくなく、hashCode比較の結果は必ずしも等しくないとは限らない

hashCodeを理解するにはまず集合を理解しなければならない.Javaでは集合が2つのListとSetに分かれている.前者は秩序であり、後者は重複を許さない.では、Setはどのように重複を許さないことを保証するのか.まず第1点はequals比較を行うことで結果が等しいかどうかを明らかにすることであるが,1つのSetにすでに1万個の要素が存在し,1万個の要素が格納されている場合には1万回の比較を行う可能性があり,これは非常に大きな演算量であり,速度を大幅に低下させるが,hashCode比較を行うとhashCodeが等しい場合にequals比較を行う.hashCodeが待ちたくない場合は、直接保存することで、万回の比較を何回か1回に下げ、効率を高めることができます.
次にhashCodeの2つの特徴について議論します.

等しいオブジェクトには、等しいhashCodeが必要です.

両オブジェクトのhashCodeが同一である場合、それらは必ずしも同一ではない.

まず1つ目は,2つのオブジェクトAとBがあり,AとBが等しいと仮定し,彼らのhashCodeが待ちたくない場合,hashMapでhashCodeによって計算された値が一定に異なると仮定すると,AとBはhashMapに格納することができ,これは明らかにSetの定義と一致しない.
次に2番目に、オブジェクトAとオブジェクトBのどちらがhashCodeが等しく、値が異なると仮定すると、hashCodeによって計算された値は同じですが、hashMapに格納する必要があります.hashCodeが同じですが、値が異なるオブジェクトをどのように格納するかは、衝突衝突を処理することによって解決する必要がある問題です.
1.3.2ファスナー法による衝突処理
Mサイズの配列がN個のデータを格納していると仮定し,ハッシュ関数によりKeyを配列下標に変換し,衝突衝突が発生した場合ファスナー法で処理したが,ファスナー法はどのように処理したのか.
ファスナー法とは、各配列要素をチェーンテーブルに指向し、衝突衝突が発生した場合にノードを追加し、データを格納することであり、データを検索する際には、まず下付きスケールでvalueが存在するチェーンテーブルを直接見つけ、チェーンテーブルを巡って対応する要素を見つけ、時間の複雑さはO(N)に維持される.
**配列Mのサイズはどのように選択しますか?**ファスナー法に基づいてハッシュテーブルを実現する場合、チェーンテーブルが長すぎるために時間を浪費しないことを保証するために、適切な大きさのMを選択する必要があります.また、空のチェーンテーブルのためにメモリを浪費することもありません.多くの実践を経て、科学者たちはチェーンテーブルの平均長を2～8に維持することが最も適切だと提案しています.
要素を削除する方法チェーンテーブル削除要素と同じです.
ファスナー法に基づくハッシュ表を以下に示す.
まず、シーケンス検索を実現するチェーンテーブル

/**
 * @author linxi
 * @function          
 * @project   
 * @package   .    
 * @date 2020/7/20-11:47   
 */
public class SequentialSearchST<Key, Value> {
    //     
    private Node first;
    //  
    private class Node{
        Key key;
        Value value;
        Node next;

        public Node(Key key, Value value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    //  key  value
    public Value get(Key key){
        for (Node x = first; x != null; x = x.next){
            if (key.equals(x.key)){
                //   
                return x.value;
            }
        }
        return null;
    }

    //  key  value，  value      
    public void put(Key key, Value value){
        for (Node x = first; x != null; x = x.next){
            if (key.equals(x.key)){
                //   
                x.value = value;
                return;
            }
        }
        first = new Node(key, value, first);
    }
}

ファスナー法に基づくハッシュテーブルの実現

/**
 * @author linxi
 * @function          
 * @project   
 * @package   .   
 * @date 2020/7/20-10:31   
 */
public class SeparateChainingHashST<Key, Value> {
    //      
    private int N;
    //    
    private int M;
    //         
    //SequentialSearchST             
    private SequentialSearchST<Key, Value>[] st;

    /**
     *                
     * @param M
     */
    public SeparateChainingHashST(int M) {
        this.M = M;
        st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
        for (int i = 0; i < M; i++) {
            st[i] = new SequentialSearchST<>();
        }
    }


    /**
     *      
     * @param key
     * @return
     */
    private int hash(Key key){
        // hashCode     0，      ，   M，       0～M-1  
        return (key.hashCode() & 0x7fffffff) % M;
    }

    /**
     *     
     * @param key
     * @return
     */
    public Value get(Key key){
        return (Value) st[hash(key)].get(key);
    }

    /**
     *     
     * @param key
     * @param value
     */
    public void put(Key key, Value value){
        st[hash(key)].put(key, value);
    }
    
}

1.3.3線形検出法に基づくハッシュテーブル
線形プローブ法がファスナー法と異なる点は,線形プローブ法が配列中の空孔で衝突衝突を解決することであり,衝突が発生するとハッシュテーブルの次の位置を直接チェックし,空であれば挿入し,空でなければ次の位置を検索し続け,空である位置に遭遇するまで検索することである.
**配列Mのサイズはどのように選択しますか?**多くの実践を経て、科学者たちはデータを格納する位置を配列全体の1/8～1/2にするのが最も適切であることを提案しているので、データが絶えず挿入されると、resizeを使って配列の大きさを調整する必要があります.この方法を実現するには、まず新しい配列を作成し、元の配列のkeyとvalueを再挿入します.配列のサイズを変更する方法を次に示します.

/**
     *       
     * @param cap
     */
private void resize(int cap){
  LinearProbingHashST<Key, Value> t;
  t = new LinearProbingHashST<Key, Value>(cap);
  for (int i = 0; i < M; i++) {
    if (keys[i] != null){
      t.put(keys[i], values[i]);
    }
  }
  keys = t.keys;
  values = t.values;
  M = t.M;
}

削除削除削除にかかわる場合、keyに対応する位置をnullに直接置くことはできません.同じkeyのデータが5つハッシュテーブルに格納されている場合、3番目のデータを直接空にすると、4番目の5番目とデータが見つからないため、1つの要素を削除するには、右側のすべてのキーをハッシュテーブルに再挿入する必要があります.削除方法のコードを次に示します.

/**
     *     
     * @param key
     */
public void delete(Key key){
  //   key
  if (get(key)  == null){
    return;
  }

  int i = hash(key);

  //         
  while (!key.equals(keys[i])){
    i =  (i + 1) % M;
  }
  keys[i] = null;
  values[i] = null;

  //                        
  i =  (i + 1) % M;
  while (keys[i] !=  null){
    Key key1 = keys[i];
    Value value1 = values[i];
    keys[i] = null;
    values[i] = null;
    N--;
    put(key1, value1);
    i =  (i + 1) % M;
  }

  N--;

  if (N > 0 && N == M/8){
    resize(M/2);
  }

}

ハッシュ・テーブルの完全な実装を次に示します.

/**
 * @author linxi
 * @function            
 * @project   
 * @package   .   
 * @date 2020/7/21-12:32   
 */
public class LinearProbingHashST<Key, Value> {
    //      
    private int N;
    //    
    private int M;
    // 
    private Key[] keys;
    // 
    private Value[] values;

    public LinearProbingHashST(int cap) {
        this.M = cap;
        keys = (Key[]) new Object[M];
        values = (Value[]) new Object[M];
    }



    /**
     *      
     * @param key
     * @return
     */
    private int hash(Key key){
        // hashCode     0，      ，   M，       0～M-1  
        return (key.hashCode() & 0x7fffffff) % M;
    }

    /**
     *       
     * @param cap
     */
    private void resize(int cap){
        LinearProbingHashST<Key, Value> t;
        t = new LinearProbingHashST<Key, Value>(cap);
        for (int i = 0; i < M; i++) {
            if (keys[i] != null){
                t.put(keys[i], values[i]);
            }
        }
        keys = t.keys;
        values = t.values;
        M = t.M;
    }

    /**
     *     
     * @param key
     * @param value
     */
    public void put(Key key, Value value){
        //        1/2～1/8
        if (N >=  M/2) {
            resize(2*M);
        }

        int i;
        //i = (i + 1) % M  i    
        for (i = hash(key); keys[i] != null; i = (i + 1) % M) {
            if (keys[i].equals(key)){
                values[i] = value;
                return;
            }
        }
        keys[i] = key;
        values[i] = value;
        N++;
    }

    /**
     *     
     * @param key
     * @return
     */
    public Value get(Key  key){
        for (int i = hash(key); keys[i] != null; i = (i + 1) % M) {
            if (keys[i].equals(key)){
                return values[i];
            }
        }
        return null;
    }

    /**
     *     
     * @param key
     */
    public void delete(Key key){
        //   key
        if (get(key)  == null){
            return;
        }

        int i = hash(key);

        //         
        while (!key.equals(keys[i])){
            i =  (i + 1) % M;
        }
        keys[i] = null;
        values[i] = null;

        //                        
        i =  (i + 1) % M;
        while (keys[i] !=  null){
            Key key1 = keys[i];
            Value value1 = values[i];
            keys[i] = null;
            values[i] = null;
            N--;
            put(key1, value1);
            i =  (i + 1) % M;
        }

        N--;

        if (N > 0 && N == M/8){
            resize(M/2);
        }

    }
}

1.3.4ハッシュテーブルと他のアルゴリズムの比較
アルゴリズム#アルゴリズム#
最悪の場合のコスト(検索)
最悪の場合のコスト(挿入)
平均原価(検索)
平均の場合のコスト(挿入)
秩序性関連操作を効率的にサポートするかどうか
メモリ使用(バイト)
シーケンシャルルックアップ(シーケンシャルチェーンテーブル)シーケンシャルルックアップシーケンシャルチェーンテーブル
N
N
N/2
N
いいえ
48N
にぶんたんさく
lgN
2N
lgN
N
はい
16N
ツリー
N
N
1.39lgN
1.39lgN
はい
64N
2-3ツリーの検索(赤と黒)
2lgN
2lgN
1.00lgN
1.00lgN
はい
64N
ファスナーほう
N/(2M)
N/M
いいえ
48N+32M
せんけいプローブほう
clgN
clgN
<1.5
<2.5
いいえ
32N~128N