Java プログラミングスキル - データ構造とアルゴリズム「ハッシュテーブル」

[[388064]]

基本的な紹介

ハッシュテーブル (ハッシュテーブルとも呼ばれます) は、キー値に基づいて直接アクセスされるデータ構造です。つまり、キーコード値をテーブル内の場所にマッピングしてレコードにアクセスし、検索を高速化します。このマッピング関数はハッシュ関数と呼ばれ、レコードを格納する配列はハッシュテーブルと呼ばれます。

Google コンピュータに関する質問

ある会社では、新入社員が仕事に報告するときに、新入社員の情報（ID、性別、年齢、住所など）を追加することを求めています。社員のIDを入力すると、その社員のすべての情報が検索される必要があります。

要件: データベースを使用せず、メモリを可能な限り節約し、高速であるほど良いです。

パッケージ com.xie.hashtable; 
 
 java.util.Scanner をインポートします。 
 
パブリッククラスHashTableDemo {
公共 静的void main(String[] args) {
        //ハッシュタブを作成する
        ハッシュタブ hashTab = new HashTab(7); 
 
        文字列キー= "" ;
        スキャナー scanner = new Scanner( System.in );
        （真）の間{
            System.out.println ( "add: 従業員を追加" );
            System.out.println ( "list:従業員を表示" ) ;
            System.out.println ( "find: 従業員を検索" );
            System.out.println ( "delete: 従業員を削除します" );
            System.out.println ( "exit: プログラムを終了" );
キー= スキャナ.next ( );
            スイッチ（キー）{
場合  "追加" ：
                    System.out.println ( "入力ID" ) ;
 int id = スキャナー.nextInt();
                    System.out.println ( "入力名" ) ;
                    文字列名= scanner.next ( );
                    Emp emp = 新しい Emp(id、名前);
                    hashTab.add (emp);
                    壊す;
場合  「リスト」 :
                    ハッシュタブのリスト();
                    壊す;
場合  "探す" ：
                    System.out.println ( "番号を入力してください" );
整数 いいえ= scanner.nextInt();
                    hashTab.findEmpById(なし);
                    壊す;
場合  "消去" ：
                    System.out.println ( "番号を入力してください" );
 int deleteNo = スキャナ.nextInt();
                    hashTab.deleteEmpById(deleteNo);
                    壊す;
場合  "出口" ：
                    スキャナーを閉じます() ;
                    システム終了(0);
                    壊す;
デフォルト：
                    壊す;
            }
        }
    }
 } 
 
 // 複数のリンクリストを管理するためのハッシュテーブルを作成する
クラスHashTab{
    プライベートint  サイズ;
    プライベートEmpLinkedList[] empLinkedListArray; 
 
パブリックハッシュタブ( int  サイズ） {
        this.size =サイズ;
        empLinkedListArray = 新しいEmpLinkedList[サイズ];
 ( int i = 0; i <サイズ; i++) {
            empLinkedListArray[i] = 新しいEmpLinkedList();
        } 
 
    } 
 
    //従業員を追加
パブリックvoidを追加します(Emp emp) {
        //従業員のIDに応じて、従業員を追加するリンクリストを取得します
int empLinkedListNo = hashFun(emp.id);
        // empを対応するリンクリストに追加します
        empLinkedListArray[empLinkedListNo] .add (emp);
    } 
 
    //従業員を探す
パブリックEmp findEmpById( int id) {
整数 いいえ= hashFun(id);
        Emp empById = empLinkedListArray[ no ].findEmpById(id);
        empByIdがnullの場合
            System.out.println ( "id=" + id + "要素"は存在しません" );
戻る ヌル;
        }それ以外{
            System.out.println ( " existsid =" + id + ",name=" + empById.name );
 empByIdを返します。
        }
    } 
 
    //従業員を削除
パブリックvoid deleteEmpById( int id) {
整数 いいえ= hashFun(id);
        empLinkedListArray[ no ].deleteEmp(id);
    } 
 
    //ハッシュテーブルを走査する
パブリックボイドリスト（）{
 ( int i = 0; i <サイズ; i++) {
            empLinkedListArray[i].list(i);
        }
    } 
 
    //単純な係数法を使用してハッシュ関数を記述します
    プライベートint hashFun( int id) {
 id % sizeを返します。
    } 
 
 } 
 
 // 従業員を表す
クラス Emp {
公共 整数ID;
パブリック文字列名;
パブリックEmp次; 
 
パブリックEmp( int id, String name ) {
        id は、
        this.name =名前;
    } 
 
    @オーバーライド
パブリック文字列toString() {
戻る  「エンプ{」 +
 "id=" + id +
 ", 名前='" +名前+ '\ '' +
 '}' ;
    }
 } 
 
 //リンクリストを表す
クラス EmpLinkedList {
    //ヘッドポインタ
    プライベートエンプヘッド; 
 
    //リンクリストに従業員を追加する
    //説明:
    //1. 従業員を追加すると、IDは自動的に増加します。つまり、IDの割り当ては常に小さいものから大きいものへと進むため、従業員をこのリンクリストの末尾に直接追加するだけです。
パブリックvoidを追加します(Emp emp) {
        //最初の従業員を追加する場合
        ヘッドがnullの場合
            ヘッド = emp;
        }それ以外{
            Emp curr = ヘッド;
            （真）の間{
                （ curr.next == nullの場合）{
                    壊す;
                }
                curr = curr.next ;
            }
            emp の次の行にポインターを置きます。
        }
    } 
 
    //トラバース
パブリックvoid リスト( int  いいえ） {
        ヘッドがnullの場合
            System.out.println ( "No." +( no +1)+ "リンクリストは空です" ) ;
戻る;
        }
        System.out.print ( "No." +( no +1)+ "リンクリストの情報は次のとおりです:" );
        Emp curr = ヘッド;
        （真）の間{
            （カレントがnullではない場合）
                システム.out.printf ( "=>id=%d,name=%s\t" 、curr.id、curr.name ) ;
                curr = curr.next ;
            }それ以外{
                壊す;
            }
        }
        System.out.println( ) ;
    } 
 
    //IDで従業員を検索
パブリックEmp findEmpById( int id) {
        ヘッドがnullの場合
            System.out.println ( "リンクリストは空です" ) ;
戻る ヌル;
        }
        Emp temp = ヘッド;
        while ( temp != null ) {
            if ( temp .id == id) {
戻る 温度;
            }
 temp = temp . next ;
        }
戻る ヌル;
    } 
 
    //IDで従業員を削除
パブリックvoid deleteEmp( int id) {
        ヘッドがnullの場合
            System.out.println ( "id=" +id+ "の従業員は存在しません" );
戻る;
        }
        Emp curr = ヘッド;
        ブールフラグ = false ;
        （真）の間{
            （カレントがnullの場合）
                壊す;
            }
            （ curr.next.id == id）の場合{
                フラグ = true ;
                壊す;
            }
            curr = curr.next ;
        }
        if (フラグ) {
            curr.next = curr.next . next ;
        }それ以外{
            System.out.println ( "id=" +id+ "の従業員は存在しません" );
        }
    } 
 
 }