[대학원-자료구조 7~] Hash Table : an example of dictionary

 

 

Hash Table

 

• Hash Table의 역할:
  • 동적 집합(dynamic set)을 다루며 삽입(INSERT), 탐색(SEARCH), 삭제(DELETE) 연산을 지원하는 데이터 구조.
  • 컴파일러의 심볼 테이블(symbol table)과 같은 곳에서, 임의의 문자열을 키(key)로 사용해 효율적으로 요소를 관리.
• 효율성:
  • 해시 테이블은 딕셔너리(dictionary)를 구현하기 위한 효과적인 데이터 구조로 사용됩니다.
  • 탐색 시간:
    • 최악의 경우: Θ(n) (모든 요소가 충돌하여 단일 체인으로 연결된 경우).
    • 일반적인 경우(합리적인 가정 하): 평균 탐색 시간은 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 

- https://databridge.tistory.com/50