기어가더라도 제대로

사물함의 각 칸에 이름과 번호가 있어서 바로 찾기가 쉽듯, 해시 테이블도 키를 인덱스로 변환하여 값을 넣는다. 정의 키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조 삽입은 O(1)이며 키를 알고 있다면, 삭제, 탐색도 O(1) 로 수행한다. 키를 잘게 잘라 인덱스로 만들어 사용한다는 것이 비슷하다. 해시 함수는 입력 받은 값을 특정 범위 내 숫자로 변경하는 함수 특별한 규칙이 있는 것은 아니다. 해시 충돌 Hash Collision 해시 충돌이란, 키값을 인덱싱한 결과 서로 다른 키지만, 인덱스 값이 같은 경우, 해시 충돌이라고 한다. 1. 선형 탐사법 충돌이 발생하면 옆으로 한 칸 이동한다. 2. 제곱 탐사법 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆..