연쇄법2 [알고리즘] ep4+) 연쇄법 구현 문제) 크기 M인 해시테이블에 여러 개의 키 값을 입력받아 저장하고, 연쇄법을 이용하여 충돌을 처리하는 해시테이블 프로그램을 작성하시오 [구현 조건]- 해시테이블은 크기가 M인 배열로 동적 할당한다.- 입력 키는 중복이 없는 자연수다.- 키 x에 대한 해시함수 h(x) = x % M 을 사용한다.- 삽입 시 충돌이 발생하는 경우, 해당 버켓 리스트의 맨 앞에 삽입한다. [입력]- 해시테이블의 크기 M을 입력받는다.- 삽입(i), 탐색(s), 삭제(d), 인쇄(p) 명령어를 순서에 상관없이 반복하여 입력받는다. i x> : 키 x를 해시테이블에 삽입s x> : 키 x가 해시테이블에 존재하는지 탐색d x> : 키 x가 해시테이블에 존재하면 삭제p : 해시테이블에 저장된 키들을 순서대로 인쇄(입출력 예시 참.. 2024. 7. 19. [알고리즘] 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 다음
