Javaでのハッシュテーブルの実装と検索方法

2024.08.27

ハッシュテーブルは、効率的なデータの格納と検索を実現するために広く使用されるデータ構造です。この記事では、Javaでハッシュテーブルを実装し、特定の値を検索する方法を紹介します。

問題の概要

以下のようなコードで、配列を使ってハッシュテーブルを実装しようとしたとき、うまく動作しないことがあります。

public static void main(String[] args) throws Exception {
    int[] nums = {1, 3, 5, 6, 7, 10, 20};
    int[] hashNums = new int[nums.length];
    
    for(int i=0; i<hashNums.length; i++){
        int hashNum = nums[i] % 7;
        hashNums[hashNum] = nums[i];
        System.out.println(hashNums[hashNum] + " ");
    }
    
    // 検索したい値
    int val = 5;
    int valHash = val % 7;
    System.out.println("検索値:" + valHash + " 添え字:" + valHash);
}





このコードでは、同じハッシュ値に対して複数の値が格納される可能性があるため、正しくハッシュ検索ができません。





解決方法：リストを使用した衝突解決





ハッシュテーブルの衝突を避けるためには、各ハッシュ値に複数の値を格納できるようにする必要があります。ここでは、ArrayList を使用して実装する方法を紹介します。





ArrayListを使用したハッシュテーブルの実装





以下のコードは、ArrayList を使ってハッシュテーブルを実装し、値を格納する例です。





import java.util.ArrayList;

public static void main(String[] args) throws Exception {
    int[] nums = {1, 3, 5, 6, 7, 10, 20};
    ArrayList<Integer>[] hashTable = new ArrayList[7]; // 7はハッシュテーブルのサイズ

    // 初期化
    for (int i = 0; i < hashTable.length; i++) {
        hashTable[i] = new ArrayList<>();
    }

    // ハッシュテーブルへの格納
    for (int i = 0; i < nums.length; i++) {
        int hashNum = nums[i] % 7;
        hashTable[hashNum].add(nums[i]);
    }

    // ハッシュテーブルの内容を表示
    for (int i = 0; i < hashTable.length; i++) {
        System.out.println("Index " + i + ": " + hashTable[i]);
    }

    // 検索したい値
    int val = 5;
    int valHash = val % 7;
    if (hashTable[valHash].contains(val)) {
        System.out.println("検索値: " + val + " はハッシュテーブルのインデックス " + valHash + " に存在します。");
    } else {
        System.out.println("検索値: " + val + " はハッシュテーブルに存在しません。");
    }
}











コードのポイント





    

  1. 初期化: ArrayList の配列を作成し、各インデックスに空のリストを初期化します。
    2. 




  2. 値の格納: 配列 nums の各値に対してハッシュ値を計算し、そのハッシュ値に対応する ArrayList に値を追加します。
    3. 




  3. 検索: 検索したい値に対してハッシュ値を計算し、対応する ArrayList にその値が存在するかどうかを確認します。
    4. 






結果





この方法を用いることで、ハッシュ値が衝突した場合でも、値を正しく格納および検索できるようになります。





結論





ArrayList を使用することで、ハッシュテーブル内で同じインデックスに複数の値を持つことができ、衝突を効果的に処理できます。Javaでハッシュテーブルを実装する際には、データの格納方法と検索方法を考慮することが重要です。