해시 테이블 구현.md

해시 테이블 구현

• 먼저 구현하기전에 해시에 대한 개념을 짚고 넘어가자!
• 해시

구현

• 일단 해시의 기본인 해시 테이블을 구현해야한다.
• 그리고 해시 충돌에 대한 처리를 구현해야한다.
  • 해시 충돌에는 크게 두가지 해결법이 있다.
  • Separate chaining (Open Hashing)
  • Open addressing (Close Hashing)

1. 해시 테이블을 구현해보자

# 해쉬 테이블 공간 생성
hash_table = list([0 for i in range(8)])

# 해쉬 키 생성
def get_key(data) : 
  return hash(data)
  
# 나머지를 이용한 해쉬 함수 (간단하게 표현하기위해 한번 더 해쉬함수를 돌린 것)
def hash_function(key):
  return key % 8

# 해쉬 함수로 산출한 해쉬 주소
def save_data(data, value):
  hash_address = hash_fuction(get_key(data))
  hash_table[hash_address] = value
  
def read_data(data):
  hash_address = hash_function(get_key(data))
  return hash_table[hash_address]

2. 충돌의 첫번째 경우 - Open Hasing

# 해쉬 테이블 공간 생성
hash_table = list([0 for i in range(8)])

# 해쉬 키 생성
def get_key(data) : 
  return hash(data)
  
# 나머지를 이용한 해쉬 함수 
def hash_function(key):
  return key % 8

# 해쉬 함수로 산출한 해쉬 주소
def save_data(data, value):
  index_key = get_key(data)
  hash_address = hash_function(index_key)
  
  # 1. 해쉬 충돌이 발생할 경우
  if hash_table[hash_address] != 0:
    for index in range(len(hash_table[hash_address])):
       1-1. Key가 동일하면 데이터를 덮어씀
      if hash_table[hash_address][index][0] == index_key:
        hash_table[hash_address][index][1] = value
        return
    # 1-2. Key가 동일하지 않으면 데이터를 연결해 저장    
    hash_table[hash_address].append([index_key, value]) 
  # 2. 해쉬 충돌이 발생하지 않으면 해당 공간에 데이터   
  else: 
    hash_table[hash_address] = [[index_key, value]]
    
def read_data(data):
  index_key = get_key(data)
  hash_address = hash_function(index_key)
  
  if hash_table[hash_address] != 0:
    for index in range(len(hash_table[hash_address])):
      if hash_table[hash_address][index][0] == index_key:
        return hash_table[hash_address][index][1]
   else:
    return None

3. 충돌의 첫번째 경우 - Close Hasing

# 해쉬 테이블 공간 생성
hash_table = list([0 for i in range(8)])

# 해쉬 키 생성
def get_key(data) : 
  return hash(data)
  
# 나머지를 이용한 해쉬 함수 
def hash_function(key):
  return key % 8

# 해쉬 함수로 산출한 해쉬 주소
def save_data(data, value):
  index_key = get_key(data)
  hash_address = hash_address(index_key)
  
  # 1. 해쉬 충돌이 발생할 경우 
  if hash_table[hash_address] != 0:
    # 충돌이 일어난 주소부터 끝까지 스캔
    for index in range(hash_address, len(hash_table)):
      # 동일한 Key일 경우 덮어씀
      if hash_table[index][0] == index_key:
        hash_table[index][1] = value
        return
      # 빈 공간을 찾으면 저장
      elif hash_table[index] == 0:
        hash_table[index] = [index_key, value]
        return
  # 2. 해쉬 충돌이 발생하지 않으면 해당 공간에 저장     
  else: 
    hash_table[hash_address] = [[index_key, value]]
    
def read_data(data):
  index_key = get_key(data)
  hash_address = hash_function(index_key)
  
  if hash_table[hash_address] != 0:
    for index in range(hash_address, len(hash_address)):
      if hash_table[index][0] == index_key:
        return hash_table[index][1]
      # 빈 공간이 나올때까지 동일한 Key를 발견하지 못하면 데이터가 없다는   
      elif hash_table[index] == 0:
        return None
  else:
    return None

---

Referance

• https://idm101.tistory.com/3