【アルゴリズム】ハッシュ法｜基本情報技術者科目B対策

2023年4月から基本情報技術者の試験制度が変更されたものの科目B（旧：午後問題）の重要さは変わりません。

出題方式は「多肢選択式」で以前と同じですが、データ構造及びアルゴリズムが8割、情報セキュリティが2割の割合で出題される点が大きく変わっています。

合格基準点は600点以上/1000点満点中、つまり6割以上取れれば合格になります。

そんな科目Bのデータ構造及びアルゴリズムについて、基本となる探索の問題について考えてみましょう。

探索アルゴリズムとは？？
ハッシュ法とは？？
どんなときに使う？
ハッシュ法の実装例（プログラム）
まとめ

探索アルゴリズムとは？？

配列のようなデータの集合から目的の値をを持った要素を探し出すアルゴリズムのことを言います。

何らかの項目（属性）に着目して探索を行います。このとき、着目する項目を「キー」と呼びます。例えば、年齢に着目して探索を行う場合、キーは年齢ということになります。

＜探索アルゴリズム例＞

・線形探索

・２分探索

・ハッシュ法　　等

ハッシュ法とは？？

ハッシュ法（Hashing）は、データの高速な検索や識別を目的として使用されるデータ構造の一つです。ハッシュ法では、データを一定のサイズのハッシュ値（ハッシュコード）に変換し、そのハッシュ値を使ってデータを格納・検索します。

例えば、配列から探索する手順は下記のようになる。

データに対してハッシュ関数を適用してハッシュ値を計算します。ハッシュ関数は、データから一意のハッシュ値を生成するための算術的な処理です。
ハッシュ値を用いてデータを格納するデータ構造（ハッシュテーブルやハッシュマップ）にデータを配置します。ハッシュ値をインデックスとして使用し、データを格納するバケット（格納場所）を決定します。
データを検索する際にも、同じハッシュ関数を使用して対応するハッシュ値を計算し、そのハッシュ値を持つバケットからデータを取得します。

このため、ハッシュ法ではデータの検索速度が高速である特徴があります。

どんなときに使う？

ハッシュ法は、データの格納と検索において高速な処理を提供するため、データベースやキャッシュメモリ、パスワードの保存などさまざまな応用分野で利用されています。ただし、ハッシュ関数の選択や衝突（複数のデータが同じハッシュ値を持つ状況）の処理など、適切な設計と実装が必要となります。

ハッシュ法の実装例（プログラム）

実装例は下記です。

Web上で実際にプログラムを動かすことができるサイトがあります。

色々プログラムをいじってみましょう！

Online PHP/Java/C++... editor and compiler | paiza.IO

＜実装例＞

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        // ハッシュテーブルの作成
        HashMap<String, Integer> hashTable = new HashMap<>();

        // データの追加
        hashTable.put("Apple", 10);
        hashTable.put("Banana", 20);
        hashTable.put("Orange", 30);

        // データの検索
        int appleValue = hashTable.get("Apple");
        System.out.println("Apple: " + appleValue);

        int bananaValue = hashTable.get("Banana");
        System.out.println("Banana: " + bananaValue);
        
        int orangeValue = hashTable.get("Orange");
        System.out.println("Orange: " + orangeValue);

        // データの削除
        hashTable.remove("Orange");

        // 存在しないデータの検索
        Integer grapesValue = hashTable.get("Grapes");
        if (grapesValue == null) {
            System.out.println("Grapes not found");
        }
    }
}