C++ Academy · 강의

성능 고려 사항

버킷과 부하율 알아보기

성능 고려 사항은(는) CoddyKit의 무료 C++ Academy 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C++ Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C++ Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

hash 테이블이 데이터를 저장하는 방식

정렬되지 않은 컨테이너는 bucket 배열을 보유합니다. 키의 hash가 bucket을 선택하고, 하나의 bucket에 여러 키가 들어가면 선형으로 검색하는 연결 구조가 만들어집니다.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 1}, {2, 2}, {3, 3}};
    std::cout << "bucket count: " << m.bucket_count() << '\n';
    return 0;
}

어떤 bucket일까요

bucket(key)는 현재 키가 매핑되는 bucket 인덱스를 알려 줍니다.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{10, 1}, {20, 2}, {30, 3}};
    std::cout << "key 20 in bucket " << m.bucket(20) << '\n';
    return 0;
}

로드 팩터

로드 팩터는 size / bucket_count입니다. 로드가 높을수록 연결 구조가 길어져 조회가 느려집니다.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 1}, {2, 2}};
    std::cout << "load factor: " << m.load_factor() << '\n';
    return 0;
}

최대 로드 팩터

max_load_factor()는 임계값입니다. 로드 팩터가 이 값을 초과하면 테이블이 더 많은 bucket으로 rehash됩니다.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    std::cout << "default max load: " << m.max_load_factor() << '\n';
    return 0;
}

rehash 수행하기

rehash는 더 많은 bucket으로 테이블을 다시 구성하는 작업이며 비용이 큽니다. 로드 팩터가 초과되면 자동으로 발생합니다.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    std::size_t before = m.bucket_count();
    for (int i = 0; i < 100; ++i) m[i] = i;
    std::cout << before << " -> " << m.bucket_count() << " buckets\n";
    return 0;
}

rehash를 피하기 위한 reserve

크기를 미리 알고 있다면 reserve(n)을 호출해 bucket을 사전 할당하고 반복적인 rehash를 피하세요.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.reserve(1000);
    std::cout << "buckets reserved: " << (m.bucket_count() >= 1000 ? "yes" : "no") << '\n';
    return 0;
}

rehash 직접 사용하기

rehash(n)은 bucket 개수를 최소한 n으로 설정합니다. 요소 개수에는 reserve를 사용하고 bucket 개수에는 rehash를 사용하세요.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.rehash(64);
    std::cout << "buckets >= 64: " << (m.bucket_count() >= 64 ? "yes" : "no") << '\n';
    return 0;
}

bucket 크기 확인하기

bucket_size(i)는 i번 bucket을 공유하는 요소의 개수를 보여 주며, 충돌을 진단할 때 유용합니다.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    for (int i = 0; i < 10; ++i) m[i] = i;
    std::cout << "bucket 0 holds " << m.bucket_size(0) << " elements\n";
    return 0;
}

최악의 경우 O(n)

충돌이 많이 발생하는 나쁜 hash를 사용하면 모든 키가 하나의 bucket에 연결되어 연산이 선형 시간으로 저하됩니다. 좋은 hash는 성능을 O(1)로 유지합니다.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    for (int i = 0; i < 5; ++i) m[i] = i * i;
    std::cout << "avg lookups stay fast with good hashing\n";
    std::cout << "load: " << m.load_factor() << '\n';
    return 0;
}

최대 로드 팩터 낮추기

더 낮은 max_load_factor를 설정하면 메모리를 속도와 맞바꿉니다. 충돌은 줄어들지만 bucket은 더 많아집니다.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.max_load_factor(0.5f);
    std::cout << "new max load: " << m.max_load_factor() << '\n';
    return 0;
}

반복자 무효화

rehash는 반복자를 무효화하지만 요소에 대한 참조와 포인터는 유효하게 유지합니다. 이에 맞게 반복문을 설계하세요.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 100}};
    int& ref = m[1];
    m.reserve(500);
    std::cout << "reference still valid: " << ref << '\n';
    return 0;
}

빠른 확인

해시 테이블 성능에 대한 이해도를 확인해 보십시오.

복습

해시 테이블의 내부 동작을 배웠습니다.

키는 버킷에 매핑되고, 충돌이 발생하면 체인이 형성됩니다
부하율 = 크기 / 버킷 수이며, 이 값이 max_load_factor를 초과하면 재해시가 실행됩니다
재해시를 피하려면 reserve를 사용하십시오. 재해시는 반복자를 무효화하지만 참조는 무효화하지 않습니다

다음 과정에서는 fstream으로 파일을 읽고 쓰는 방법을 배웁니다.

자주 묻는 질문

“성능 고려 사항” 강의는 무료인가요?

네 — “성능 고려 사항” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C++ Academy 강의 전체를 잠금 해제할 수 있습니다. C++ Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

“성능 고려 사항”에서 뭘 배우나요?

버킷과 부하율 알아보기 브라우저에서 직접 실행하는 실습 코드로 C++ Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

C++ Academy을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 C++ Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.

“성능 고려 사항” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 C++ Academy 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 C++ Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

← C++ Academy(으)로 돌아가기