Python에서 HashSet 설계

내장된 해시 테이블 라이브러리를 사용하지 않고 HashSet 데이터 구조를 설계한다고 가정합니다. −

• add(x) - HashSet에 값 x를 삽입합니다.
• contains(x) - 값 x가 HashSet에 있는지 여부를 확인합니다.
• remove(x) - HashSet에서 x를 제거합니다. HashSet에 값이 없을 경우 아무 것도 하지 마십시오.

따라서 테스트하려면 해시 세트를 초기화한 다음 add(1), add(3), contains(1), contains(2), add(2), contains(2), remove(2), contains(2)를 호출하십시오. ). 그러면 출력은 각각 true(1이 있음), false(2가 없음), true(2가 있음), false(2가 없음)가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• Bucket이라는 데이터 구조를 하나 정의하고 아래와 같이 초기화합니다.
• 버킷:=새 목록
• update() 함수를 정의합니다. 열쇠가 필요합니다
• 찾음 :=거짓
• 버킷의 각 인덱스 i와 키 k에 대해 다음을 수행합니다.
  • 키가 k와 같으면
    • 버킷[i]:=키
    • 찾음:=사실
    • 루프에서 나오다
  • 거짓으로 판명되면
    • 버킷 끝에 키 삽입
• get() 함수를 정의합니다. 이것은 key
  가 필요합니다.
  • 버킷의 각 k에 대해 다음을 수행합니다.
    • k가 키와 같으면
      • 참 반환
    • 거짓을 반환
• remove() 함수를 정의합니다. 이것은 key
  가 필요합니다.
  • 버킷의 각 인덱스 i와 키 k에 대해 다음을 수행합니다.
    • 키가 k와 같으면
      • 버킷 삭제[i]
• 이제 사용자 정의 hashSet을 만듭니다. 다음과 같은 몇 가지 방법이 있습니다.
• 다음과 같이 초기화하십시오 -
• key_space :=2096
• hash_table:=key_space 크기의 버킷 유형 개체 목록
• add() 함수를 정의합니다. 이것은 key
  가 필요합니다.
  • hash_key:=키 모드 key_space
  • hash_table[hash_key]의 업데이트(키) 호출
• remove() 함수를 정의합니다. 이것은 key
  가 필요합니다.
  • 해시_키:=키모드키_스페이스
  • hash_table[hash_key]에서 키 삭제
• contains() 함수를 정의합니다. 이것은 key
  가 필요합니다.
  • 해시_키:=키모드키_스페이스
  • hash_table[hash_key]의 get(key) 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Bucket:
   def __init__(self):
      self.bucket=[]
   def update(self, key):
      found=False
      for i,k in enumerate(self.bucket):
         if key==k:
            self.bucket[i]=key
            found=True
            break
      if not found:
         self.bucket.append(key)
   def get(self, key):
      for k in self.bucket:
         if k==key:
            return True
      return False
   def remove(self, key):
      for i,k in enumerate(self.bucket):
         if key==k:
            del self.bucket[i]
class MyHashSet:
   def __init__(self):
      self.key_space = 2096
      self.hash_table=[Bucket() for i in range(self.key_space)]
   def add(self, key):
      hash_key=key%self.key_space
      self.hash_table[hash_key].update(key)
   def remove(self, key):
      hash_key=key%self.key_space
      self.hash_table[hash_key].remove(key)
   def contains(self, key):
      hash_key=key%self.key_space
      return self.hash_table[hash_key].get(key)
ob = MyHashSet()
ob.add(1)
ob.add(3)
print(ob.contains(1))
print(ob.contains(2))
ob.add(2)
print(ob.contains(2))
ob.remove(2)
print(ob.contains(2))

입력

ob = MyHashSet()
ob.add(1)
ob.add(3)
print(ob.contains(1))
print(ob.contains(2))
ob.add(2)
print(ob.contains(2))
ob.remove(2)
print(ob.contains(2))

출력

True
False
True
False