또 다른 자료 구조인 집합을 파헤쳐 보자. 집합은 중복 값을 허용하지 않는 자료 구조다.

실제로 집합의 종류는 꽤 다양하지만 여기서는 배열 기반 집합을 다룬다. 배열 기반 집합은 값들의 단순 리스트로 배열과 거의 비슷하다. 배열 기반 집합과 일반적인 배열 간 유일한 차이점은 집합은 중복 값의 삽입을 절대 허용하지 않는다는 점이다.

예를 들어 ["a", "b", "c"]라는 집합에 또 다른 "b"를 추가하려고 하면 컴퓨터는 "b"가 이미 집합에 있으므로 삽입을 허용하지 않는다.

즉, 집합은 중복 데이터가 없어야 할 때 유용하다.

예를 들어 온라인 전화번호부를 만든다면 같은 전화번호가 두 번 나와서는 안 된다. 실은 나 역시 현재 지역 전화번호부에서 같은 문제를 겪고 있다. 우리 집 전화번호가 내 이름뿐만 아니라 Zirkind라는 어떤 가족의 전화번호로 잘못 등록돼 있다(거짓말이 아니다). Zirkind를 찾는 사람들한테서 오는 전화와 음성 메일이 솔직히 꽤 성가시다. 동시에 Zirkind 역시 왜 자신에게 아무 전화가 오지 않는지 궁금해하고 있으리라. Zirkind에게 전화해서 번호가 잘못됐다고 알려주면 내 아내가 전화를 받는다. 내 진짜 번호로 걸었기 때문이다(사실 이건 농담 삼아 한 거짓말이다). 전화번호부를 만든 프로그램이 집합만 이용했다면….

어쨌든 배열 기반 집합은 중복 금지라는 제약이 하나 더 추가된 배열이다. 중복을 허용하지 않는 기능이 유용하기는 하나 이 간단한 제약으로 인해 네 주요 연산 중 하나에서 집합의 효율성이 크게 달라진다.