ハッシュセット (Hash Set)とは?重複を排除するデータ構造

スポンサーリンク
ハッシュセット (Hash Set)とは重複を排除するデータ構造 データ構造

ハッシュセット (Hash Set)とは

ハッシュセット とは、

要素を重複なく管理するためのデータ構造

です。

 

ハッシュセットは以下のような特徴を持つデータ構造です。

ハッシュセットの基本的な特徴
  • 重複を許さない : setの中では、同じ要素を複数回追加しても一つしか保持されません。
  • 順序がない : 要素の順序は保持されません
  • 集合演算が可能 : 数学的な集合(和集合・積集合など)に基づく演算ができます。

set_重複を許さない

set_集合演算が可能

 

 

ハッシュセットの実装

ハッシュセットはハッシュテーブルを使って実装されます。

このハッシュテーブルを活用することで、高速な要素の追加・削除・検索が可能です。

実装(Python)

class Myset:
    def __init__(self):
        self.data = {}

    def add(self, value):
        self.data[value] = True

    def remove(self, value):
        if value in self.data:
            del self.data[value]
        else:
            raise KeyError("Value not found")

    def union(self, other_set):
        # 和集合の実装
        result = Myset()
        for value in self.data:
            result.add(value)
        for value in other_set.data:
            result.add(value)
        return result

    def intersection(self, other_set):
        # 積集合の実装
        result = Myset()
        for value in self.data:
            if value in other_set.data:
                result.add(value)
        return result

    def difference(self, other_set):
        # 差集合の実装
        result = Myset()
        for value in self.data:
            if value not in other_set.data:
                result.add(value)
        return result

# 使用例
set_A = Myset()
set_A.add(1)
set_A.add(2)
set_A.add(3)

set_B = Myset()
set_B.add(3)
set_B.add(4)
set_B.add(5)

print("A:", set_A.data)
print("B:", set_B.data)

print("A union B:", set_A.union(set_B).data.keys())
print("A intersection B:", set_A.intersection(set_B).data.keys())
print("A difference B:", set_A.difference(set_B).data.keys())
A: {1: True, 2: True, 3: True}
B: {3: True, 4: True, 5: True}
A union B: dict_keys([1, 2, 3, 4, 5])
A intersection B: dict_keys([3])
A difference B: dict_keys([1, 2])

 

標準ライブラリ(Python)

Pythonにはsetとしてハッシュセットが標準ライブラリに含まれています。

setを使用するとハッシュセットがより簡潔に実装できます。

set_A = set([1, 2, 3])
set_B = set([3, 4, 5])

print("A:", set_A)
print("B:", set_B)

print("A union B:", set_A.union(set_B))
print("A intersection B:", set_A.intersection(set_B))
print("A difference B:", set_A.difference(set_B))
A: {1, 2, 3}
B: {3, 4, 5}
A union B: {1, 2, 3, 4, 5}
A intersection B: {3}
A difference B: {1, 2}

 

参考文献

組み込み型 — Python 3.13.0 ドキュメント

コメント

タイトルとURLをコピーしました