이차 조사1 [알고리즘] ep4) 해시테이블(hashtable) 선형검색에 반해 해시테이블의 검색시간은 평균적으로 상수시간이다 (사전에 삽입된 모든 키가 충돌하는 최악의 경우는 O(n))해시테이블의 상수시간이 가능한 이유는 "해시함수"를 통해 바로 접근하기 때문이다ㅁ해시테이블(hashtable): 버켓배열 + 해시함수(key, address) 맵핑에 의해 구현된 사전 ADT※ key-value는 키와 값을 직접 연결하는 방식이라면, key-address는 키가 실제 데이터의 위치(주소)를 가리키는 방식 e.g. 컴파일러의 심볼 테이블, 환경변수들의 레지스트리, 소규모 DB, 브라우저 캐시 ㅇ버켓배열(bucket array) = 테이블 버켓을 슬롯(slot)이라고도 한다 ㅇ해시함수(hash fucntion): 맵핑하는 역할e.g. h(x) = x % Mh(x)는 정.. 2024. 7. 18. 이전 1 다음
