Section 11 / 13
ハッシュ関数とハッシュテーブルの基本
ハッシュ関数とハッシュテーブルは、データの迅速な検索や保存を実現するための非常に重要なデータ構造とアルゴリズムです。この教材では、ハッシュ関数とハッシュテーブルの基本的な概念を理解し、Pythonでの実装を通じてその動作を学びます。
ハッシュ関数とは
ハッシュ関数は、入力データ（通常は文字列や数値）を固定長のハッシュ値に変換する関数です。このハッシュ値は、元のデータの特徴を反映しており、異なるデータが同じハッシュ値を生成する可能性（ハッシュ衝突）があります。
ハッシュ関数の特性
- 一方向性: 入力からハッシュ値を計算するのは容易ですが、ハッシュ値から元の入力を逆算することは非常に困難です。
- 固定長出力: 入力の長さに関わらず、出力は固定のサイズです。
- 衝突耐性: 異なる入力が同じハッシュ値を生成する可能性があるが、良いハッシュ関数はその確率を低く保つ。
ハッシュテーブルとは
ハッシュテーブルは、データを効率的に格納・検索するためのデータ構造です。データをキーと値のペアとして格納し、キーを使って値を迅速に取得します。ハッシュテーブルは、内部的に配列を使用し、ハッシュ関数を使ってキーをインデックスに変換します。
ハッシュテーブルの基本的な操作
- 挿入: 新しいキーと値のペアをハッシュテーブルに追加します。
- 検索: 指定したキーに関連付けられた値を取得します。
- 削除: 指定したキーとその関連値をハッシュテーブルから削除します。
Pythonによるハッシュテーブルの実装
以下は、ハッシュ関数とハッシュテーブルの基本的な実装の例です。
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [None] * size
def _hash(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash(key)
self.table[index] = value
def search(self, key):
index = self._hash(key)
return self.table[index]
def delete(self, key):
index = self._hash(key)
self.table[index] = None
# 実装をテスト
if __name__ == "__main__":
hash_table = HashTable()
# データの挿入
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("orange", 3)
# データの検索
print("apple:", hash_table.search("apple")) # 出力: apple: 1
print("banana:", hash_table.search("banana")) # 出力: banana: 2
# データの削除
hash_table.delete("apple")
print("apple:", hash_table.search("apple")) # 出力: apple: None
コード解説
-
クラス定義:
HashTableクラスを定義し、コンストラクタでハッシュテーブルのサイズを設定します。self.tableは、指定したサイズの空のリストを作成します。 -
ハッシュ関数:
_hashメソッドを定義し、Pythonの組み込み関数hash()を使用してキーをハッシュ化し、テーブルのサイズで剰余を取ることでインデックスを計算します。 -
挿入メソッド:
insertメソッドは、指定されたキーのハッシュ値を計算し、そのインデックスに値を格納します。 -
検索メソッド:
searchメソッドは、指定されたキーのハッシュ値を計算し、そのインデックスから値を取得します。 -
削除メソッド:
deleteメソッドは、指定されたキーのハッシュ値を計算し、そのインデックスの値をNoneに設定します。 -
テスト: メインブロックでハッシュテーブルを作成し、いくつかのデータを挿入、検索、削除を行います。
このように、ハッシュ関数とハッシュテーブルを使用することで、効率的なデータの格納と検索が可能になります。次回は、ハッシュ衝突の解決法に焦点を当てていきます。