해시(Hash)란?
- 해시 테이블은 key와 value를 매핑해서 데이터를 저장하는 자료구조이다.
- 파이썬에서는 기본적으로 제공되는 딕셔너리 자료형이 해시 테이블과 같은 구조이다.
- 보통 배열을 미리 해시 테이블 size만큼 생성 후에 사용한다. (공간과 탐색 시간을 맞바꾸는 기법)
- 하지만, 파이썬은 딕셔너리 타입이 존재하기 때문에 따로 해시를 구현할 필요가 없다.
용어
| 용어 | 설명 |
|---|---|
| 키(key) | 고유의 값으로 해시 함수의 Input |
| 해시 테이블(Hash Table) or 해시 맵(Hash Map) | key와 value를 매핑해서 데이터를 저장하는 자료구조 |
| 해시 함수(Hash Function) | 임의의 값을 고정된 길이의 데이터로 변환하는 함수. 다양한 길이의 키를 고정된 길이의 해시로 변환시키므로 저장소를 효율적으로 운영할 수 있게 해준다. |
| 해시 값(Hash Value) | key에 해시 함수를 적용해서 얻은 값 |
| 버킷(Bucket) | 한 개의 데이터를 저장할 수 있는 공간 |
해시의 특징
- 연산의 평균 시간복잡도가 O(1)로 데이터 저장 및 읽기 처리 속도가 매우 빠르다.
- 배열의 index와 같이 해시 함수를 통해 얻은 키값으로 그 위치를 찾아주면 된다.
- worst case인 경우 O(N)의 복잡도를 갖는다 → 충돌(Collision) 때문
충돌(Collision) - 여러 개의 키값이 해시 함수를 통해 같은 해시 값을 갖는 경우
해시 충돌 해결
1. Chaining
충돌 발생 시 버킷에 연결리스트 자료구조를 이용해 데이터를 연결하여 충돌을 해결한다.
2. Open Addressing
충돌이 발생하면 빈 버킷을 찾아 데이터를 저장하는 방법으로 대표적으로 선형 탐색 방법이 있다.
- 선형 탐색 - 충돌이 발생하면 해당 위치부터 순차적으로 버킷을 하나씩 탐색
_ 제곱 탐색 - 충돌이 발생하면 해당 위치부터 제곱만큼 떨어진 다음 버킷을 탐색 - 이중 해시 - 충돌이 발생하면 다른 해시 함수를 한 번 더 적용
해시 언제 사용하면 좋을까
1. 리스트를 쓸 수 없을 때
- 리스트는 숫자 인덱스를 이용하여 원소에 접근하는데 즉 list[1]은 가능하지만 list['a']는 불가능하다.
- 인덱스 값을 숫자가 아닌 다른 값 '문자열', '튜플' 등을 사용하려고 할 때 딕셔너리를 사용하면 좋다.
2. 빠른 접근/탐색이 필요할 때
- 딕셔너리 함수의 시간복잡도은 대부분 O(1)이므로 아주 빠른 자료구조이다.
3. 집계가 필요할 때
- 코딩테스트에서 원소의 개수를 세는 문제가 자주 출제된다.
- 이때, 해시와 collections 모듈의 Counter 클래스를 사용하면 아주 빠르게 문제를 풀 수 있다.
딕셔너리와 리스트의 시간복잡도 차이
| Operation | Dictionary | List |
|---|---|---|
| Get Item | O(1) | O(1) |
| Update Item | O(1) | O(1)~O(N) |
| Update Item | O(1) | O(1) |
| Delete Item | O(1) | O(1)~O(N) |
| Search Item | O(1) | O(N) |
👉 즉, 원소를 넣거나 삭제, 찾는 일이 많을 때에는 딕셔너리를 사용하는 것이 좋다.
chick! chick!