해시 테이블 (Hash Table)
해시 테이블 (또는 해시 맵)은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)을 구현하는 자료구조.
해시 구조란?
- 키(Key)와 값(Value) 의 쌍으로 이루어진 데이터 구조. Key를 이용하여 데이터를 찾으므로, 속도를 빠르게 만드는 구조.
- 파이썬에서는 Dictionary (딕셔너리) 타입이 해시 테이블과 같은 구조임.
- 기본적으로는, 배열로 미리 Hash Table 크기만큼 생성해서 사용함. 공간은 많이 사용하지만, 시간은 빠르다는 장점이 있음.
- 검색이 많이 필요한 경우, 저장, 삭제, 읽기가 많은 경우, 캐쉬를 구현할 때 주로 사용됨.
| 장점 | 단점 |
| 데이터 저장/ 검색 속도가 빠름 | 일반적으로 저장공간이 조금 더 많이 필요함 |
| 키에 대한 데이터가 있는지 (중복) 확인이 쉬움 | 키에 대한 충동을 해결하지 위한 별도의 자료구조가 필요함 (충돌 해결 알고리즘) |
시간 복잡도
- 일반적인 경우 (충돌이 없는 경우): O(1)
- 최악의 경우 (모든 경우에 충돌이 발생하는 경우): O(n)
- 분할 상환 분석에 따른 시간 복잡도: O(1)
개념 정리
해시(Hash)
- 임의 값을 고정 길이로 변환하는 것
해시 함수 (Hash Function)
- 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수
- 즉, 특정 연산을 이용하여 키 값을 받아서 value를 가진 공간의 주소로 바꾸어주는 함수
- 해시 테이블을 인덱싱하기 위해, 해시 함수를 사용하는 것을 해싱 (Hashing) 이라고 함. 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법 중 하나.
- 해싱에는 다양한 알고리즘이 있으며, 최상의 분포를 제공하는 방법은 데이터에 따라 제각각.
- 성능이 좋은 해시 함수의 특징
- 해시 함수 값 충돌의 최소화
- 쉽고 빠른 연산
- 해시 테이블 전체에 해시 값이 균일하게 분포
- 사용할 키의 모든 정보를 이용하여 해싱
- 해시 테이블 사용 효율이 높을 것
- 유명한 해시 함수: SHA(Secure Hash Algorithm)
해시 테이블 (Hash Table)
- 해시 구조를 사용하는 데이터 구조
해시 값 (해시 주소, Hash Value, Hash Address)
- Key 값을 해시 함수에 넣어서 얻은 주소 값. 이 값을 통해 슬롯을 찾아감.
슬롯 (Slot)
- 한 개의 데이터를 저장할 수 있는 공간 (bucket)
충동 문제
아무리 좋은 해시 함수라도 충동 (Collision) 은 발생하게 됨.
생일 문제 (Birthday Problem)
충돌은 얼마나 많이 발생할까? 에 대한 예시.
여러 사람이 모였을 때 생일이 같은 2명이 존재할 확률을 구하는 문제.
실제로 23명만 모여도 50%를 넘고, 57명이 모이면 99%를 넘어섬.
해시 충돌을 해결하는 대표적인 방법
- 개별 체이닝 (Separate Chaining)
- 오픈 어드레싱 (Open Addressing)
개별 체이닝 (Separate Chaining)
오픈 해싱 (Open Hashing) 이라고도 함.
만약 해시 값이 중복되는 경우, 먼저 저장된 데이터에 연결 리스트를 이용해서 중복 해시 데이터를 연결함.
간단한 원리 요약
- 키의 해시 값 계산
- 해시 값을 이용해 배열의 인덱스 구함
- 같은 인덱스가 있다면 연결 리스트로 연결
개별 체이닝 한계점
- 해당 방식은 끝없이 key, value 쌍들을 넣을 수 있지만, 공간 효율성이 떨어짐.
- 하나의 hash value index에만 들어간다면 불균형한 구조가 될 가능성이 있음.
오픈 어드레싱 (Open Addressing)
클로즈 해싱 (Close hashing), Linear Probing 이라고도 함.
해시 중복이 발생하면, 해당 해시 값부터 순차적으로 빈 공간을 찾음. 가장 처음 찾는 빈 공간에 key와 value 저장.
오픈 어드레싱 한계점
- 사실상 무한정 저장할 수 있는 체이닝 방식과 달리, 오픈 어드레싱 방식은 전체 슬롯의 개수 이상은 저장할 수 없음.
- 충돌이 일어나면 테이블 공간 내에서 탐사 (Probing) 를 통해 빈 공간을 찾아 해결하며, 이 때문에 개별 체이닝 방식과 달리, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없음.
파이썬에서의 해시 테이블
- 해시 테이블로 구현된 파이썬의 자료형: 딕셔너리
- 파이썬의 해시 테이블이 충돌 시 사용하는 방식: 오픈 어드레싱 방식
- 체이닝 시 malloc으로 메모리를 할당하는 오버헤드가 높아 오픈 어드레싱을 택함.
| no | title | leedcode | status |
| 28 | 해시맵 디자인 | 리트코드 706 | X |
| 29 | 보석과 돌 | 리트코드 771 | O |
| 30 | 중복 문자 없는 가장 긴 부분 문자열 | 리트코드 3 | X |
| 31 | 상위 k 빈도 요소 | 리트코드 347 | O |
No.28 해시맵 디자인 (아직 못 품)
My Solution) 어디서 틀렸는지 모르겠음ㅠㅜ
class MyHashMap:
def __init__(self):
"""
Initialize your data structure here.
"""
self.size = 1000
self.hash_table = [None for i in range(self.size)]
def put(self, key: int, value: int) -> None:
"""
value will always be non-negative.
"""
hash_value = key % self.size
self.hash_table[hash_value] = value
return
# if self.hash_table[hash_value] != 0:
# for i in range(len(self.hash_table[hash_value])):
# if self.hash_table[hash_value][i][0] == key:
# self.hash_table[hash_value][i][1] == value
# return
# else:
# self.hash_table[hash_value] = [[key, value]]
def get(self, key: int) -> int:
"""
Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
"""
hash_value = key % self.size
if self.hash_table[hash_value] != None:
return self.hash_table[hash_value]
# for i in range(len(self.hash_table[hash_value])):
# if self.hash_table[hash_value][i][0] == key:
# return self.hash_table[hash_value][i][1]
else:
return -1
def remove(self, key: int) -> None:
"""
Removes the mapping of the specified value key if this map contains a mapping for the key
"""
hash_value = key % self.size
if self.hash_table[hash_value] != None:
self.hash_table[hash_value] = None
return
# for i in range(len(self.hash_table[hash_value])):
# if self.hash_table[hash_value][i][0] == key:
# self.hash_table[hash_value][i][0] == 0
# self.hash_table[hash_value][i][1] == 0
# return
# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)No.29 보석과 돌
My Solution) defaultdict를 이용한 비교 생략
32ms, 14.2MB
시간 복잡도: O(n)
책 풀이
Solution 1) 해시 테이블을 이용한 풀이
32ms, 14.4MB
Solution 2) defaultdict를 이용한 비교 생략
Solution 3) Counter로 계산 생략
32ms, 14.3MB
Solution 4) 파이썬다운 방식
28ms, 14.3MB
No.30 중복 문자 없는 가장 긴 부분 문자열 (아직 못 품)
No.31 상위 K 빈도 요소
My Solution 1)
- Counter.most_common() 까지 생각은 했는데, 튜플을 어떻게 분리해서 출력해야 할지 모르겠었음.
- [(1, 3), (2, 2)] 이런 식으로 출력됨.
My Solution 2) dict 정렬
96ms, 18.6MB
시간 복잡도: O(N*logN)
책 풀이
Solution 1) Counter 를 이용한 음수 순 추출
아직 이해를 못했음..
Solution 2) 파이썬다운 방식
144ms, 18.6MB
zip() 함수
zip() 함수는 2개 이상의 시퀀스를 짧은 길이를 기준으로, 일대일 대응하는 새로운 튜플 시퀀스를 만드는 역할을 함.
- 파이썬 2에서는 zip()의 결과가 바로 리스트가 됨.
- 그러나 파이썬 3+ 에서는 제너레이터를 리턴하기 때문에, 제너레이터에서 실젯값을 추출하기 위해서는 list()로 한 번 더 묶어줘야 함.
- zip()의 결과 자체는 리스트 시쿼스가 아닌 튜플 시퀀스를 만들기 때문에, 값을 변경하는게 불가능한 불변 (Immutable) 객체임.
- list가 아닌 딕셔너리로도 만들 수도 있음.
아스테리스크(*)
파이썬에서 아스테리스크는 크게 4가지 경우에서 사용됨.
- 곱셈 및 거듭제곱 연산으로 사용할 때
- 리스트형 컨테이너 타입의 데이터를 반복 확장하고자 할 때
- 가변인자 (Variadic Arguments)를 사용하고자 할 때
- 컨테이너 타입의 데이터를 Unpacking 할 때
- 언패킹뿐만 아니라 함수의 파라미터가 되었을 때는 반대로 패킹 (Packing) 도 가능함 (사실상 3번과 동일한 이야기 같음, 함수가 받은 인자의 개수를 유연하게 지정해 주기 때문에)
CODE 1
# Unpacking 1
a, b, *c = (1, 2, 3, 4, 5)
print(a)
print(b)
print(c)
OUTPUT 1
# Unpacking 1
1
2
[3, 4, 5]
CODE 2
# Unpacking 2
a, b, *_ = (1, 2, 3, 4, 5)
print(a)
print(b)
OUTPUT 2
# Unpacking 2
1
2
CODE 3
# Unpacking3
a, b, *c, d = (1, 2, 3, 4, 5, 6)
print(a)
print(b)
print(c)
print(d)
OUTPUT 3
# Unpacking3
1
2
[3, 4, 5]
6
CODE 4
# Unpacking 4
a, b, *_, d = (1, 2, 3, 4, 5, 6, 7)
print(a)
print(b)
print(d)
OUTPUT 4
# Unpacking 4
1
2
7
'Python Basic > 파이썬 알고리즘 인터뷰' 카테고리의 다른 글
| [3부] 10장 데크, 우선순위 큐 (0) | 2021.02.22 |
|---|---|
| [3부] 09장 스택, 큐 (0) | 2021.02.16 |
| [3부] 08장 연결 리스트 (0) | 2021.02.14 |
| [3부] 07장 배열 (0) | 2021.02.11 |
| [2부] 06장 문자열 조작 (0) | 2021.02.09 |
