本記事は、ソフトバンクパブリッシングから発行されている「」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、前回学んだハッシュ法（Hashing）の衝突を回避するチェイン法について学んでいきます。
チェイン法とは
チェイン法（Chaining）とは、同じハッシュ値を持つデータが存在した場合に、連結リストとして繋いでいく方式を言います。
チェイン法においては、例えばリスト（バケット）のサイズをB、データの数をNとした場合、リストのインデックスを探索するにはO(1)の計算量で済みますが、連結リストを線形探索しなければならないため、全体の計算量はO(1 + N/B)になります。
また、データの数に比べてリストのサイズが十分に大きい場合はN/Bは定数をみなせる為、計算量はO(1)で済みます。
しかし、データの数に比べてリストのサイズが極端に小さい場合には、O(N)の計算量になってしまいます。
Pythonでチェイン法を実装してみる
それでは、Pythonでチェイン法を実装してみます。
# chain.py
class Cell:
def __init__(self, value):
self.value = value
self.next = None
class HashTable:
def __init__(self, size):
self.size = size
self.values = [None for _ in range(size)]
def my_hash(self, value):
length = 0
for c in value:
length += ord(c)
return length % self.size
def find(self, target):
hash = self.my_hash(target)
tmp = self.values[hash]
while tmp:
if tmp.value == target:
return tmp
else:
tmp = tmp.next
continue
return None
def insert(self, value):
try:
if self.find(value):
print('[*] value already exists.')
return False
hash = self.my_hash(value)
tmp = self.values[hash]
self.values[hash] = Cell(value)
self.values[hash].next = tmp
return True
except:
print("[*] Failed to insert.")
return False
def delete(self, value):
hash = self.my_hash(value)
cell = self.values[hash]
if not cell:
print("Data not found.")
return False
elif cell.value == value:
self.values[hash] = cell.next
print('[*] Successfully deleted.')
return True
next = cell.next
while next:
if next.value == value:
cell = next.next
next = None
print('[*] Successfully deleted.')
return True
elif next.next:
cell = next
next = next.next
print("Data not found.")
return False
table = HashTable(100)
table.insert('one')
table.insert('neo')
table.insert('one')
data = table.find('neo')
print(data.value)
print(data.next.value)
作成したHashTableクラスは、リストのサイズで初期化します。
insert()では、データの重複が無いか確認し、連結リストの先頭に挿入していきます。
delete()では、リストの先頭が削除すべきデータであるか確認してから、2番目以降のセルについて順番に確認をしていきます。
動作確認
それでは上記で作成したスクリプトを実行してみます。
> python chain.py [*] value already exists. neo one
上記では、まず"one"と"neo"という同じハッシュ値を持つデータを挿入します。
再度"one"を挿入しようとすると重複エラーが発生します。
その後、"neo"を探索しその結果を表示してから、さらにcellをたぐり寄せて"one"を表示しています。
前回で作成したハッシュ関数での衝突は回避されましたが、データ数に対してリストに十分な余裕が無ければ、探索に時間がかかるため、こちらもトレードオフの関係であると言えます。
参考書籍
定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)
