本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考に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"を表示しています。
前回で作成したハッシュ関数での衝突は回避されましたが、データ数に対してリストに十分な余裕が無ければ、探索に時間がかかるため、こちらもトレードオフの関係であると言えます。