집합 (추상 자료형)

컴퓨터 과학에서, 집합이란 특정한 값들을 저장하는 추상자료형이다. 이때, 값들을 순서가 존재하지 않으며 중복되지 않는다. 이는 수학에서의 유한집합의 컴퓨터 구현이다. 다른 모음(Collection) 타입에서 특정 원소를 검색하는 것이 주 업무인 반면, 집합은 대상 원소가 집합에 소속되었는지 여부를 검사한다.

정적인 집합은 생성된 이후에 변동되지 않는다. 정적인 집합은 쿼리 연산만을 허용하는데-예를 들어 주어진 값이 집합에 속하는지, 혹은 임의 순서대로 값들을 세는 경우이다. 동적인 집합은 원소들의 삽입 및 삭제가 가능하다.

추상 자료 구조는 데이터의 모음(collection) 혹은 합계(aggregate)를 뜻한다. 데이터란 참거짓(booleans), 숫자, 글자, 혹은 다른 자료구조를 지칭한다. 이 추상 자료구조는 포장(packaging)¹ 혹은 색인(indexing)²에 따라 4가지 방식으로 구분 가능하다.

1. 비포장, 비색인: 묶음(bunch)
2. 포장, 비색인: 집합(set)
3. 비포장, 색인: 문자열 (시퀀스)
4. 포장, 색인: 리스트 (배열)

1. 포장(packaging)은 오브젝트의 모음을 한개의 오브젝트로 다루기 위한 컨테이너를 제공한다. 함수호출을 생각해보자. 만약 포장이라는 개념이 없다면, 각 모음의 원소들을 별개의 인자값으로 통과시켜야 한다. 이 모음의 원소들을 집압으로 포장할 경우, 함수는 한개의 인자로 호출이 가능하다.

2. 색인(indexing)은 모든 원소들에 완벽한 순서가 존재할 때 가능하다. 순서가 없다면, 멀티셋의 원소들은 대/소 혹은 전/후 관계가 존재하지 않는다. 원소들은 절대적인 용어로만 구분 가능하다(같음/다름).