반응형 [PCCP] 자료구조 - 해시 1. 이론- 해시(hash): 해시함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조- 해시 특징: 단방향 동작(키를 통한 값 탐색만 가능). 키가 값의 인덱스이므로 값을 찾기 위한 탐색과정이 없음. 값을 인덱스로 사용하려면 변환 과정이 필요- 해시테이블: 키와 값이 저장되어 있는 공간- 버킷: 해시테이블의 각 데이터- 해시 ADT: (시간복잡도)- 임의 접근(탐색): O(1)- 삽입:- 삭제: (선택시 고려할 점)- 단방향 검색이지만 빠른 검색이 필요한 경우 (해시함수 구현시 고려사항)- 해시함수 변환값은 해시테이블의 크기보다 작아야함- 변환값의 충돌이 최대한 적어야함+) 충돌: 서로 다른 두 키에 값을 적용시 동일한 결과를 의미 (주요 해시함수)- 나.. 2024. 12. 14. 이전 1 다음 반응형
