📌 해쉬 구조

Hash Table : 키(Key)에 데이터(Value)를 저장하는 데이터 구조이다.

• key를 통해 바로 데이터를 받아올 수 있어 속도가 매우 빨라진다. (배열 같은 다른 데이터 구조보다 훨씬 검색 속도가 빠름)
• 보통 배열로 미리 Hash Table의 사이즈만큼 공간을 생성한 후 사용한다. 따라서 저장 공간이 많이 필요한 대신, 탐색 시간이 훨씬 감소하므로 해쉬 테이블은 공간과 탐색 시간을 맞바꾸는 기법이다.
• 해쉬 테이블의 대표적인 예로는 파이썬의 딕셔너리(Dictionary) 타입이 있다. 따라서 파이썬에서는 해쉬를 별도로 구현할 필요가 없다. (딕셔너리 타입을 사용하면 된다.)

---

📌 관련 용어 정리

• 해쉬(Hash) : 임의의 값을 고정된 길이로 변환하는 것
• 해쉬 테이블(Hash Table) : (key, value)로 데이터를 저장하여, 키 값의 연산에 의해 데이터에 접근할 수 있는 데이터 구조
• 해싱 함수(Hashing function) : key에 대한 산술 연산을 통해 데이터의 위치를 찾을 수 있는 함수
• 해쉬 주소(Hash Address) or 해쉬 값(Hash Value) : key를 해싱 함수로 연산한 결과로, 이를 이용하여 해쉬 테이블에서 해당 key에 대한 데이터 위치를 일관성 있게 찾을 수 있음
• 슬롯(Slot) : 한 개의 데이터를 저장할 수 있는 공간

---

📌 Hash Table 만들기

💡 리스트로 해쉬 테이블 만들기

• 충돌은 고려하지 않음

hash_table = list([0 for i in range(8)])
# 파이썬 list comprehension 사용

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8

def save_data(data, value):
    hash_address = hash_function(get_key(data))
    hash_table[hash_address] = value
    
def read_data(data):
    hash_address = hash_function(get_key(data))
    return hash_table[hash_address]

입력

save_data('Dave', '0102030200')
save_data('Andy', '01033232200')
read_data('Dave')
print(hash_table)

출력

[0, 0, 0, 0, 0, 0, '0102030200', '01033232200']

문제점

• 하지만 만약 서로 다른 key임에도 해쉬 주소가 동일하다면 어떻게 해야 할까?
• 따라서 위의 방법으로 해쉬 테이블을 구현하게 되면 이러한 해쉬 충돌(Hash Collision) 문제를 해결하지 못한다.
• 해쉬 충돌을 해결하기 위해서는 Chaining 기법 or Linear Probing 기법을 이용해야 한다.

---

💡 충돌 해결 (1) - Chaining 기법

• 개방 해슁(Open Hashing) 기법 중 하나이다.
• 해쉬 테이블의 저장공간 외의 공간을 활용하는 기법이다.
• 충돌이 일어나면 Linked List 자료구조를 이용하여 데이터를 추가로 뒤에 연결시켜 저장한다.

Code

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)
    if hash_table[hash_address] != 0: # 충돌이 일어나는 경우
        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
                return
        hash_table[hash_address].append([index_key, value]) # 일치하는 키 값이 없다면 추가로 뒤에 연결
    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: # 해당 hash address에 데이터가 존재하는 경우
        for index in range(len(hash_table[hash_address])): # 해당 hash address에 연결된 모든 key 순회
            if hash_table[hash_address][index][0] == index_key: 
                return hash_table[hash_address][index][1]
        return None # 순회 후 일치하는 key가 없으면 None 반환
    else:
        return None # 해당 hash address에 데이터가 존재하지 않는 경우

---

💡 충돌 해결 (2) - Linear Probing 기법

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

Code

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)
    if hash_table[hash_address] != 0: # 충돌이 일어나는 경우
        for index in range(hash_address, len(hash_table)): # 현재 hash address부터 해쉬 테이블 끝까지 순회
            if hash_table[index] == 0: # 처음 나오는 빈 공간에 데이터를 저장
                hash_table[index] = [index_key, value]
                return
            elif hash_table[index][0] == index_key: # 같은 키이면 데이터를 업데이트
                hash_table[index][1] = value
                return
    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: # 해당 hash address에 데이터가 존재하는 경우
        for index in range(hash_address, len(hash_table)): # 현재 hash address부터 해쉬 테이블 끝까지 순회
            if hash_table[index] == 0: #빈 슬롯이 나타나게 되면 저장된 적이 없는 데이터임
                return None
            elif hash_table[index][0] == index_key: 
                return hash_table[index][1]
    else: # 해당 hash address에 데이터가 존재하지 않는 경우
        return None

---

📌 해쉬 테이블의 장단점과 주요 용도

• 장점
  • 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다)
  • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
• 단점
  • 일반적으로 저장공간이 좀더 많이 필요하다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함
• 주요 용도
  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현시 (중복 확인이 쉽기 때문)

---

📌 시간 복잡도

• 일반적인 경우(Collision이 없는 경우)는 $O(1)$
• 최악의 경우(Collision이 모두 발생하는 경우)는 $O(n)$

해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에, 시간 복잡도는 $O(1)$ 이라고 말할 수 있음