C++의 해시 테이블 및 해시 테이블

C++의 해시 테이블과 해시 테이블

해시 테이블과 해시 테이블은 컴퓨터 과학에서 매우 일반적인 데이터 구조입니다. 왜? 해시 테이블과 해시 테이블은 일정한 시간 내에 특정 요소를 빠르게 찾을 수 있기 때문입니다. 많은 애플리케이션에서 이러한 성능 차이는 중요합니다.

그럼 해시 테이블과 해시 테이블의 차이점은 무엇인가요? C++에서는 둘 사이의 차이가 매우 미묘하여 일반적으로 동일한 개념으로 간주할 수 있습니다. 이번 글에서는 해시 테이블과 해시 테이블에 대해 자세히 소개하겠습니다.

해시 테이블

해시 테이블은 해시 함수를 기반으로 한 데이터 구조입니다. 이는 상수 삽입 및 검색 작업을 지원합니다. 해시 테이블의 데이터 요소는 해시 함수의 결과에 따라 구성됩니다. 서로 다른 키의 경우 해시 함수에서 반환된 결과는 고유합니다. 즉, 각 키 값은 해시 값에 해당합니다.

C++에서 해시 테이블을 사용하려면 표준 라이브러리의 unordered_map 클래스를 사용하세요. 헤더 파일 을 포함시킨 후, unordered_map 객체를 정의하고 그 멤버 함수를 사용하여 이에 대해 작업할 수 있습니다. 예:

#include <unordered_map>
#include <string>
#include <iostream>

int main()
{
    std::unordered_map<std::string, int> grades;

    // 添加键值对
    grades["John"] = 90;
    grades["Sara"] = 85;
    grades["Bob"] = 95;

    // 查找键对应的值
    std::cout << "John's grade is " << grades["John"] << std::endl;

    return 0;
}

위의 예에서는 unordered_map 객체 등급을 사용하여 학생 성적 쿼리 기능을 구현했습니다. grades["John"]를 통해 John의 성적을 쉽게 알 수 있으며, 출력 결과는 90이다.

해시 테이블

해시 테이블은 해시 함수를 기반으로 키를 위치에 매핑하는 데이터 구조입니다. 삽입, 검색 등의 작업을 일정한 시간 내에 수행할 수 있습니다. 해시 테이블과 해시 테이블의 핵심 아이디어는 동일하며 유일한 차이점은 해시 테이블도 충돌을 처리해야 한다는 것입니다.

소위 충돌이란 두 개의 서로 다른 키 값이 해시 함수에 의해 동일한 위치로 해시되는 것을 의미합니다. 이때 오픈 해싱이나 링크드 리스트 해싱 등 해시 함수 충돌 해결 방법을 사용해야 합니다. 오픈 해싱에서 오픈 주소 방법은 다른 슬롯을 사용하는 것입니다. 이를 오픈 슬롯이라고 합니다. 키의 해시 값을 계산하여 해시 테이블의 다른 슬롯에 키를 삽입합니다. 슬롯이 이미 점유되어 있으면 다른 슬롯을 시도합니다. 슬롯. 연결된 목록 해싱에서는 연결된 목록이 해시 테이블의 슬롯에 구현됩니다.

C++에서 해시 테이블을 사용하려면 표준 라이브러리의 unordered_map 또는 unordered_set 클래스를 사용해야 합니다. 이 두 클래스를 사용할 때 해시 함수도 제공해야 합니다. 기본값은 해시 가능한 유형 변수를 고유한 정수 값에 매핑할 수 있는 std::hash 클래스 템플릿입니다. 예:

#include <unordered_set>
#include <string>
#include <iostream>

struct Person
{
    std::string name;
    int age;
};

bool operator==(const Person& lhs, const Person& rhs)
{
    return lhs.name == rhs.name && lhs.age == rhs.age;
}

// 哈希函数
struct PersonHash
{
    std::size_t operator()(const Person& p) const
    {
        std::size_t h1 = std::hash<std::string>()(p.name);
        std::size_t h2 = std::hash<int>()(p.age);
        return h1 ^ (h2 << 1);
    }
};

int main()
{
    std::unordered_set<Person, PersonHash> people = {
        {"John", 30},
        {"Sara", 25},
        {"Bob", 45},
    };

    // 添加元素
    people.insert({"Mary", 38});

    // 查找元素
    Person p = {"John", 30};
    if (people.find(p) != people.end()) {
        std::cout << p.name << " is found" << std::endl;
    }

    return 0;
}

위의 예에서는 unordered_set 개체를 사용하여 사람들의 정보 그룹을 유지합니다. 여기서 Person은 이름과 나이라는 두 필드를 포함하는 구조 유형입니다. 우리는 또한 사용자 정의 해시 함수인 PersonHash를 제공한다는 점에 유의해야 합니다. Person 유형은 해시 가능한 유형이 아니기 때문에 이에 대한 해시 함수를 제공해야 합니다.

요약

해시 테이블과 해시 테이블은 C++의 매우 실용적인 데이터 구조로, 실제 개발에서는 키워드 세트와 인덱스를 유지하는 데 자주 사용됩니다. 이를 사용할 때 해시 함수 선택과 충돌 처리 방법에 주의해야 합니다.

위 내용은 C++의 해시 테이블 및 해시 테이블의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!