해시테이블

자료구조 : 해시테이블 (Hash Table) 

해시(Hash)는 키 값을 해시 함수(Hash function)으로 해싱하여 해시테이블의 특정 위치로 직접 엑세스하도록 만든 방식이다.
키 값을 통해 직접 엑세스하기 위해서 모든 가능한 키 값을 갖는 배열을 만들면, 배열크기가 엄청나게 커지게 된다. 예를 들어, 주민등록번호를 키 값으로 하는 경우, 000000-0000000 부터 999999-9999999까지 10의 13승의 배열 공간이 필요한데, 만약 회원수가 1000명인 경우, 1000명을 저장하기 위해 10^13의 엄청난 배열 공간이 필요하게 된다. 이렇게 낭비되는 공간을 줄이기 위해 해시 함수를 사용하게 되는데, 이 함수는 적은 공간 안에서 모든 키를 직접 찾아갈 수 있도록 해준다. 하지만 경우에 따라 서로 다른 키가 동일한 해시테이블 버켓 위치를 가리킬 수 있는데, 이를 해결하기 위해 여러 Collision Resolution 방식이 사용된다. Collision Resolution의 방식으로 Linear Probing, Quadratic Probing, Rehashing (Double Hashing), Chaining 등 여러가지가 있다. 해시테이블 자료구조는 추가, 삭제, 검색에서 O(1)의 시간이 소요된다.