구현방법
- Array list based (Open addressing) - 파이썬
- Array list + Linked list based (Seperate chaining)
() 괄호 안 내용은 충돌 해결 방법
Find key O(1)
해시테이블
Hash table은 효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key-value쌍의 데이터를 입력받습니다. hash function h에 key값을 입력으로 넣어 얻은 해시값h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장합니다. 저장, 삭제, 검색의 시간복잡도는 모두 O(1)입니다.
0~8까지 범위 내 리턴.
Direct-address Table
키값이 index가 되는 Table
단점:
1. 메모리 낭비
2. 문자열 입력
문제를 해결하기 위해 Hash Table을 생각
Collision
데이터가 이미 있는 충돌
- 해결방법 (다음 인덱스에 저장)
키값에 해당하는 인덱스로 찾아가는 과정이 O(1)
