ハッシュテーブルは、キーと値のペアを格納し、平均的に定数時間O(1)でデータの検索、挿入、削除を行うことができる非常に効率的なデータ構造です。ここでは、ハッシュテーブルの特性を利用して計算量を削減し、アルゴリズムのパフォーマンスを最適化する代表的な問題について解説します。

有効なアナグラムの判定

2つの文字列がアナグラム（文字の並び替え）であるかどうかを判定する問題では、各文字の出現回数を比較する必要があります。配列の長さが等しいことを確認した後、辞書構造を使用して文字の頻度をカウントし、比較を行う手法が有効です。

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        char_counts = {}
        for char in s:
            char_counts[char] = char_counts.get(char, 0) + 1
            
        for char in t:
            if char not in char_counts or char_counts[char] == 0:
                return False
            char_counts[char] -= 1
            
        return True

2つの配列の共通集合

2つの整数配列に含まれる共通の要素を見つける問題では、重複する要素を除外し、高速な検索が可能である「セット（集合）」データ構造を利用するのが適切です。Pythonのセットはハッシュテーブルをベースとしているため、メンバーシップのテストが高速です。

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        seen = set(nums1)
        result = []
        for num in nums2:
            if num in seen:
                result.append(num)
                seen.remove(num) # 重複を避けるために削除
        return result

ハッピーナンバー

各桁の二乗の和を計算し続ける操作が1に到達するか、無限ループに陥るかを判定する問題です。この問題は、以前に出現した値を記録しておき、同じ値が再び現れた時点でループ（サイクル）が発生したとみなすことで解決できます。ここでもハッシュセットを利用して、既出の数値を管理します。

class Solution:
    def isHappy(self, n: int) -> bool:
        visited = set()
        while n != 1:
            if n in visited:
                return False
            visited.add(n)
            
            sum_squares = 0
            while n > 0:
                digit = n % 10
                sum_squares += digit * digit
                n //= 10
            n = sum_squares
            
        return True

2つの数の和

配列内の2つの数の和が特定のターゲット値と等しくなる組み合わせのインデックスを見つける問題です。全探索（二重ループ）では計算量がO(n^2)となってしまいますが、ハッシュテーブル（辞書）を使用して「ターゲット値から現在の数を引いた値（補数）」が既に登場したかを確認することで、計算量をO(n)に削減できます。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}
        
        for index, value in enumerate(nums):
            complement = target - value
            if complement in num_map:
                return [num_map[complement], index]
            
            num_map[value] = index
            
        return []