ハッシュセット (Hash 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}
コメント