CS/Data Structure & Algorithm
Hash Table & Dictionary
dohem
2024. 4. 12. 10:48
Hash Table
- 효율적인 탐색(빠른 탐색)을 위한 자료구조
- key-value 쌍의 데이터를 입력 받음
- hash function에 key값을 입력으로 넣어 얻은 해시값을 위치로 지정하여 데이터 쌍(key-value)을 저장
- 저장, 삭제, 검색의 시간복잡도 O(1)
- Array List 또는 Array List+Linked List로 구현 가능 → 파이썬의 경우 Array List로 구현됨
Direct-address Table
- key 값이 index가 되는 테이블
- 낭비되는 메모리가 발생
- 문자열이 key로 들어오면 index로 사용 불가
- 이러한 문제를 해결하기 위해 Hash Table 사용
Collision
- 해시 테이블에서 인덱스 간 중복이 발생하는 것(충돌)
- Open Addressing, Seperate Chaining 기법이 있음
Open Addressing
- 충돌되면 바로 다음 인덱스에 저장
Dictionary
- key 값은 유일해야 함(중복x)
- (코테) 시간복잡도를 줄이기 위해 메모리를 사용 하는 것
- key in {} 사용이 핵심
리스트의 경우 특정 값을 찾을 때, 하나씩 탐색하므로 O(n)이지만, 해시테이블은 O(1)으로 바로 탐색