[PYTHON]해시(Hash)

✅ 목표

요청데이터를 묶은 key 값을 받고(1차), 그 key값과 요청 데이터의 hash값을 보내면 성공 응답이 돌아온다(2차).

# 요청 데이터
{"name":"user", "transfer_amount":100}

# 응답 데이터: key 값
{"transfer_identifier": 11}

# 요청 데이터
{"signature":"46a84b46fb4f6gad5f6dg", "transfer_identifier": 11}

# 응답 데이터
{"status": true}

1. 해시 테이블

• Hash Table: 키에 데이터를 저장하는 key-value 구조.
• 파이썬 딕셔너리 타입이 해시 테이블의 한 예이다(파이썬에는 해시를 별도 구현할 필요가 없음).

hash_table = list([0 for _ in range(5)]) #해시 테이블 크기는 0~4

#hash() 내장함수 사용
def get_key(data): #데이터를 hash값으로
    return hash(data)
 
def hash_function(key): #hash값 리턴
    return key % 5
 
def save_data(data, value): #key값을 받으면 0~4의 인덱스값으로 변환해줌, 그 인덱스에 value를 저장
    hash_address = hash_function(get_key(data))
    hash_table[hash_address] = value
    return hash_address # hash 주소(key값) 반환
    
def read_data(hash_address):
    return hash_table[hash_address]

결과

>>> save_data('user', '1000')
2
>>> save_data('user2', '01055559999')
4
>>> save_data('user3', '11000')
2

• 동일한 주소가 있어서 충돌(collision) 발생

2. Chaining 기법

• 개방해싱(Open hashing) 기법 중 하나.
• 해시 테이블 외의 저장공간을 활용하는 기법.
• 충돌 발생 시 연결리스트(linked list) 자료구조를 이용해 데이터를 뒤에 추가로 연결시켜 저장한다.

hash_table = list([None for i in range(5)]) #해시 테이블 크기는 0~4

#hash() 내장함수 사용
def get_key(data): #데이터를 hash값으로
    return hash(data)

def hash_function(key): #hash값 리턴
    return key % 5

def save_data_hash_table(data, value):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    # 같은 hash_address가 있는 경우
    if hash_table[hash_address] != None:
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                hash_table[hash_address][index][1] == value
        # hash_table[hash_address] 출력 예: [[7886761754358330341, value]]
        hash_table[hash_address].append([index_key, value])
        return hash_address
    else:
        hash_table[hash_address] = [[index_key, value]]
        return hash_address

def get_data_hash_table(data, hash_address):
    index_key = get_key(data)
    if hash_address == hash_function(index_key):
        if hash_table[hash_address] != None:
            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 "invalid data"

결과

>>> save_data_hash_table('user', 1000)
2
>>> save_data_hash_table('user1', 10050)
2
>>> get_data_hash_table('user', 2)
1000
>>> get_data_hash_table('user2', 2)
'invalid data'
>>> get_data_hash_table('user2', 4)
15000

• hash_address가 중복돼도 충돌은 일어나지 않는다.

3. Linear Probing 기법

• 패쇄해싱(Close hashing) 기법 중 하나.
• 충돌 발생 시 해시 주소의 다음 주소부터 맨 처음 나오는 빈공간에 저장.
• 저장공간 활용도가 높다.

---

[참고 사이트]

https://www.fun-coding.org/Chapter09-hashtable.html