Python에서 HashMap 디자인

내장된 해시 테이블 라이브러리를 사용하지 않고 HashMap을 설계한다고 가정합니다. 다음과 같이 다른 기능이 있습니다 -

• put(key, value) - 키와 관련된 값을 HashMap에 삽입합니다. 값이 이미 HashMap에 있으면 값을 업데이트합니다.
• get(key) - 지정된 키가 매핑된 값을 반환합니다. 그렇지 않으면 이 맵에 키에 대한 매핑이 없는 경우 -1이 반환됩니다.
• remove(key) - 이 맵에 키에 대한 매핑이 포함되어 있으면 값 키에 대한 매핑을 제거합니다.

따라서 입력이 초기화 후와 같으면 다음과 같이 put 및 get 메소드를 호출하십시오. -

• put(1, 1);
• put(2, 2);
• get(1);
• get(3);
• put(2, 1);
• get(2);
• 제거(2);
• get(2);

그러면 출력은 각각 1, -1(없음), 1, -1(없음)이 됩니다.

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

• 노드라고 하는 새 데이터 구조를 만들고 초기화하기 위해 다음과 같은 필드가 있을 것입니다(key, val, next), next는 초기에 null입니다.
• 하나의 연결 목록을 정의합니다. 다음과 같은 몇 가지 방법이 있습니다. -
• 하나의 이니셜라이저를 정의하면 다음과 같이 작동합니다. -
  • prehead:=key =null 및 val =null인 새 노드 노드
• search() 함수를 정의합니다. 열쇠가 필요합니다
• p :=prehead.next
• p가 null이 아닌 동안 do
  • p.key가 key와 같으면
    • 반환
  • p :=p.next
• 반환 없음
• add() 함수를 정의합니다. 키, val이 필요합니다.
• p :=검색(키)
• p가 null이 아니면
  • p.val :=val
• 그렇지 않으면
  • node :=(key, val)이 있는 새 노드
  • prehead.next :=노드, node.next :=prehead.next
• get() 함수를 정의합니다. 열쇠가 필요합니다
• p :=검색(키)
• p가 null이 아니면
  • p.val 반환
• 그렇지 않으면
  • null 반환
• 제거 기능을 정의합니다. 열쇠가 필요합니다
• prev :=머리말
• cur :=prev.next
• cur가 null이 아닌 동안 do
  • cur.key가 key와 같으면
    • 루프에서 나오다
  • 이전 :=curr, cur :=cur.next
  • cur가 null이 아니면
    • prev.next :=cur.next
• serialize() 함수를 정의합니다.
• p :=prehead.next
• ret :=새 목록
• p가 null이 아닌 동안 do
  • 끝에 ret에 [p.key, p.val] 삽입
  • p :=p.next
• 반환
• 사용자 정의 해시맵에서 다음과 같이 메서드를 정의합니다. -
• 하나의 이니셜라이저를 정의합니다.
• 크기 :=1033
• arr :=크기와 길이가 같은 LinkedList() 배열
• _hash() 함수를 정의합니다. 열쇠가 필요합니다
• 반환 키 모드 크기
• put() 함수를 정의합니다. 여기에는 핵심 가치가 필요합니다.
• h :=_hash(키)
• arr[h]의 add(key, value)
• get() 함수를 정의합니다. 열쇠가 필요합니다
• h :=_hash(키)
• ret :=arr[h]의 get(key)
• ret가 null이 아니면
  • 반환
• 그렇지 않으면
  • 반환 -1
• remove() 함수를 정의합니다. 열쇠가 필요합니다
• h :=_hash(키)
• arr[h]에서 키 삭제

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

예

class Node:
   def __init__(self, key, val):
      self.key = key
      self.val = val
      self.next = None
class LinkedList:
   def __init__(self):
      self.prehead = Node(None, None)
   def search(self, key):
      p = self.prehead.next
      while p:
         if p.key == key:
            return p
         p = p.next
      return None
   def add(self, key, val):
      p = self.search(key)
      if p:
         p.val = val
      else:
         node = Node(key, val)
         self.prehead.next, node.next = node, self.prehead.next
   def get(self, key):
      p = self.search(key)
      if p:
         return p.val
      else:
         return None
   def remove(self, key):
      prev = self.prehead
      cur = prev.next
      while cur:
         if cur.key == key:
            break
         prev, cur = cur, cur.next
      if cur:
         prev.next = cur.next
   def serialize(self):
      p = self.prehead.next
      ret = []
      while p:
         ret.append([p.key, p.val])
         p = p.next
      return ret
class MyHashMap:
   def __init__(self):
      self.size = 1033
      self.arr = [LinkedList() for _ in range(self.size)]
   def _hash(self, key):
      return key % self.size
   def put(self, key, value):
      h = self._hash(key)
      self.arr[h].add(key, value)
   def get(self, key):
      h = self._hash(key)
      ret = self.arr[h].get(key)
      if ret is not None:
         return ret
      else:
         return -1
   def remove(self, key):
      h = self._hash(key)
      self.arr[h].remove(key)
ob = MyHashMap()
ob.put(1, 1)
ob.put(2, 2)
print(ob.get(1))
print(ob.get(3))
ob.put(2, 1)
print(ob.get(2))
ob.remove(2)
print(ob.get(2))

입력

ob = MyHashMap()
ob.put(1, 1)
ob.put(2, 2)
print(ob.get(1))
print(ob.get(3))
ob.put(2, 1)
print(ob.get(2))
ob.remove(2)
print(ob.get(2))

출력

1
-1
1
-1