해시 테이블을 사용하여 C++에서 문자열 검색 구현

해시 테이블은 키 값을 고정된 크기의 테이블에 매핑하여 효율적인 검색, 삽입, 삭제 작업을 가능하게 하는 매우 일반적인 데이터 구조입니다. C++에서는 STL(표준 템플릿 라이브러리)의 unordered_map을 사용하여 해시 테이블을 구현할 수 있습니다.

실제 응용 프로그램에서는 문자열에 대한 검색 작업을 수행해야 하는 경우가 많습니다. 예를 들어, 텍스트에서 특정 키워드의 발생 횟수를 찾거나 특정 문자열이 포함된 모든 줄을 찾습니다. 이러한 작업을 효율적으로 수행하기 위해 해시 테이블을 사용하여 문자열 조회를 구현할 수 있습니다.

이 글에서는 C++에서 문자열 조회를 구현하기 위해 해시 테이블을 사용하는 구체적인 방법을 소개하겠습니다. 텍스트에 문자열이 나타나는 횟수를 찾는 예를 사용하겠습니다.

먼저 문자열을 해시 테이블에 매핑하는 함수를 정의해야 합니다. 일반적인 방법은 문자열의 해시 값을 키 값으로 사용하여 서로 다른 문자열이 서로 다른 위치에 매핑되도록 하는 것입니다. 해시 함수가 좋은 성능을 가지기 위해서는 빠르게 계산되어야 하며 해시 충돌 발생을 최소화해야 합니다.

다음은 문자열의 ASCII 코드를 추가하고 나머지를 취하는 간단한 해시 함수 구현입니다.

size_t hash_func(const std::string& str) {
    size_t hash_val = 0;
    for (char c : str) {
        hash_val += static_cast<size_t>(c);
    }
    return hash_val % MAP_SIZE;
}

다음으로 텍스트의 각 단어를 해시 테이블에 삽입해야 합니다. 텍스트를 공백으로 단어로 나누고 해시 함수를 호출하여 텍스트를 해시 테이블에 삽입할 수 있습니다. 키워드는 여러 번 나타날 수 있으므로 각 키워드가 나타나는 횟수를 기록해야 합니다. unordered_map을 사용하면 삽입 중에 키 값이 이미 존재하는 경우 값이 증가합니다.

std::unordered_map<std::string, size_t> word_map;
for (std::string word : words) {
    if (word_map.find(word) == word_map.end()) {
        word_map[word] = 1;
    } else {
        ++word_map[word];
    }
}

마지막으로 해시 테이블의 문자열에 해당하는 값을 호출하여 텍스트에서 키 값이 나타나는지 확인할 수 있습니다. 횟수:

size_t count = word_map["target_string"];

전체 코드는 다음과 같습니다.

#include 
#include 
#include 
#include 

const size_t MAP_SIZE = 1024;

size_t hash_func(const std::string& str) {
    size_t hash_val = 0;
    for (char c : str) {
        hash_val += static_cast<size_t>(c);
    }
    return hash_val % MAP_SIZE;
}

int main() {
    std::vector words {"hello", "world", "hello", "c++", "hash", "world", "world"};
    std::unordered_map word_map;

    for (std::string word : words) {
        if (word_map.find(word) == word_map.end()) {
            word_map[word] = 1;
        } else {
            ++word_map[word];
        }
    }

    size_t count = word_map["world"];
    std::cout << "The word 'world' appears " << count << " times." << std::endl;

    return 0;
}

위 코드를 사용하면 해시 테이블을 사용하여 텍스트에 문자열이 나타나는 횟수를 빠르게 계산할 수 있습니다. 해시 테이블을 사용하면 검색 성능이 향상될 수 있으며 이는 대량의 데이터에 대해 더욱 분명해지며 실제 애플리케이션에서도 유연성과 확장성이 뛰어납니다.

위 내용은 해시 테이블을 사용하여 C++에서 문자열 검색 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!