Hash Table(1) - 해시테이블/해시함수/해시충돌

Yves (Taeyeon Kim)·2021년 12월 1일

Big O Hash Table Hashing algorithm data structure hash colision hash function 빅오 알고리즘 자료구조 해시충돌 해시테이블 해시함수

CS - Data Structure and Algorithm Core

목록 보기

6/7

0. Hash Table

해시테이블은 키와 값이 하나의 쌍을 이루는 추상자료형이며, 키를 빠르게 저장하고 검색할 수 있는 테이블 형태의 자료구조이다.
결과적으로, 키를 활용하여 값에 직접 접근이 가능한 구조이다.

0.0. Hash

해시는 해시 함수를 통해 나온 값이다.

해시함수
: 여러 키를 각각의 해시값으로 매칭시키는 역할의 함수

0.1. Hashing

해싱이란, 키와 값을 매핑(mapping)시키는 과정이다.
해싱의 목적은 '검색'인데, 쉽게 말해 다 흩뜨려 놓고, 키와 매칭되는 값을 검색하는 과정이다.
따라서, 해시테이블은 검색 알고리즘의 역할도 한다.
또한, 해싱은 데이터 양에 영향을 덜 받으며 빠른 성능을 보인다.

빠른 탐색

빠른 삽입

빠른 삭제

0.2. 해시 탐색법

해시 탐색법은 데이터의 내용과 저장한 곳의 요소를 미리 연결해둠으로써 극히 짧은 시간 안에 탐색할 수 있도록 고안된 알고리즘이다.

Big-O 성능 비교

해시 탐색 -> $O(1)$

이진 탐색 -> $O(logn)$

선형 탐색 -> $O(n)$

1. Hash Function - 해시함수

해시함수는 키를 해시테이블 내의 버킷(==hash)으로 매핑시킨다.
검색/삽입/삭제 작업에 관계없이 해시함수는 키를 통해 저장된 값에 연관된 해시(인덱스)를 반환한다.
해시함수의 입력값은 다양하고, 출력값은 숫자 형태이다.

해시함수 요구 조건

입력값이 동일할 시, 출력값도 동일해야 한다.

입출력값이 일정하지 않다면 적절한 해시함수가 아니다.

입력값 'aqua'가 4를 반환한다면, 입력값 'beige'는 4를 반환할 수 없다.

해시함수는 특정 범위 내의 숫자를 반환해야 한다.

어떤 해시함수를 통과한 입력 데이터들이 각각 다른 숫자와 매핑된다면 이 해시함수는 완벽한 해시함수이다.

해시함수가 입력데이터에 따라 다른 숫자를 반환하게 된다면 이는 해시충돌을 최소화하는 것이다.

1.1. 기본 해시함수

해시함수는 보통 문자열 입력값에 정수형 숫자를 반환한다.
파이썬에서 .encode 메소드를 활용하여 문자열 to 바이트 코드로 인코딩하는 예시를 통해 해시함수의 기본을 알아본다.

먼저 특정 문자열을 byte code로 나타내보자.

bytes_representation = "hello".encode()

for byte in bytes_representation:
    print(byte)
    
#
104 #'h'
101 #'e'
108 #'l'
108 #'l'
111 #'o'

입력된 문자열에 해당하는 특정 해시값을 만들기 위한 해시함수로 모든 바이트코드(정수값)의 합을 반환하는 방법을 활용해본다.

bytes_representation = "hello".encode()

sum = 0
for byte in bytes_representation:    
    sum += byte

print(sum)

이제 위의 특성을 가진 해시함수를 만들어본다.

def my_hashing_func(str, list_size):
    bytes_representation = str.encode()
    sum = 0

    for byte in bytes_representation:
        sum += byte
    
    print('sum', sum)
    print('list_size', list_size)
    print('sum % list_size', sum % list_size)

    return sum % list_size # a hash

만들어진 해시함수를 사용해본다.

#리스트 값 None 초기화
my_list = [None] * 5 

#해시함수를 통과한 문자열의 해시값을 리스트의 인덱스로 하여 값(value) 입력
my_list[my_hashing_func('aqua', len(my_list))] = "#00FFFF" #value

#리스트에 입력된 값 확인(해시함수를 통한 값 검색)
print("========")
print(my_list[my_hashing_func('aqua', len(my_list))])

#업데이트된 리스트 확인
print("========")
print(my_list)