해시 함수과 이진 탐색

1. 해시 함수
임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
해시 함수에 의해 얻어지는 값은 해시값, 해시 코드, 또는 간단하게 해시라고 한다
매우 빠른 데이터 검색을 위해 널리 사용되고, 암호학에서도 사용될 수 있다
데이터의 값을 이용해 저장하고, 찾을 수 있다

2. Direct Addressing Table
Direct Addressing Table은 key-value쌍의 데이터를 배열에 저장할, key값을 직접적으로 배열의 인덱스로 사용하는 방법
(ex. 키 값이 100인 데이터가 있다면, 이는 배열 인덱스가 100인 위치에 key값을 저장하고 뒤에 데이터를 연결)
찾고자 하는 데이터의 key만 알고있으면 즉시 위치를 찾는 것이 가능하므로 탐색, 저장, 삭제 모두 선형시간

3. Hash Table
Derect Addressing Table과 달리 key값을 함수(해시 함수)를 통해 계산을 한 후,
그 결과 값을 배열의 인덱스로 사용하여 저장하는 방식
hash(key) => 이를 해시값이라고 부름
충돌을 허용하지만 최소화하는 방법 중 하나로 Chaining방식을 사용
(Chaining : 데이터들을 포인터를 이용해 서로 체인 형태로 엮어 나가는 것을 뜻함)
동일한 해시값이 출력되어 충돌이 일어나면, 그 위치에 있던 데이터에 key값을 포인터로 뒤이어 연결
최초로 hash(key)위치에 저장된 데이터를 시작으로 같은 해시값이 출력되는 데이터는 모두 연결 리스트의 형태를 취한다 (연결 리스트와 비슷)

4. 이진 탐색
데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘
배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교
-> X가 중간값보다 작으면 좌측의 데이터들을 대상으로, 크면 우측을 대상으로 다시 탐색
->동일한 방법으로 다시 중간값을 임의로 선택하고 비교
ex) 
{17, 28, 43, 67, 88, 92, 100} 43찾기
1) 가운데 값인 67선택, 43과 비교 -> 좌측을 타겟
2) 가운데 값인 28선택, 43과 비교 -> 우측을 타겟
원하는 값을 찾으면 종료
구현 : 인덱스를 이용 / 인덱스의 최소, 최대값을 따로 저장하여 탐색이 진행될 때마다 갱신하고 탐색하는 배열의 범위를 줄여나감