-
해시 테이블(Hash Table)ALGORITM 2022. 4. 18. 09:41
키(Key)에 데이터(Value)를 저장하는 데이터 구조
- Key를 통해 데이터를 바로 받아올 수 있음 → 속도가 획기적으로 빨라짐
- 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예 - Key를 가지고 바로 데이터(Value)를 꺼냄
- 보통 배열로 미리 Hash Table 사이즈만큼 생성 후 사용(공간과 탐색 시간을 맞바꾸는 기법)
- 파이썬에서는 해쉬를 별도로 구현할 필요 없음 - 딕셔너리 타입을 사용하면 되기 때문
해쉬 테이블 시간 복잡도
- 일반적인 경우(Collision이 없는 경우)는 O(1)
- 최악의 경우(Collision이 모두 발생하는 경우)는 O(n)
반응형'ALGORITM' 카테고리의 다른 글
스택(stack)과 큐(queue) (0) 2022.04.18 연결리스트(linked list) (0) 2022.04.18 배열(Array) (0) 2022.04.11