[Python] Hash Table

문제

set 는 동일한 값을 여러번 삽입 불가능하고 해쉬값을 기반으로 저장하기 때문에 look up 이 굉장히 빠른 자료구조라고 배웠습니다.
내부적으로 해시 값을 사용해서 빠르게 데이터를 저장하고 가져올 수 있기 때문 인데요. 해시 값을 구해주는 함수를 해시 함수라고 하는데 다른 키에 대해서 같은 해시값이 나오는 경우를 충돌 이라고 합니다.
우리는 이런 충돌을 해결하여 중복된 값을 저장하지 않도록 해시 테이블을 사용하여 주어진 MySet클래스의 add 메소드를 간단하게 구현해 보겠습니다.
여기서는 가장 간단한 방법인 선형 탐사기법을 사용하여 충돌을 방지하고 중복된 데이터를 저장하지 않도록 구현해 보겠습니다.
선형탐사(Linear Probing) 특정 버킷에서 충돌이 발생하면 인덱스를 1씩 증가시켜 비어있는 버킷을 찾는 방법입니다.
다음 그림은 wecode를 sha1 해시 함수와 숫자만 뽑아내서 나눗셈법으로 해시버킷6에 삽입한 이후, weplay 를 해시할때 버킷6에서 충돌이 발생한 상황입니다. 충돌이 발생하면 고정적으로 인덱스를 1씩 증가시켜 비어있는 버킷을 찾아내는 것을 선형 탐사라고 합니다.

Assignment

MySet클래스는 내부에 15개의 bucket을 가지는 클래스 입니다.

1. hash_value 함수
   SHA1 알고리즘으로 해시값을 구한후,
   16진수중 0~9까지만 골라내서 나눗셈법으로 버킷의 인덱스를 구합니다.
   (hint) hash_value 를 print 해서 값을 확인해보고 숫자만 골라내서 이어붙여서 새로운 숫자를 만들어 내고 버킷의 사이즈로 나눈 나머지를 버킷의 인덱스로 하는 함수입니다.

2. add 함수
   hash_value 함수를 사용하여 해시값을 구한 후 중복되는 키에 대해서는 충돌을 해결하여 중복된 값을 저장하지 않도록 bucket에 저장하는 함수 입니다.

내코드

class MySet:
  def __init__(self, size):
    self.size = size
    self.bucket = [ None for x in range(size) ]

  def values(self):
    set_data =""
    for i in range(self.size):
      if self.bucket[i] != None:
        set_data += self.bucket[i]
        set_data += ", "
    if set_data[-1] == " ":
      data_set = set_data[:-2]
    return data_set

  # 1. hash_value 함수
  def hash_value(self,key):
    hash_value = hashlib.sha1(key.encode())
    hash_value = hash_value.hexdigest()
    # 여기서 부터 구현
    result = str()
    for i in hash_value:
      if i.isdigit():
        result += i
    result = int(result)
    
    index = result%self.size
    return index
    
  # 2. add 함수
  def add(self, key):
    hash_value = self.hash_value(key)
    # 여기서 부터 구현
    def check(key, hash_value):  # self를 써줘야되는지 말아야되는지 헷갈림
      if self.bucket[hash_value] is None:
        self.bucket[hash_value] = key
        return 0
      else:
        if self.bucket[hash_value] == key:
          return 0
        else:
          hash_value += 1
          if hash_value >=self.size:
            hash_value -= self.size
          return check(key, hash_value)
    return check(key, hash_value)   # outer function에서 호출을 해주어야한다.
      ### 반복되는 부분
      # if self.bucket[hash_value] is not None:
      #   slef.buckt[hash_value] = key
      # else:
      #   hash_value += 1

add()코드를 짜다가 과정이 반복되길래 오늘 아침 코드카타에서본 재귀함수가 생각나서 사용해보았다. 클래스 내에서는 어떻게 하는지 잘 모르겠어서 self를 붙여야되는지 말아야되는지가 고민되었다. 그건 나중에 더 알아봐야겠다.

재귀함수를 사용할때 선언만 해주고 호출을 안해주어서(check()함수 내에서 자기자신만 호출함) 실행이 안되었었다. 바깥쪽 함수(add())에서 return을 해줘야지 실행이 된다.

또한 index의 값만 늘려주는 것이 아니라 같은 key가 오면 그 key는 넣어주면 안되서 그 부분을 처리해줘야했다.(다 푼 줄 알고 좋아했는데😂) 그것은 값이 들어있을때 내가 넣으려는 hash에 들어있는 값과 key를 비교해주면 해결되었다. 처음에는 values()함수로 체크를 해야하나 싶었는데 class내에서 values()를 호출해도 객체의 값을 불러낼 수 없기 때문에 사용할 수 없었다.(내부에 아무것도 없어서 IndexError만 발생)

isdigit(), isalpha() 함수 살펴보기

Model Solution

class MySet:
  def __init__(self, size):
    self.bucket = [ None for x in range(size) ]
    self.size = size
  
  def hash_value(self,key):
    hs_value = hashlib.sha1(key.encode())
    hash_value = re.findall('\d+',hs_value.hexdigest())
    hash_value = "".join(hash_value)
    return int(hash_value)%15

  def add(self, key):
    hash_value = self.hash_value(key)
    i = hash_value

    while self.bucket[i] != None:  
      if key is self.bucket[i]:
        return "duplicate"

      i = (i + 1) % self.size

      if i == hash_value:
        return "full"

    self.bucket[i] = key
    return


  def values(self):
    set_data =""
    for i in range(self.size):
      if self.bucket[i] != None:
        set_data += self.bucket[i]
        set_data += ", "
    if set_data[-1] == " ":
      data_set = set_data[:-2]
    return data_set