자료구조(3)-해시 테이블(Hash table)

링크드리스트(LinkedList)

1.구조

• Hash Table: 키(key)에 데이터(value)를 저장하는 데이터 구조
  • key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
  • 파이썬 딕셔너리 타입이 해시테이블의 예(key를 가지고 바로 데이터(value)를 꺼내옴)
  • 보통 배열로 미리 hash table 사이즈만큼 생성 후에 사용(공간과 탐색 시간을 맞바꾸는 기법 -> 해쉬테이블의 공간을 늘림으로써 충돌로 인한 추가적인 자료구조 알고리즘을 만들지 않기 때문)
  • 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 되기 때문

2.알아둘 용어

• 해쉬(hash): 임의 값을 고정 길이로 변환하는것
• 해쉬 테이블: 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱함수: key에 대해 산술 연산을 이용해 데이터 위치를 찾을수 있는 구조
• 해쉬값 또는 해쉬 주소: key를 해싱함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 key에 대한 데이터 위치를 일관성있게 찾을 수 있음
• 슬롯: 각각의 데이터를 저장할 수 있는 공간
• 저장할 데이터에 대해 key(입력값)를 추출할 수 있는 별도 함수도 존재할 수 있음
• 배열보다 해쉬테이블이 좋은 이유: 검색할 때 배열같은경우는 입력값에 대해 처음부터 확인을 해야하지만 해쉬테이블은 입력값을 통해서 바로 검색을 하여 가져올 수 있기 때문에 더 많이 쓰이게 된다.

3.장단점과 주요 용도

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

4.파이썬에서의 해시 테이블의 활용 예 - 딕셔너리(Dictionary)

5.직접 해쉬테이블 구현해보기

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_function으로 받은 키값으로 데이터 저장
    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]

여기서 한가지 의문점이 든다. 그렇다면 전달받은 데이터를 기반으로 키값을 만들어내는데 이때 같은 키값이 나오게 된다면 이를 어떻게 처리하고 저장이 될까? 이때 해쉬테이블의 가장 큰 문제점이 나온다. 바로 충돌(collison)이다. 그래서 해쉬테이블은 따로 충돌알고리즘을 구현해야하는데 대표적으로 2가지 방식이 있다.

-Chaining 기법

• 개방 해슁 또는 Open Hashing 기법 중 하나: 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
• 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법

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:
        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]
        return None
    else:
        return None

-Linear Probing 기법

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

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)):
            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:
        for index in range(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                return None
            elif hash_table[index][0] == index_key:
                return hash_table[index][1]
    else:
        return None

+) 위와 같은 해결기법을 통해 해결가능하지만 근본적으로 빈번한 충돌을 방지하기 위해서는 해쉬테이블의 저장공간을 애초에 많이 생성해주면 된다!