해시란?

자료구조)해시 - 빠른속도 but 리소스 소모
해싱: 임의의 길이의 값을 해시함수를 사용하여 고정된 크기의 값으로 변환
해시테이블 : 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조
충돌(적재율(키의개수/해시테이블크기)가 1초과일경우)이 발생할 수 있음.
충돌해결 : 
1.chaining (구조개선) - 동일한 버킷으로 저장할 때 연결리스트 형태로 저장함.
2.open addressing - 동일한 주소에 다른 데이터가 있을 경우 다른 주소도 이용할 수 있게 함.
 다른 비어있는 자리를 탐색(탐사Probing)
2-1. open addressing의 3가지 충돌처리기법
 1. 선형탐사 linear probing - 기본적. 바로 인접한 인덱스에 데이터를 삽입. 
    데이터 밀집되는 클러스터링 문제가 발생하고 이로인해 탐색,삭제가 느려짐.
 2. 제곱탐사 quadratic probing - 제곱으로 탐사(1^2, 2^2 ...) 폭 넓게 탐사하여 탐색,삭제가 더 효율적.
    but 초기해시값이 같을 경우 클러스터링 문제 발생
 3. 이중해싱 double hashing - 클러스터링 문제를 피하기 위함. 
    1번해시함수 해시값 찾기/ 2번해시함수는 충돌이 발생했을때 탐사폭 계산