해시는 자료를 입력할 때부터 검색하기 쉬운 위치에 삽입하는 방법이다.
해시는 검색방법이라기 보다는 빠른 검색을 위한 자료관리 기법이다.
쉬운 예로 실생활의 주소록을 생각하면 된다. 주소록은 가나다 순으로 페이지를 미리분류하고 이름의 첫 글자를 기준으로 주소를 적는다.
주소록 처럼 찾기 쉽게 인덱싱을 만들어 놓은 형태를 해싱(Hasing)이라고 한다.
해시테이블 자료가 저장되는 전체 저장소를 해시테이블(Hash Table)이라고 한다.
해시 테이블은 여러 개의 버킷으로 나누어지는데, 주소록의 ㄱ,ㄴ,ㄷ,ㄹ 과 같은 인덱스 페이지가 버킷이다.
버킷은 여러 개의 슬롯으로 구성되어 있는데, 슬롯은 버킷에 데이터가 저장되는 단위이다. 즉, 주소록에서 한 명의 주소를 적는 칸의 단위라고 보면 된다.
슬롯1칸짜리 버킷 10개를 가진 해시테이블에 사용자로부터 값을 5개입력받아 저장후 값이 존재하는지 검색가능한 프로그램이다.
여기서 우리는 문제에 직면한다. 만약 1의자리 숫자가 중복이된다면 값이 충돌하게된다.
그래서 우리는 이 문제를 해결하기 위해서 각 버킷의 슬롯갯수를 늘려주기로 했다.
선형탐색
슬롯이 넉넉하고 해시함수가 정교해도 언제나 충돌가능성은 있다.
선형탐색법은 충돌이 발생할 경우 이 데이터를 버리지 않고 다른 버킷에 대신 집어넣는 방법이다.
대체 버킷을 찾는 가장 간단한 방법은 바로 옆칸에 적어놓는 것이다.
주소록의 경우 ㄱ칸이 모자라면 ㄴ칸을 잠시 빌려 쓰도록 하는 것이다.
입력된 데이터의 버킷 번호를 조사하여 데이터를 넣되 이 버킷이 비어있지 않다면 다음버킷을 조사한다.
만약 다음 버킷이 비어있지 않다면 그 다음 빈 버킷을 계속해서 찾아 빈 버킷에 값을 써 넣는다.
이분검색이 제일많이 나온다.
다음시간엔 정렬