컴퓨터 과학에서 연관 배열, 지도, 기호 테이블 또는 사전은 (키, 값) 쌍의 모음으로 구성된 추상 데이터 유형입니다. 컬렉션에서 가장 자주. 사전은 지도라고도 합니다.
사전 문제는 고전적인 컴퓨터 과학 문제입니다. '검색', '삭제' 및 '삽입' 작업 동안 데이터 집합을 유지 관리하는 데이터 구조를 설계하는 작업입니다. 다양한 유형의 사전 구현이 있습니다.
- 해시 테이블 구현
- 트리 기반 구현(자체 균형 및 불균형 트리)
- 목록 기반 구현
사전을 사용해야 하는 경우
사전은 만병통치약이 아니며 기회가 있을 때마다 사용해서는 안 됩니다. 많은 시나리오에서 유용하지만 사전을 사용하여 문제를 해결하기로 결정하기 전에 다음 사항을 염두에 두어야 합니다.
- 삽입은 일반적으로 느리고 읽기는 트리보다 빠릅니다.
- 예를 들어 캐시 데이터, 색인 데이터베이스, 기호 테이블 등의 빠른 조회에 사용합니다.
- 요소의 순서가 중요하지 않은 경우.
- 모든 요소 키가 고유한 경우.
구현할 방법
사전에는 일반적으로 잘 정의된 API가 있습니다. 우리는 아래에 정의된 매우 기본적인 사전 API를 구현할 것입니다 -
- get(): 입력 키가 있는 요소를 가져옵니다.
- put(): 키-값 쌍을 사전에 넣습니다.
- hasKey(): 키가 사전에 있는지 확인
- 삭제(): 사전에서 주어진 키를 제거합니다.
- 지우기(): 사전에서 모든 키-값 쌍을 제거합니다.
- 키(): 모든 키를 배열로 반환
- 값(): 모든 값을 배열로 반환