오늘 학습 키워드

• map

1. map

1.1. map

• 키-값 쌍을 저장하는 연관 컨테이너 (키 중복 안 됨)

• 내부적으로 Red-Black Tree를 사용해 키 기준으로 자동 정렬

• 기본 오름차순이며, 정렬함수를 직접 정의해주어 정렬하기도 함.
  정렬되어 있기에 삽입, 탐색, 삭제에 O(log n) 시간 복잡도를 가짐 (평균, 최악 둘 다)

• 각 트리의 노드는 아래와 같은 데이터를 가짐

  1. <키-값>
  2. 부모 포인터
  3. 왼쪽 자식 포인터
  4. 오른쪽 자식 포인터
  5. 빨강/검정 색깔

레드블랙트리

• AVL트리와 비슷한 트리. 정렬되어 있어, 중위순회하면 정렬된 순서로 순회 가능

• AVL보다 균형제약이 약한 대신 성능은 더 좋음

• AVL트리는 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1보다 크면 안 됨

• 따라서 높이 차가 1보다 커지면 바로 Rotation 발생

• 레드블랙트리는 정렬된 상태에서 조금 더 유한 규칙을 가짐

  1. 모든 노드는 빨간색 혹은 검은색이다.

  2. 루트 노드는 검은색이다.

  3. 모든 리프 노드(NIL)들은 검은색이다.
     NIL(null leaf)은 NULL대신 사용하는 노드로, 데이터 없이 트리의 끝을 나타내는 노드. 그냥 자식포인터를 NULL하면 예외처리를 해주는 번거로움 대신에, NIL 사용하면 똑같은 노드지만 데이터만 없는거라 구현 및 설계에 편리

  4. 빨간색 노드의 자식은 검은색이다. 부모-자식이 빨강이면 안 됨

  5. 모든 NIL까지의 루트로부터 존재하는 검정색 노드의 개수는 같다

     시뮬레이션

• 따라서, 트리의 회전이 AVL보다는 덜 일어나고 시간복잡도도 O(logN)이라 map, multimap, set에서 사용

• 사실 정말 세밀하게 따지면 AVL이 트리의 균형이 더 좋아 탐색은 더 빠르긴 하나, 미미하긴 하다

반복자

• Bidirectional Access Iterator로 ++, --같은 연산자는 사용가능

• 하지만 벡터의 반복자같이(Random Access Iterator) *(it + 5)이건 안 됨

• 벡터는 메모리가 연속적으로 존재하기에, 위같은 연산이 어느 위치를 가리켜야하는지가 컴파일타임에 정해짐

• 하지만, map, unordered_map, set등과 같은 자료구조들은 메모리가 힙에서 연속적으로 존재하지 않음.
  현재 노드가 다음 노드를 가리키는 포인터를 가져 다음 노드로 이동하는 방식을 취함

• 그래서 한 번만 이동하는 ++, --는 컴파일 타임에 다음 노드의 위치를 정할 수 있지만, 벡터처럼 랜덤 액세스를 하려면 노드를 따라가며 알아야하기에 컴파일타임에 알 수가 없어 사용이 불가능하다

• 다음/이전 노드로 이동하는 방법은 이미 함수로 정의되어 있기에 노드메모리가 서로 떨어져있어도 알아서 계산해줌

• 따라서 Bidirectional Access Iterator는 ++, --만 가능

• it += 3, m1[5]같은 랜덤 접근은 안 된다

• 추가로, 반복자를 사용하는 도중에 새 원소가 삽입되어도 순회에는 문제 없음.
  반복자가 가리키는 메모리의 데이터는 트리구조가 바뀌어도 변하지 않기 때문.
  트리구조가 바뀌게 되면, 해당 노드의 부모/자식포인터만 바뀌는거라 반복자 그대로 사용해도 문제 없다.

insert vs emplace

• insert(~)는 이미 완성된 객체를 넣는 것이기에 복사 및 생성으로 이루어짐

• emplace(~)는 그냥 값을 넣기때문에 복사 안 일어나고 내부에서 생성만 함
  객체 생성자의 인수들 넣으면 내부적으로 객체 생성해서 저장. 불필요한 복사/이동 제거

• 따라서 새로 객체를 생성해주어야한다면 emplace를 이미 생성했으면 insert를 사용

1.2. unordered_map

• map과 다르게 정렬 대신 해시를 사용하여 데이터를 저장

• 해시를 사용하기에 평균 시간복잡도는 O(1), 최악은 O(N)을 가짐

• 하지만 해시 특성상 평균성능이 더 좋기에 정렬이 필요하지 않다면 이거 사용

• map의 반복자와 마찬가지로 Bidirectional Access Iterator로 증감연산자만 사용 가능

해시

• C++에 미리 정의된 해시함수를 이용하여 해시값을 얻고 해시테이블의 최대 인덱스값으로 모듈로 연산을 하여 해시테이블에 저장

• 해시함수로는 비트 연산을 하거나 각 자릿수마다 특정 큰 수를 곱하며 더하는 방식을 사용하는 등 함

// 비트 연산으로 해시 구하는 방식
unsigned int bitHash(const vector<int>& a) {
    unsigned int h = 0;
    for (int x : a) {
        h ^= static_cast<unsigned int>(x);	// 1) XOR로 섞고
        h = (h << 5) | (h >> (32 - 5));		// 2) 왼쪽/오른쪽 시프트 후 OR로 더 섞기
    }
    return h;
}

// 자릿수에 큰 수 곱하고 더하는 방식
unsigned long long hashString(const string& s) {
    const unsigned long long BASE = 131;   // 보통 31, 131, 257 등 사용
    unsigned long long h = 0;
    for (char c : s) {
        h = h * BASE + static_cast<unsigned long long>(c);
    }
    return h;
}

해시 충돌

• 해시값을 구했는데 서로 다른 키지만 같은 해시 값이 나올 수도 있음. 두 가지 방식으로 해결

Separate Chaining (연쇄법)

• unordered_map이 쓰는 방식으로, 같은 해시값끼리는 연결 리스트, vector, 트리 등에 묶어서 저장

• 새 공간을 만들어 거기에 해당값을 저장하는 법

• 삭제/삽입 쉽고 구현 단순하다는 장점이 있으나, 연결리스트같은 경우 포인터 구조라 캐시에 좋지 않고, 충돌이 많으면 최악의 경우 O(N)의 시간복잡도를 가짐

Open Addressing (개방 주소법)

• 새 공간을 더 안 만들고, 테이블 안에서 빈 자리 찾아서 넣는 방식

1. Linear Probing (선형 탐사)
   충돌 나면 바로 다음칸들을 보며 빈 칸에 넣음. 간단하고 캐시 친화적이지만, 군집(클러스터링) 생기기 쉬움.

2. dratic Probing (제곱 탐사)
   충돌 i번째마다 idx + i^2 만큼 건너뜀: 1, 4, 9, 16, …
   클러스터링 덜하지만, 구현·분석이 조금 더 복잡.

3. Double Hashing (이중 해싱)
   기본 인덱스 구하는 해시함수와(h1(key)) 점프 크기 구하는 해시함수(h2(key))를 사용하여 충돌될 때마다 idx = idx + h2(key)로 점프
   클러스터링 가장 적지만, 해시를 두 번 계산해야 해서 비용이 더 크다

1.3. multimap

• map과 거의 비슷하나, 키의 중복을 허용

• 동일한 키가 또 들어오면 map은 값을 수정하였지만, multimap은 새 노드에 저장

• 서로 다른 키에 대해서는 정렬이 이루어지지만, 동일한 키에대해선 정의된 함수는 따로 없음. 정렬하고 싶으면 본인이 구현

• map의 경우 m1[key]를 이용해서 값 없으면 추가도 가능하고 있으면 참조자를 가져오지만, multimap은 키가 여러개 존재하므로 []연산자 아예 사용 불가

• 삽입하고 싶으면 insert나 emplace사용

• 값을 읽고 싶으면 equal_range사용.

std::multimap<string, string> course; // 과목 -> 학생

course.insert({"CPP", "Alice"});
course.insert({"CPP", "Bob"});
course.insert({"CPP", "Charlie"});
course.insert({"DB",  "David"});
course.insert({"DB",  "Eve"});

// 특정 과목("CPP")의 모든 학생 출력
auto range = course.equal_range("CPP");
std::cout << "CPP 수강생:\n";
for (auto it = range.first; it != range.second; ++it) {
    std::cout << "- " << it->second << '\n';
}

• equal_range의 반환값은 {lower_bound(key), upper_bound(key)}인 pair값

• 그래서 key에 해당하는 모든 iterator를 읽을 수 있다

2. Rehash

• unordered_map 사용하다가 중간에 성능이 확 떨어질 때가 있음

• 저장할 데이터가 많아져 해시 테이블 크기보다 커지면 해시 콜리젼이 발생할 수 밖에 없기도하고 해서 내부적으로 Rehash가 불러짐

• Rehash를 불러 해시 테이블 크기를 늘리고, 기존의 저장된 데이터들도 다 옮김

• 그래서 일시적으로 성능 저하가 생김

• 그래서 아예 처음부터 생성자에서 크기를 크게 할당하거나, reserve()로 미리 용량을 확보하는것이 좋음