해시테이블은 키와 값이 하나의 쌍을 이루는 추상자료형이며, 키를 빠르게 저장하고 검색할 수 있는 테이블 형태의 자료구조이다.
결과적으로, 키를 활용하여 값에 직접 접근이 가능한 구조이다.
해시는 해시 함수를 통해 나온 값이다.
해시함수
: 여러 키를 각각의 해시값으로 매칭시키는 역할의 함수
해싱이란, 키와 값을 매핑(mapping)시키는 과정이다.
해싱의 목적은 '검색'인데, 쉽게 말해 다 흩뜨려 놓고, 키와 매칭되는 값을 검색하는 과정이다.
따라서, 해시테이블은 검색 알고리즘의 역할도 한다.
또한, 해싱은 데이터 양에 영향을 덜 받으며 빠른 성능을 보인다.
- 빠른 탐색
- 빠른 삽입
- 빠른 삭제
해시 탐색법은 데이터의 내용과 저장한 곳의 요소를 미리 연결해둠으로써 극히 짧은 시간 안에 탐색할 수 있도록 고안된 알고리즘이다.
Big-O 성능 비교
- 해시 탐색 ->
- 이진 탐색 ->
- 선형 탐색 ->
해시함수 요구 조건
- 입력값이 동일할 시, 출력값도 동일해야 한다.
- 입출력값이 일정하지 않다면 적절한 해시함수가 아니다.
- 입력값 'aqua'가 4를 반환한다면, 입력값 'beige'는 4를 반환할 수 없다.
- 해시함수는 특정 범위 내의 숫자를 반환해야 한다.
- 어떤 해시함수를 통과한 입력 데이터들이 각각 다른 숫자와 매핑된다면 이 해시함수는 완벽한 해시함수이다.
- 해시함수가 입력데이터에 따라 다른 숫자를 반환하게 된다면 이는 해시충돌을 최소화하는 것이다.
해시함수는 보통 문자열 입력값에 정수형 숫자를 반환한다.
파이썬에서 .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)
시간복잡도 안에 검색, 삽입, 삭제를 할 수 있다.
Created on Dec 1, 2021
- 글 작성