Hash Table
- Hash Table의 역할:
- 동적 집합(dynamic set)을 다루며 삽입(INSERT), 탐색(SEARCH), 삭제(DELETE) 연산을 지원하는 데이터 구조.
- 컴파일러의 심볼 테이블(symbol table)과 같은 곳에서, 임의의 문자열을 키(key)로 사용해 효율적으로 요소를 관리.
- 효율성:
- 해시 테이블은 딕셔너리(dictionary)를 구현하기 위한 효과적인 데이터 구조로 사용됩니다.
- 탐색 시간:
- 최악의 경우: (모든 요소가 충돌하여 단일 체인으로 연결된 경우).
- 일반적인 경우(합리적인 가정 하): 평균 탐색 시간은 O(1) (상수 시간).
- 충돌 해결 방법:
- Chaining (체이닝): 같은 해시 값이 여러 번 발생할 때, 연결 리스트를 사용해 충돌을 해결.
- Open Addressing (개방 주소법): 충돌 시 다른 해시 주소로 재탐색.
- 시간과 공간의 효율성:
- 시간 효율성: 빠른 탐색과 삽입이 가능.
- 공간 효율성: 메모리 사용이 효율적이지만, 충돌이 많아지면 성능 저하 가능.
(시험 출제 예정) 해시 테이블을 언제 쓰는지?
- dynamic set 자료형을 다룰 때 용이
- 즉, insert, delete, search 연산을 자주할 때 해시 테이블이 용이
- 자료구조에 따라 시간 감소에 용이한 자료구조, 공간 효율화에 용이한 자료구조가 있는데,
w. hash table : 시간 희생, 공간 효율화
w/o. hash table : 시간 효율화, 공간 희생
Reference
- Korea University - CVO101
References
- Korea University - CVO101
'IT 일반 > 자료구조(개념) - [인강] 코드잇, [대학원] 전공 수업' 카테고리의 다른 글
[대학원-자료구조 6] MST : Kruskal's Alg., Prim's Alg. (1) | 2024.10.21 |
---|---|
[대학원-자료구조 5] Disjoint Sets(서로소 집합) 자료구조 (1) | 2024.10.21 |
[대학원-자료구조 4] Elementary Graph Algorithms : BFS, DFS (1) | 2024.10.20 |
[대학원-자료구조 3] 기타 정렬 알고리즘 - MergeSort, QuickSort (0) | 2024.10.20 |
[대학원-자료구조 1~2] Tree와 Graph, Heap (2) | 2024.10.19 |