Hash table(해시 테이블) - Chaining, Linear probing

Chaining

 

데이터 추가 함수

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

def get_hash(data):
  return hash(data)
  
def get_address(hash):
  return hash % 8

def save_data(data, value):
  hash_key = get_hash(data)
  hash_address = get_address(hash_key)
  
  if hash_table[hash_address] != 0:
    for i in range(len(hash_table[hash_address])):
      if hash_table[hash_address][i][0] == hash_key:  # 같은 hash의 키로 데이터가 있을 경우
        hash_table[hash_address][i][1] = value  # value 업데이트
        return
    hash_table[hash_address].append([hash_key, value])  # for문을 돌았는데 같은 hash의 키로 된 데이터가 없다면 append로 추가
  else:
    hash_table[hash_address] = [[hash_key, value]]  # 해당 hash_address에 데이터가 없다면 0만 들어있을테니 hash_key, value를 list화 시켜서 삽입

 

데이터 찾기

def read_data(data):
  hash_key = get_hash(data)
  hash_address = get_address(hash_key)
  
  if hash_table[hash_address] != 0:
    for i in range(len(hash_table[hash_address])):
      if hash_table[hash_address][i][0] == hash_key:
        return hash_table[hash_address][i][1]
    return None
  else:
    return None

 

Linear Probing 기법 (추가예정)

• 폐쇄 해싱 또는 Close Hashing 기법 중 하나
• 해시 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈 공간에 저장하는 기법
• 저장공간 활용도를 높일 수 있다.

 

 

 

 

SHA

위에선 파이썬의 hash 함수를 썼는데

실행할 때마다 값이 달라질 수 있다는 단점이 존재

유명한 대체 해시 함수들이 존재하니 이걸 써도 됨

SHA(Secure Hash Algorithm)

- 어떤 데이터도 유일한 고정된 크기의 값으로 리턴해주므로, 해시 함수로 유용하게 활용 가능

 

SHA-1

import hashlib

data = 'test'.encode()
hash_object = hashlib.sha1()
# hash_object.update(data)
hash_object.update(b'test')  # encode()를 쓰거나 이렇게 b'test'를 써서 바이너리로 변경
hex_dig = hash_object.hexdigest()  # 16진수로 변환
print(hex_dig)

 

SHA-256

import hashlib

data = 'test'.encode()
hash_object = hashlib.sha256()
# hash_object.update(data)
hash_object.update(b'test')  # encode()를 쓰거나 이렇게 b'test'를 써서 바이너리로 변경
hex_dig = hash_object.hexdigest()
print(hex_dig)

 

이걸 토대로 위에서 사용했던 hash 함수를 sha-256을 쓰는걸로 바꿔보자

 

import hashlib

def get_key(data):
  hash_object = hashlib.sha256()
  hash_object.update(data.encode())
  hex_dig = hash_object.hexdigest()
  return int(hex_dig, 16)  # hex_dig는 16진수 문자열이기 때문에 10진수 정수형으로 변환

 

시간복잡도

일반적인 경우(Collision이 없는 경우): O(1)

최악의 경우(Collision이 모두 발생하는 경우): O(n)

* 하지만 해시 테이블은 일반적인 경우를 기대하고 만들기 때문에 시간 복잡도는 O(1)이라고 말할 수 있다.

 

검색에서 해시 테이블의 사용 예)

• 16개의 배열에 데이터를 저장하고, 검색할 때 O(n)
• 16개의 데이터 저장공간을 가진 위의 해시 테이블에 데이터를 저장하고, 검색할 때 O(1)