Hash
프로그래밍에서 데이터를 빠르고 효율적으로 저장하고 검색하는 방법은 매우 중요하다. 해시는 이러한 요구를 충족시키는 핵심 기술로, 다양한 자료구조와 알고리즘에서 널리 사용된다. 이번 글에서는 해시의 개념, 특징, 활용 방법에 대해 자세히 알아보자.
해시 함수
해시 함수(Hash Function)는 임의의 크기를 가진 입력 데이터를 고정된 크기의 정수로 변환하는 함수이다. 이 정수는 해시값(Hash value) 또는 해시코드(Hash Code)라고 불리며, 일반적으로 데이터가 저장될 배열의 인덱스로 사용된다.
특징
•
결정론적: 동일한 입력 값은 항상 동일한 해시 값을 반환한다.
•
고속성: 입력 데이터를 빠르게 해시 값으로 변환할 수 있다.
•
충돌 가능성: 서로 다른 입력 값이 동일한 해시 값을 가질수 있다.
해시맵(Hash Map)
배열은 데이터의 빠른 접근과 업데이트를 가능하게 하지만, 정수형 인덱스만 사용해야하고 크기가 고정되어야 한다는 제한이 있다. 해시맵(또는 해시 테이블)은 이러한 문제를 해결하기 위해 고안되었다. 해시 함수와 배열을 결합하면 해시맵이 만들어 진다. 해시 맵은 키-값 쌍을 저장한다.
해시 맵은 다음과 같은 장점을 제공한다.
•
데이터 검색, 삽입, 삭제 작업을 평균 의 시간 복잡도로 수행
•
문자열, 객체 등 다양한 데이터 유형을 키로 활용 가능
충돌(Collision)
충돌이란 두 개이상의 키가 동일한 해시 값을 갖는 상황을 충돌이라고 한다. 충돌이 발생하면 올바른 데이터 접근이 어려워질수 있으므로 이를 해결하기 위한 방법이 필요하다.
충돌 해결 방법
체이닝(Chaining)
•
해시 테이블의 각 슬롯에 연결 리스트를 사용한다.
•
동일한 해시 값을 가진 키-값 쌍을 리스트에 추가한다.
•
검색 시 해당 슬롯의 리스트를 순회하여 키를 비교한다.
오픈 어드레싱(Open Addressing)
•
충돌이 발생하면 빈 슬롯을 찾아 데이터를 저장한다.
•
대표적인 방법: 선형탐사, 이차탐사
충돌 최소화를 위한 설계
•
해시 함수의 설계: 데이터가 고르게 분포되도록 설계
•
해시 테이블 크기: 소수(Prime number)를 사용하여 충돌 확률을 낮춤
◦
자주 사용하는 소수: 10,007 / 1,000,003 / 1,000,000,007
Hash Map vs Array vs Set
특징 | 해시 맵 | 배열 List | 집합 Set |
데이터 구조 | 키-값 쌍 저장 | 값만 저장 | 고유 값만 저장 |
시간 복잡도
(검색) | O(1) | O(n) | O(1) |
시간 복잡도
(삽입/삭제) | O(1) | O(n) | O(1) |
중복 허용 | 키 중복 불가, 값은 가능 | 중복 허용 | 중복 불가 |
순서 유지 | 유지하지 않음 | 유지 | 유지하지 않음 |
•
해시 맵: 키-값 쌍 저장 및 검색이 필요할 때 사용
•
배열: 순서가 중요하거나 정수 인덱스를 사용할 때 적합
•
집합: 고유한 값만 저장하고자 할 때 활용
Python에서 해시 맵 사용 방법
파이썬에서는 딕셔너리(Dictionary)로 해시 맵을 구현한다. 빠르게 해시 맵 사용 방법에 대해 익혀보자.
해시 맵 선언
hash_map = {}
Python
복사
값 추가 및 업데이트
hash_map['key1'] = 'value1' # 추가
hash_map['key1'] = 'value2' # 업데이트
Python
복사
값 검색
value = hash_map['key1'] # 'value2'
Python
복사
키 존재 여부 확인
'key1' in hash_map # True
Python
복사
값 삭제
del hash_map['key1']
Python
복사
키와 값 반복
for key, value in hash_map.items():
print(f'{key}: {value}')
Python
복사
my_hash_map = {}
my_hash_map[4] = 83
print(my_hash_map[4])
print(4 in my_hash_map)
print(854 in my_hash_map)
my_hash_map[8] = 327
my_hash_map[45] = 82523
for key, val in my_hash_map.items():
print(f"{key}: {val}")
del my_hash_map[45]
len(my_hash_map)
Python
복사
팁: 배열을 해시 맵 키로 사용하는 방법
해시 맵의 키는 일반적으로 불변(Immutable)이어야 한다. 배열을 가변적이기 때문에 직접 키로 사용할 수 없다. 따라서 배열을 불변 객체로 변환해야 한다. Python에서 배열을 키로 변환하는 방법에 대해 알아보자.
튜플(Tuple)로 변환
튜플은 불변 객체이므로 배열을 튜플로 변환하여 사용한다.
arr = [1, 2, 3]
key = tuple(arr)
Python
복사
문자열로 변환
배열을 문자열로 변환하여 고유 키를 생성한다.
arr = [1, 2, 3]
key = ','.join(map(str, arr))
Python
복사
마무리
해시는 데이터의 빠른 검색과 효율적인 관리를 위한 강력한 알고리즘이다. 특히 코딩테스트에서 자주 등장하므로, 해시 함수의 원리와 해시 맵의 활용 방법을 철저히 익히는 것이 중요하다. 다양한 언어에서 제공하는 내장 해시를 적극 활용하여 문제를 풀어보길 바란다.
관련 문제들
Related Posts
Search
