Engineering Note

プログラミングなどの技術的なメモ

チェイン法 (Pythonによるアルゴリズムとデータ構造)

chain

本記事は、ソフトバンクパブリッシングから発行されている「定本 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"を表示しています。

前回で作成したハッシュ関数での衝突は回避されましたが、データ数に対してリストに十分な余裕が無ければ、探索に時間がかかるため、こちらもトレードオフの関係であると言えます。

 

参考書籍

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)