平方探测法の実装と注意点：ハッシュテーブル衝突解決の深層

ハッシュテーブルにおける衝突処理手法として、平方探査法はその特異な動作特性から多くの場面で採用されています。この手法は単なる線形探索とは異なり、特定の数列パターンを用いたジャンプ型検索を行うことで、データ構造の効率的な運用を実現します。しかし、実装時にはいくつかの落とし穴に注意が必要です。

平方探査法の数学的基盤

平方探査法はオープンアドレッシング方式の一種であり、衝突発生時に固定間隔ではなく、平方数に基づく可変間隔で空き位置を探します。探査シーケンスは以下のように表現されます：

d_i = 0, +1, -1, +4, -4, +9, -9, ..., +k², -k²

ここでkは探査回数、mはハッシュテーブルのサイズです。この数列の特徴は、初期位置を中心に左右対称に探査範囲を広げることにあります。

探査位置の計算式は以下の通りです：

H_i = (H(key) + d_i) mod m

負の値が発生する場合、適切な処理が必要になります。以下はその実装例です：

def calculate_probe_position(initial_hash, iteration, table_size):
    """探査位置を計算する関数"""
    square_value = ((iteration + 1) // 2) ** 2
    if iteration % 2 == 1:
        square_value = -square_value
    
    position = (initial_hash + square_value) % table_size
    # 負数の場合は正規化
    if position < 0:
        position += table_size
    return position

Pythonによる完全実装

以下は平方探査法を用いたハッシュテーブルの完全な実装です：

class SquareProbeHashTable:
    """平方探査法を使用したハッシュテーブル"""
    
    def __init__(self, capacity=13):
        """
        コンストラクタ
        Args:
            capacity: テーブル容量（素数推奨）
        """
        self.capacity = capacity
        self.storage = [None] * capacity
        self.removed_flags = [False] * capacity  # 削除済みフラグ
        self.element_count = 0
    
    def hash_function(self, key):
        """基本的なハッシュ関数"""
        return key % self.capacity
    
    def locate_position(self, target_key):
        """
        キーに対応する位置を検索
        Returns: (位置, 発見フラグ)
        """
        base_hash = self.hash_function(target_key)
        
        for attempt in range(self.capacity):
            offset = self.square_offset(attempt)
            current_pos = (base_hash + offset) % self.capacity
            
            if self.storage[current_pos] is None or self.removed_flags[current_pos]:
                if not self.removed_flags[current_pos]:
                    return current_pos, False
                else:
                    continue  # 削除済み位置をスキップ
            
            if self.storage[current_pos] == target_key and not self.removed_flags[current_pos]:
                return current_pos, True
        
        return -1, False  # テーブル満杯
    
    def square_offset(self, attempt):
        """平方オフセットを計算"""
        squared_num = ((attempt + 1) // 2) ** 2
        return squared_num if attempt % 2 == 0 else -squared_num
    
    def add_element(self, key):
        """要素追加メソッド"""
        load_factor = self.element_count / self.capacity
        if load_factor > 0.6:
            self.resize_table()
        
        pos, exists = self.locate_position(key)
        
        if pos == -1:
            raise OverflowError("テーブル容量超過")
        
        if not exists:
            self.storage[pos] = key
            self.removed_flags[pos] = False
            self.element_count += 1
            return True
        return False  # 既存要素
    
    def find_element(self, key):
        """要素検索"""
        _, found = self.locate_position(key)
        return found
    
    def remove_element(self, key):
        """要素削除（論理削除）"""
        pos, exists = self.locate_position(key)
        
        if exists:
            self.removed_flags[pos] = True
            self.element_count -= 1
            return True
        return False
    
    def resize_table(self):
        """テーブル再構成"""
        previous_storage = self.storage[:]
        previous_flags = self.removed_flags[:]
        
        new_capacity = self.find_next_prime(self.capacity * 2)
        self.capacity = new_capacity
        self.storage = [None] * new_capacity
        self.removed_flags = [False] * new_capacity
        self.element_count = 0
        
        for idx in range(len(previous_storage)):
            if previous_storage[idx] is not None and not previous_flags[idx]:
                self.add_element(previous_storage[idx])
    
    def find_next_prime(self, number):
        """次の素数を探索"""
        def check_prime(value):
            if value < 2:
                return False
            for divisor in range(2, int(value ** 0.5) + 1):
                if value % divisor == 0:
                    return False
            return True
        
        while not check_prime(number):
            number += 1
        return number

実装上の重要な考慮事項

この実装では以下の点に特に注意しています：

• 削除フラグ管理：物理的な削除を行うと探査パスが破壊されるため、削除済みフラグで論理削除を実現しています。
• 負荷率制御：負荷率が0.6を超えると再構成を実行し、性能維持を図ります。
• テーブルサイズ選択：4k+3形式の素数を選択することで、すべての位置が探査可能になることを保証します。

二次クラスタリング問題

平方探査法は線形クラスタリングを軽減する一方で、異なるキーが同じ探査シーケンスを持つことによる二次クラスタリングという新たな課題を抱えています。これは異なる初期位置を持つキーが特定の位置で交差し、結果としてこれらの位置が新たなクラスタとなる現象です。

例えば、異なるハッシュ値を持つ複数のキーが同じ位置で衝突すると、それ以降の探査パスが一致する可能性があります。このような場合、効率的なデータ配置が困難になり、パフォーマンスが低下する可能性があります。