해시
해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조
해시의 특징
- 단방향으로 동작한다.
- 키를 통해 값을 찾을 수 있지만 값을 통해서 키를 찾을 수 는 없다. - 찾고자 하는 값을 O(1)에서 바로 찾을 수 있습니다.
- 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없다. - 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 한다.
해시를 사용하지 않는다면 우리는 값의 위치에 대한 어떤 정보를 알 수 없다. 따라서 내가 찾고자 하는 데이터를 전체 데이터를 확인하는 방법이 유일한 방법이다.
반면 해시를 사용하면, 순차 탐색할 필요 없이 해시 함수를 활용해서 특정 값이 있는 위치를 바로 찾을 수 있어 탐색 효율이 좋다.
해시 테이블(Hash Table)은 키와 대응한 값이 저장되어 있는 공간이고, 키와 값의 한 묶음을 버킷(Bucket)이라고 한다.
해시의 특성을 활용하는 분야로
- 비밀번호 관리
- 데이터베이스 인덱싱
- 블록체인
등이 있다.
해시 함수
파이썬에서는 딕셔너리(Dict) 자료형을 제공하는데 이 자료형은 해시와 거의 동일하게 동작하므로 해시를 쉽게 사용할 수 있다. 해시의 원리를 이해하고 딕셔너리를 활용하여 더욱 효율적인 해시 활용을 하는 것이 이 글의 목적이다.
해시 함수를 구현할 때 고려할 내용
- 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안 된다.
- 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 한다.
- 충돌의 의미는 서로 다른 두 키에 대해 해시 함수를 적용한 결과가 동일한 것을 의미
- 최대한 충돌을 방지하면서도 메모리를 효율적으로 쓰기 위한 해시 함수를 활용하는 것이 해결 방안
자주 사용하는 해시 함수 알아보기
- 나눗셈법
- 가장 떠올리기 쉽고 단순한 해시 함수
- 키를 소수로 나눈 나머지를 활용한다.
- 모듈러 연산 : 나머지를 취하는 연산 -> %를 활용한다.
- 나눗셈을 할 때는 소수(Prime Number)를 사용한다.
- 충돌 방지를 위해 1 또는 자신만을 약수로 하는 소수를 사용하는 것이 좋다. - 곱셈법
- 나눗셈법과 비슷하게 모듈러 연산을 활용하지만 소수는 활용하지 않는다. - 문자열 해싱
- 키의 자료형이 문자열일 때도 사용할 수 있는 해시 함수
- 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱합니다.
# def solution(arr, target) :
# for i in range(len(arr)) :
# for j in range(i + 1, len(arr)) :
# if arr[i] + arr[j] == target :
# return True
# return False
#
# arr = [1, 2, 3, 4, 8]
# target = 6
# print(solution(arr, target))
#
# arr = [2, 3, 5, 9]
# target = 10
# print(solution(arr, target))
# -- 개선이 필요한 답안
def count_sort(arr, k) :
hashtable = [0] * (k + 1)
for num in arr :
# 현재 원소의 값이 k 이하인 때에만 처리
if num <= k :
# 현재 원소의 값을 인덱스로 해 해당 인덱스의 해시 테이블 값을 1로 설정
hashtable[num] = 1
return hashtable
def solution(arr, target) :
hashtable = count_sort(arr, target)
for num in arr :
complement = target - num
# target에서 현재 원소를 뺀 값이 해시 테이블에 있는지 확인
if (
complement != num
and complement >= 0
and complement <= target
and hashtable[complement] == 1
) :
return True
return False