Zenn
🐎

Python で学ぶハッシュ探索法 - チェーン法とオープンアドレス法 -

2023/03/08に公開
Python
アルゴリズム
ハッシュ法
チェーン法
オープンアドレス法
tech

ハッシュ法は、ソート済みリストからの探索だけでなく、データの追加や削除も効率よく行う手法です。

ソート済みリスト（List A）に新たにデータ（12）を追加する場面を考えます。この時の操作は以下のようになります。

  1. データを挿入すべき位置を特定する
  2. 挿入位置よりも後ろにあるデータを全て1つずつ後方にずらす
  3. データを挿入する

    単に新規にデータを追加するコストは決して小さくありません。データ削除も同様です。

ハッシュ法

ハッシュ法は、データ追加や削除を効率よく行う手法になります。具体的には、データの剰余（ハッシュ値と呼ぶ）を元にリストを作成・管理する方法です。

  1. リストに入っているデータと挿入するデータを 10 で割った時の剰余を求めます。ある数値を 10 で割った時の剰余は 0 から 9 の 10 通りです。
  2. 各剰余に対応するハッシュ表を作成します（ハッシュ表の各要素をバケット（bucket）と呼びます）。
  3. 新規に追加するデータ（14）の剰余は 4 なので、ハッシュ表の 4 に対応するバケットに挿入します。データを追加する際には、あらかじめ用意したハッシュ表にデータを追加するだけなので、既存のデータを移動させる必要がありません。

衝突

さらに、15 を追加してみましょう。15 を 10 で割った剰余は 5 なので、5 のバケットに追加しようとしますが、そのバケットには既にデータが入っています。このように格納すべきバケットが重複することを衝突と言います。

衝突が発生したときの対処方法として、以下に示す2つの方法があります。

  1. チェーン法
    同一のハッシュ値を持つ要素を線形リストで管理する
  2. オープンアドレス法
    空きバケットを見つけるまでハッシュを繰り返す

チェーン法（オープンハッシュ法）

チェーン法は、同じハッシュ値を持つデータを鎖（チェーン）状に線形リストで繋ぐ方法です。例えば、2, 12, 32 は同じ剰余「2」のバケットに属しています。「２」のバケットは、バケットに最初に追加された 2 のポインタが格納されています。そして、2 には　12 のポインタが後続のオブジェクトとして登録されています。

各データを表すノード（Node）とチェーン法を実現するクラス（ChainHash）を Python で表したものを以下に示します。ノードは、データと後続ノードのポインタを持ちます。

class Node
    """
    各データを表すノードクラス
    """
    def __init__(self, key, value, next):
        self.key = key 　　　　　　　　# データ（数値）
	self.next = next   # 後続ノードへのポインタ
	
class ChainHash
    """
    チェーン法を実現するクラス
    """
    def __init__(self):
        self.capacity = 10 # ハッシュ表のサイズ
	self.hash_table = [None] * self.capacity # ハッシュ表
	
    def hashing(self, key):
        """
	ハッシュ値（剰余）を求める
	"""
	return key % self.capacity
	
    def add(self, key):
        """
	データを追加する
	"""
	hash = self.hashing(key)
	p = self.hash_table[hash]
	
	if p is None:
	    # 対応するバケットに 1 つもデータが入っていない場合
	    node = Node(key, None)
	    self.hash_table[hash] = node
	    return True
	
	else:
	    while p is not None:
	        if p.key == key:
	            # 既に同じデータが格納されている
	            return False
	        p = p.next
	
	    node = Node(key, None)
	    p.next = node
	    return True

データを追加する（add 関数）時は、まずデータの剰余を求めてハッシュ表を確認します。対応するバケットにまだデータが1つも追加されていない場合、今回追加するデータを使ってノードを作成してバケットに追加して終了します。

バケットに既に1つでもデータが格納されている場合、そのバケットの終端ノードを while 文で検索しています。終端ノードの next を新しく追加するノードに変更することで、新しいデータがバケットの終端に結合したことになります。

データの検索

チェーン法のデータ検索について Python で実装した例を以下に示します。検索対象の剰余を求めて、対応するバケットの中身を1つずつ走査しています。

class ChainHash:
    ...
    
    def search(self, key):
        hash = self.hashing(key)
	p = self.hash_table[hash]
	
	while p is not None:
	    if p.key == key:
	        return p
	    p = p.next
	
	return None # 検索失敗

データの削除

チェーン法のデータ削除について Python で実装した例を以下に示します。まずは、対象のノードを検索します。その後、そのノードを next で参照しているノードに修正を加えます。具体的には、next を削除ノードの next に変更しています。

class ChainHash:
    ...
    
    def delete(self, key):
        hash = self.hashing(key)
	p = self.hash_table[hash]
	pre_node = None
	
	while p is not None:
	    if p.key == key:
	        if pre_node is None:
		    self.hash_table[hash] = p.next
		else:
	            pre_node.next = p.next
		return True
	    pre_node = p
	    p = p.next
	
	return False # 失敗（削除対象が存在しない）

オープンアドレス法

オープンアドレス法は、同じバケットに衝突したときに再ハッシュを行うことで、空いているバケットを探し出す手法です。クローズドハッシュ法とも呼ばれます。再ハッシュ関数は自由に設定することができます。例えば、「元の値に 1 を加えてからハッシュ計算をする」です。

15 を追加しようとしていますが、５ のバケットには既にデータが格納されているため、挿入できません。そこで、15 + 1 のハッシュ値である 6 のバケットにデータを格納します。

オープンアドレス法での、データの検索と削除は少し面倒です。単に、挿入データのハッシュ値を検索するだけでなく、データの再ハッシュについても検索する必要があるからです。

Discussion