반응형 [PCCP] 자료구조 - 해시 1. 이론- 해시(hash): 해시함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조- 해시 특징: 단방향 동작(키를 통한 값 탐색만 가능). 키가 값의 인덱스이므로 값을 찾기 위한 탐색과정이 없음. 값을 인덱스로 사용하려면 변환 과정이 필요- 해시테이블: 키와 값이 저장되어 있는 공간- 버킷: 해시테이블의 각 데이터- 해시 ADT: (시간복잡도)- 임의 접근(탐색): O(1)- 삽입:- 삭제: (선택시 고려할 점)- 단방향 검색이지만 빠른 검색이 필요한 경우 (해시함수 구현시 고려사항)- 해시함수 변환값은 해시테이블의 크기보다 작아야함- 변환값의 충돌이 최대한 적어야함+) 충돌: 서로 다른 두 키에 값을 적용시 동일한 결과를 의미 (주요 해시함수)- 나.. 2024. 12. 14. [코딩테스트] 해시 해시 unordered_map 다루기#include int main(int argc, char** argv) { /* 생성 및 초기화 */ unordered_map dict1 = {{"key1": val1}, {"key2": val2}, {"key3": val3}}; /* 삽입 */ dict1["key"] = val; dict1.insert({"key": val}); dict1.insert(make_pair("key", val)); /* 삭제 */ dict1.erase("key"); /* 탐색 */ dict1.find("key"); /* 조회 */ for (auto it = dict1.begin(); it != dict.. 2024. 7. 9. 이전 1 다음 반응형
