まず、ハッシュテーブルの基本的な仕組みについて説明します。ハッシュテーブルは、キーと値のペアを格納するためのデータ構造であり、ハッシュ関数を使ってキーをハッシュ値に変換します。ハッシュ値は、配列のインデックスとして使用され、値はそのインデックスに格納されます。これにより、データの追加、検索、削除が高速に行えます。
次に、クアドラティックプロービング法について説明します。クアドラティックプロービングは、ハッシュテーブルで発生する衝突（複数のキーが同じハッシュ値を持つ場合）を解決するための手法の一つです。クアドラティックプロービングでは、ハッシュ値に一定のオフセットを加えて、次の利用可能なインデックスを見つけるまで探索します。具体的な手順は以下の通りです。
- キーのハッシュ値を計算する。
- ハッシュ値をハッシュテーブルのサイズで割り、インデックスを求める。
- インデックスがすでに使用されている場合、クアドラティックプロービングを行う。
- クアドラティックプロービングでは、オフセットを加えた次のインデックスを計算する。オフセットは、通常はインデックスの二乗を使用する。
- 次のインデックスが利用可能であるかを確認する。利用可能であれば、そのインデックスに値を格納する。利用不可であれば、再度クアドラティックプロービングを行う。
- 上記の手順を繰り返し、利用可能なインデックスが見つかるまで探索を続ける。
以上がクアドラティックプロービング法の基本的な手順です。実際のコード例を示します。
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def quadratic_probing(self, index, i):
return (index + i2) % self.size
def insert(self, key, value):
index = self.hash_function(key)
i = 0
while self.table[index] is not None:
index = self.quadratic_probing(index, i)
i += 1
self.table[index] = (key, value)
def search(self, key):
index = self.hash_function(key)
i = 0
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = self.quadratic_probing(index, i)
i += 1
return None
def delete(self, key):
index = self.hashfunction(key)
i = 0
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = None
return
index = self.quadratic_probing(index, i)
i += 1
# ハッシュテーブルの使用例
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("orange", 3)
print(hash_table.search("banana")) # Output: 2
hash_table.delete("banana")
print(hash_table.search("banana")) # Output: Noneこのコード例では、クラスHashTableがハッシュテーブルの実装を担当しています。__init__メソッドでは、指定されたサイズの配列を作成し、ハッシュ関数hash_functionとクアドラティックプロービング関数quadratic_probingも定義されています。
insertメソッドでは、キーと値のペアをハッシュテーブルに挿入します。衝突が発生した場合は、クアドラティックプロービングを行い、利用可能なインデックスを探索します。
searchメソッドでは、指定されたキーに対応する値を検索します。衝突が発生した場合も、クアドラティックプロービングを行い、対応する値を見つけます。
deleteメソッドでは、指定されたキーに対応するエントリを削除します。
上記のコード例を使用することで、クアドラティックプロービングを使ったハッシュテーブルの実装方法を理解し、自身でカスタマイズや応用を行うことができます。