-
Hash Table : 키(key)에 데이터(value)를 저장하는 데이터 구조
- 파이썬에서는 해쉬를 별도 구현하지 않아도 된다. 딕셔너리 사용.
-
용어정리
- 해쉬 : 임의 값을 고정 길이로 변환하는 것
- 해쉬 테이블 : key값의 연산을 위해 직접 접근이 가능한 자료구조
- 해싱 함수 : key에 대해 연산을 이용해 데이터 위치를 찾을 수 있는 함수 (SHA-1, SHA-256 등 다양한 함수들이 있음)
- 해쉬 값, 해쉬 주소 : key를 해싱 함수로 연산하고, hash table에서 해당 key에 대한 data를 찾을 수 있음
-
장점
- 데이터 저장/읽기 속도가 빠르다 (검색 속도)
- 검색량이 많을 때 / 저장, 삭제, 읽기가 빈번할 때 / 캐시 구현시 사용
-
단점
- 많은 저장 공간 필요 (데이터 저장 전 미리 공간 확보 필요)
- 순서가 있는 배열에 어울리지 않음
- 여러 키에 해당하는 주소 동일할 때에, 충돌을 해결해야함 (해쉬 충돌)
- Chaining 기법
- Linear Probing 기법
-
시간복잡도
- 저장, 삭제, 검색 충돌이 일어나지 않는 일반적인 경우에 O(1)
- 이것은 해시 함수의 연산을 고려하지 않은 것. 해시 함수가 복잡하다면, 시간복잡도는 이것에 의존성이 더 높아질 수 있다.
한 쪽 끝에서만 자료를 넣고 뺄 수 있는 Last In First Out 형식의 자료 구조. 즉, 가장 최근에 추가한 항목이 가장 먼저 제거 된다.
-
실행 취소 등에서 사용 된다.
-
dfs 알고리즘에서 사용된다.
파이썬에서는 쓰는 list가 스택 구조이다.
-
시간 복잡도
- pop() 은 O(1), pop(k) 는 O(k)
- append()는 O(1)