선형탐사법 (1) 썸네일형 리스트형 해시 테이블에 대하여 (about Hash Table) 해시 테이블은 한마디로 공간을 팔아 시간을 사다 라는 말로 표현할 수 있다. 주소를 이용해서 배열같이 직접 탐색이 가능하다. 해시테이블의 기본 개념은 다음과 같다. 데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것, 이것이 바로 해시 테이블의 기본 개념이다. 해시테이블은 특이하게도 데이터가 입력되지 않은 여유공간이 많아야 제 성능을 발휘할 수 있다. 테이블 내의 주소를 계산할 때는 해시함수를 이용하는 데 이에는 두가지 방법이 사용된다. 1) 나눗셈법 주소 = 입력값 % 테이블의 크기 하지만 이는 충돌과 클러스터 문제가 발생할 가능성이 높다. 2) 자릿수 접기 Hello -> 72 + 101 + 108 + 111 = 500.. 이전 1 다음