Challenge In 20s Ph.D.

- 키값을 난수로 변환하여 필요한 주소를 산출하는 직접 주소법
- 해시 함수를 이용하여 데이터베이스에서 자료를 색인하고 신속하게 자료를 검색하는데 사용

- 임의의 길이에 이진 문자열을 고정된 길이의 이진 문자열로 매핑하여 주는 함수
- 검색키에 있는 문자를 이진으로 표현한 후에 계산 수행
- h는 K를 B에 대응시키는 함수
 ■ K: 모든 검색키 값의 집합
 ■ B: 모든 버켓 주소의 집합
 ■ h: 해시 함수
- 레코드 키 값(k) → 해싱 함수 h(k)→ 해상표의 상대주소
- hash의 사용
 ■ 해시 파일 구조: 레코드의 검색키 값에 대한 함수 계산을 통해 원하는 레코드를 가진 디스크 블록의 주소를 직접 얻을 수 있음
 ■ 해시 인덱스 구조: 검색키들과 관련된 포인터들을 해시 파일 구조로 조직화할 수 있음

- 해시 파일 구조는 이름을 키로 갖는 account 파일의 해시 함수는 다음과 같다.
- 레코드의 분배가 균등해야 함 (그렇지 않으면, 하나의 버켓에 몰려있는 현상이 있을 수 있어 특정 버켓에 있는 레코드를 모두 검색해야 하는 문제점이 있을 수 있음)

- 검색키, 이와 연관된 포인터를 해시 파일 구조 안에 구성
- 2차 해시 인덱스는 다음과 같다.

- 레코드의 저장을 위한 자료구조로써 해상함수로부터 계산된 함수값에 해당하는 위치에 각 레코드를 한 개 이상 보관할 수 있는 버켓(bucket)들로 구성된 기억 공간이며, 주어진 key값을 가지고 해당 레코드를 빠르게 검색하기 위한 수단을 제공하며 레코드의 삽입과 삭제가 용이
- 해시 테이블은 파일의 레코드의 키 값에 대응하는 해시주소와 레코드를 저장하는 공간은 버켓으로 구성
- 포인터를 사용하여 구현하는 경우에는 실제의 레코드 대신에 레코드가 저장되어있는 메모리 포인터를 저장
- 파일 내의 키 값에 해시함수를 적용하여 해시주소를 생성



- 해슁의 절차
 ■ 파일 내 모든 레코드의 키 값을 해시함수를 사용해 해시주소Hash Address를 구한다. 
 ■ 해시주소로 해시 테이블을 구성, 해시주소의 버켓에 레코드를 입력한다. 
 ■ 검색대상 레코드의 키 값에 해시함수를 적용, 해시주소를 구한다. 
 ■ 해시 테이블에서 해시주소로 레코드를 검색 

- 해시 테이블: 해시 테이블의 크기는 파일의 크기보다 커야한다. 왜냐하면, 주어진 n개의 레코드에 대해 n개의 해시주소를 생성하기 위한 해시함수는 찾는 것은 불가능하기 때문이다. 대부분의 경우에는 일정한 범위에 산발적으로 데이터가 분포하기 때문에 이러한 분포를 가진 데이터를 함수를 적용하여 최대한 밀집된 범위의 주소로 매핑하는 것은 한계가 있다.
- 해시 테이블의 크기가 적어지는 경우에는 서로 다른 키 값에 대해 동일 해시주소가 생성되는 경우가 발생하는데 이러한 현상을 해시충돌Hash Collision이라고 한다.

- 해시 테이블의 검색 속도는 O(1+n/m)으로 표현
 ■ m은 slot의 개수
 ■ n은 원소의 개수
 ■ n/m은 흔히 load factor로 표현