: 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것
→ 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다
데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌나는 현상 ⇒ Collision 현상
그래도 해시 테이블을 쓰는 이유는?
- 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해
- 하드디스크나 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시 값으로 매핑하면 작은 메모리로도 프로세스 관리 가능
- 언제나 동일한 해시 값 리턴, index를 알면 빠른 데이터 검색 가능
- 해시 테이블의 시간 복잡도 O(1), 이진탐색트리는 O(logN)
충돌 문제 해결
- 체이닝 : 연결리스트로 노드를 계속 추가해가는 방식 (제한 없이 연결 가능 but 메모리 문제)
- Open Addressing : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용(해당 키 값에 이미 저장되어있으면 다음 주소에 저장)
- 선형 탐사 : 정해진 고정 폭으로 옮겨 해시 값의 중복을 피함
- 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시 값의 중복을 피함
