[자료구조] 해시테이블 클로즈 기법 개념 및 구현 with 파이썬(Python)

이전 포스팅 체이닝 기법에 이어 클로즈 기법에 대해 알아보자.

[자료구조] 해시테이블 체이닝 기법 개념 및 구현 with 파이썬(Python)

클로즈 기법에 하나로 Linear Probing 이 있다. hash address 충돌로 인해 다른 hash address를 찾아 저장하는 방법이다. 체이닝 처럼 링크드 리스트 자료구조를 사용하지 않아도 되어 메모리 공간을 효율적으로 사용할 수 있다는 장점이 있다. 

 

아래 그림처럼 Jack 과 Andrew는 같은 해시 테이블의 주소를 갖고 있어 충돌이 발생할때 그 아래 주소가 비어 있어Andrew는 아래에 저장하는 기법이다.

출처 https://lrtk-coder.github.io/2021/02/16/Data-Structure-Hash-Table/

코드를 통해 해시 테이블의 Linear Probing을 구현해보자.

hash_table = list([0 for i in range(10)])

def get_key(data):
  return hash(data)

def hash_function(key):
  return key % 8

def save_data(data, value):
  key = get_key(data)
  hash_address = hash_function(key)
  
  # 해시테이블에 데이터가 저장되어 있다면 해시테이블을 순회하며 데이터가 저장된 주소를 찾는다. 
  if hash_table[hash_address] != 0:
    for index in range(hash_address, len(hash_table)):

      # 순회를 돌다가 아무것도 저장되어 있지 않은 곳을 찾으면 데이터를 저장한다.
      if hash_table[index] == 0:
        hash_table[index] = [key, value]
        return
      
      # 만약 동일한 index_key를 갖고 있으면 값을 업데이트 한다.
      elif hash_table[index][0] == key:
        hash_table[index][1] = value
        return
  # 데이터가 저장되어 있지 않다면 바로 저장한다.  
  else:
    hash_table[hash_address] = [key, value]

def read_data(data):
  key = get_key(data)
  hash_address = hash_function(key)

  # 데이터가 있다면
  if hash_table[hash_address] !=0:
    for index in range(hash_address, len(hash_table)):
      if hash_table[index] == 0:
        return None
      elif hash_table[index][0] == key:
        return hash_table[index][1]

  # 데이터가 없다면
  else:
    return None

 Ddae, Date 키는 동일한 7이라는 동일한 주소를 갖고 있다. 아래의 hash table을 출력한 결과 Ddae 밑에 Date 키가 저장된 것을 확인 할 수 있다. 

print(hash('Doave') % 8)
print(hash('Ddae') % 8)
print(hash('Date') % 8)

4
7
7

save_data('Doave', '해시테이블')
save_data('Ddae', '채이닝 기법')
save_data('Date', '굿')


print(hash_table)

[0,
 0,
 0,
 0,
 [-8036962853101299476, '해시테이블'],
 0,
 0,
 [-6806664244704651577, '채이닝 기법'],
 [8831411780459752511, '굿'],
 0]

검색 개발할때 한번 써먹어봐야겠다.