탐색1 [Algorithms] 해쉬 테이블(Hash Table) 해시 테이블은 궁극의 탐색 알고리즘이라고 불린다. 데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해싱(hashing)하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것이 기본적인 컨셉이다. 해시 테이블은 한마디로 공간을 팔아 성능을 얻어내는 것이다. 해시값으로의 접근은 다음과 같은 방식으로 이루어진다. Table[3819] = 123817; 데이터는 해시 함수를 거치면 다음 그림처럼 테이블 내의 주소(즉, 인덱스)로 변환된다. 해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다. 그렇지 않으면, collision 현상이 발생한다. 통계적으로 해시 테이블의 공간 사용률이 70%~80%에 이르면 성능 저하가 나타나기 시작한다. 다른 배열 형식의.. 2017. 4. 21. 이전 1 다음
