알고리즘 기초 - 해쉬 테이블(Hash Table)

🌈 해쉬 테이블(Hash Table)

🔥 해쉬 테이블이란?

🔥 python 내장 함수 hash

🔥 Hash 충돌 해결

1.해쉬 테이블이란?

• 해쉬 테이블은 키(Key)에 데이터를(Value)를 저장하는 데이터 구조로 키(Key)를 통해 데이터를 받아올 수 있기 때문에 속도가 빠름
• python에서는 해쉬를 별도 구현할 필요없이 딕셔너리를 사용할 수 있고, 딕셔너리도 내부적으로 해쉬 테이블의 구조를 띄고 있음
• 해쉬 테이블 관련 용어
  • 해쉬 : 임의에 값을 고정 길이로 변환하는 것
  • 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
  • 해싱 함수 : Key에 대해 산술 연산을 적용해 해쉬 값으로 변환해주는 함수
  • 해쉬 값(해쉬 주소) : Key를 해싱 함수에 대입하여 반환되는 것을 해쉬 값이라하고, 이를 기반으로 테이블에서 해당 Key에 대한 데이터 위치를 탐색
  • 슬롯 : 한개의 데이터를 저장할 수 있는 공간

1) 간단 Hash Table 만들기

# 빈 해쉬 테이블 만들기
hash_table = list([0 for i in range(10)])
print(hash_table) # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

# 간단 해쉬 함수 : Division 방식
# Division 방식 : 나누기를 통한 나머지 값을 사용하는 기법
def hash_func(key):
    return key % 5

# 해쉬 테이블에 데이터 저장
def storage_data(data, value): # 👈 키와 저장할 데이터를 받음
    key = ord(data[0]) # 👈 키를 해쉬함수에 넣어 연산하기 위해 숫자로 변환
    hash_address = hash_func(key) # 👈 해쉬 함수 작동하여 해쉬값(해쉬주소) 얻음
    hash_table[hash_address] = value # 👈 해쉬 주소를 index로하여 데이터를 테이블에 저장
storage_data('Jaewon', '010-1234-5678')
storage_data('Haezin', '010-4444-9999')
storage_data('Ginsu', '010-8989-1212')
# 해쉬 테이블 저장 후 해쉬 테이블 상태 확인
print(hash_table)
# [0, '010-8989-1212', '010-4444-9999', 0, '010-1234-5678', 0, 0, 0, 0, 0]

# 해쉬 테이블에서 특정 주소의 데이터를 가져오는 함수
def get_data(data):
    key = ord(data[0]) # 👈 데이터에서 Key를 추출
    hash_address = hash_func(key) # 👈 key를 해쉬 함수에 넣어 해쉬 주소를 얻음
    return hash_table[hash_address] # 👈 해쉬 주소를 통해 배열에서 데이터를 반환
print(get_data('Jaewon')) # 010-1234-5678
print(get_data('Haezin')) # 010-4444-9999
print(get_data('Ginsu')) # 010-8989-1212

2) Hash Table 특징

• 장점 : 데이터 저장/읽기 속도 빠름, 해쉬는 키에 대한 데이터의 존재여부 확인 및 중복 처리가 쉬움
• 단점 : 불필요한 저장 공간을 확보해두기 때문에 비교적 저장 공간이 많이 필요, 여러 키에 해당하는 주소가 동일할 경우 충돌을 막기 위한 자료구조가 별도로 필요
• 주요 용도 : 검색이 많이 필요한 경우, 저장&삭제&읽기가 빈번한 경우, 캐쉬 구현시

2. python 내장 함수 hash

• python에서는 hash라는 내장함수를 제공하고, 파라미터를 주면 자동으로 키를 생성함

# hash 내장 함수 : 해쉬 키를 자동으로 생성해줌
print(hash('jaewon')) # -2933907617461129694

• 해쉬 기능 구현해보기

# 해쉬 테이블
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_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('Jaewon', '01011112222')
save_data('Haezin', '01088889999')
print(hash_table) # [0, '01088889999', 0, 0, 0, '01011112222', 0, 0]
print(read_data('Jaewon')) # 01011112222
print(read_data('Haezin')) # 01088889999

3. Hash 충돌 해결

• 0부터 100까지 수를 key라 하고, 8로 나눈 나머지를 구하는 hash_function에 넣어 나올 수 있는 모든 hash address는 0~7이기 때문에 중복이 발생
• 이로 인해 hash의 주소가 동일해 데이터가 덮어씌어져버리는 문제가 발생

l = [i for i in range(100)]
data_set = []
for i in l:
    data = i % 8
    data_set.append(data)
print(list(set(data_set)))

1) Chaining 기법

• Open Hashing 기법 중 하나로 해쉬 테이블 공간 외의 공간을 마련하여 데이터를 저장함
• 즉, 충돌이 발생 시 연결 리스트 자료 구조를 사용해 데이터를 저장하는 기법
• 단, 공간이 많이 필요함
• Chaining 기법은 데이터를 식별할 수 있는 key값을 함께 저장하여 이를 식별함
  • 🔍 index_key = get_key(data)

# 해쉬 테이블
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) # 👈 index_key라는 별도의 변수에 key값을 저장
    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] == 0 👈 없을 때
        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
# 해쉬주소 중복 발생 <- 할때마다 변함
print(hash('Jaewon')%8) # 3
print(hash('Haezin')%8) # 2
print(hash('AaLa')%8)  # 3
# 저장
save_data('Jaewon', '01011112222')
save_data('Haezin', '01088889999')
save_data('AaLa', '01033331234')
print(hash_table)
# [0, 0, [[-3231082452735185358, '01088889999'], [630994963842225842, '01033331234']], [[-6162502635708335149, '01011112222']], 0, 0, 0, 0]
# 조회
print(read_data('Jaewon')) # 01011112222
print(read_data('Haezin')) # 01088889999

2) Linear Probing 기법

• Close Hashing 기법 중 하나로 해쉬 테이블 저장 공간 안에서 충돌 문제를 해결하는 기법으로 Linear Probing 기법이 대표적임
• Linear Probing 기법은 충돌 발생 시, hash adress의 다음 adress부터 맨 처음 나오는 빈공간에 저장하는 방식이기 때문에 저장공간 활용도가 높음

# 해쉬 테이블
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
    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
# 해쉬주소 중복 발생 <- 할때마다 변함
print(hash('Jaewon')%8) # 0
print(hash('Haezin')%8) # 0
print(hash('AaLa')%8)  # 7
# 저장
save_data('Jaewon', '01011112222')
save_data('Haezin', '01088889999')
save_data('AaLa', '01033331234')
print(hash_table)
# [[3214169218863054112, '01011112222'], [-291548128366538008, '01088889999'], 0, 0, 0, 0, 0, [-143120377966334057, '01033331234']]
# 조회
print(read_data('Jaewon')) # 01011112222
print(read_data('Haezin')) # 01088889999

• 빈번한 hash 충돌이 나타난다면, 해쉬 함수를 재정의하거나 해쉬 테이블 저장 공간 확대해야 함

3) hash table 시간 복잡도

• 충돌이 없는 경우 : O(1)
• 충돌이 발생하는 경우 : O(N)