ハッシュテーブルの使用方法を説明する前に、ハッシュ関数について説明します。ハッシュ関数は、与えられたキーから一意のハッシュ値を生成します。ハッシュ値は通常、ハッシュテーブル内のデータを格納するための配列のインデックスとして使用されます。ハッシュ関数は、キーのハッシュ値を計算するためのアルゴリズムです。
ハッシュテーブルの基本的な操作は、要素の挿入、検索、削除です。要素の挿入では、キーと値のペアをハッシュ関数を使用してハッシュ値に変換し、そのハッシュ値に対応する配列のインデックスに要素を格納します。ハッシュ関数が異なるキーに同じハッシュ値を生成する場合、ハッシュ衝突が発生します。ハッシュ衝突を解決するためには、異なるキーを同じハッシュ値にマッピングする方法が必要です。一般的な解決策は、チェイン法と呼ばれる方法で、各配列のインデックスにリンクリストを作成し、衝突した要素をリストに追加します。
要素の検索では、検索するキーをハッシュ関数に渡し、対応するハッシュ値を計算します。そのハッシュ値に対応する配列のインデックスにアクセスし、リスト内でキーが一致する要素を検索します。
要素の削除では、検索と同様にキーに対応するハッシュ値を計算し、そのハッシュ値に対応する配列のインデックスにアクセスします。リスト内でキーが一致する要素を削除します。
ハッシュテーブルは、一般的に高速なデータアクセスを提供します。ハッシュ関数の選択や衝突解決の方法によって、ハッシュテーブルの効率性が異なる場合があります。
以下に、Pythonのコード例を示します。
class HashTable:
def __init__(self):
self.size = 10
self.table = [[] for _ in range(self.size)]
def _hash_function(self, key):
return key % self.size
def insert(self, key, value):
index = self._hash_function(key)
self.table[index].append((key, value))
def search(self, key):
index = self._hash_function(key)
for k, v in self.table[index]:
if k == key:
return v
return None
def delete(self, key):
index = self._hash_function(key)
for i, (k, v) in enumerate(self.table[index]):
if k == key:
del self.table[index][i]