Set and Map
맵
키-값 쌍을 저장하는 자료구조입니다.
크게 트리를 이용하는 방식과 해시를 이용하는 두 가지 방식으로 나뉩니다.
어떤 구현 방식을 사용하느냐에 따라 삽입, 제거, 조회 연산에 걸리는 시간 복잡도가 다릅니다.
맵에 저장된 자료의 개수
- 트리를 이용하는 경우
의 시간 복잡도를 갖습니다. - C++의
std::map,set::set
- C++의
- 해시를 이용하는 경우 평균적으로는
, 최악의 경우 의 시간 복잡도를 갖습니다. - C++의
std::unordered_map,std::unordered_set - Python의
dictionary,set
- C++의
집합
맵에서 키-값 쌍 대신 키만 삽입하면 집합이 됩니다.
트리를 이용한 맵
이진 탐색 트리(BST, Binary Search Tree)를 이용합니다.
이진 탐색 트리는 위와 같이 왼쪽 자식으로 가면 값이 작아지고, 오른쪽 자식으로 가면 값이 커지는 구조를 갖습니다.
찾고자 하는 키를 찾기 위해서는 어떤 노드보다 키의 값이 작은지 혹은 큰지를 판단해서 아래로 계속 내려가면 됩니다.
이진 탐색 트리가 어느 한쪽만 깊지 않고 균일하게 분포되어 있다면 트리의 높이는 전체 노드 개수의 로그에 비례합니다. 따라서 아무리 많아도
만약 트리에 있는 값의 최솟값보다 더 작은 값을 삽입하기를 반복하면 맨 왼쪽에만 값이 붙으므로 트리의 높이가 균등하지 않고 일자 형태가 됩니다. 이를 방지하고 높이를 최대
해시를 이용한 맵
해시 함수란 임의 크기의 입력을 받아 고정된 크기의 출력을 내보내는 함수를 말합니다.
입력의 경우의 수 보다 출력의 경우의 수가 더 적으므로 비둘기집의 원리에 의해서 같은 출력값을 갖는 서로 다른 입력이 항상 존재합니다. 이러한 경우를 해시 충돌이라 부르고, 해시 테이블의 최악 시간 복잡도가
값을 해시 함수에 넣어서 함숫값을 얻는 것을 해싱이라고 합니다.
원리
키를 해싱하여 얻은 값을 배열의 인덱스로 사용하는 방식을 사용합니다.
따라서 해시 함수의 시간 복잡도가 곧 따라 삽입/제거/조회의 시간 복잡도가 됩니다.
예를 들어 문자열의 모든 문자를 해싱에 이용하는 경우 문자열의 길이에 비례하는 선형 시간 복잡도를 갖습니다.
해시 충돌
해시 충돌이 일어나면 이미 삽입된 해시 값이 같은 키들 중 찾고자 하는 키와 일치하는 것이 어디 있는지 완전탐색해야 하므로 시간 복잡도가
악의적인 유저가 입력으로 해시 충돌을 유도하여 공격을 시도할 수 있으므로 주의해야 합니다.
이를 방지하기 위해 해시 충돌이 일어난 부분을 트리 맵을 이용해 처리하는 방식도 있지만 메모리 오버헤드 때문에 잘 쓰이지는 않습니다.
특이하게 Java의 경우 해시 값이 같은 원소가 8개가 되면 트리 맵으로 바꾸어 처리합니다.
