해시 테이블
1. 개념
해시 - 고기와 감자를 잘게다져 요리한것. 키 값을 잘게 다져 특정 인덱스로 변경
-> 키와 값을 받아 키를 해싱(잘게 쪼개어)하여 도출된 인덱스에 값을 저장하는 구조
- 해시테이블이란?
입력받은 값을 특정범위내의 숫자로 변경하는 함수
2. 해시충돌
해시함수를 거친 값이 동일하다면, 데이터가 삽입되는 위치가 중복되는 현상
2-1. 해시충돌해결방법 1 : 선형탐사법
충돌이 발생하면 다음인덱스에 데이터 저장. 충돌이 발생하면 다른곳에 저장.
2-2. 해시충돌해결방법 2 : 제곱탐사법
충돌이 발생한 지점의 제곱만큼 옆으로 이동하여 데이터 저장
2-3. 해시충돌해결방법 3 : 이중 해싱
A함수를 이용해 충돌이 발생하면 B함수를 통해 해싱하는것
2-4. 해시충돌해결방법 4 : 분리 연결
충돌이 발생하면, 연결리스트로직을 이용해 메모리에 저장. 한 메모리 내에 차지하는 데이터가 무한정 늘어날수 있음.