map(맵)

MoOrY·2023년 4월 10일

자료구조

목록 보기

3/3

map 맵

key와 value로 쌍으로 구성되어 있는 자료구조.
key와 value를 짝짓는 것을 매핑이라고 한다.
key는 맵 자료구조에서 대응하는 값을 찾기 위한 용도로, 중복을 허용하지 않는다.
순서보단 정의된 이름key와 상응하는 데이터를 묶기 위한 자료구조로써 효과적이다.

HashMap

출처
https://mangkyu.tistory.com/102
https://www.youtube.com/watch?v=HraOg7W3VAM

Key와 Value로 데이터를 저장하는 자료구조 중 하나로
O(1)이라는 빠른 시간에 데이터를 검색하고, 추가할 수 있는 자료구조이다.

해시테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열을 사용하여 데이터를 저장하기 때문이다.
주어진 Key값을 해시 함수가 index로 변환하고, 그 index에 해당하는 배열 값을 가져오게 된다.

key값을 해시 함수에 나오면 고정된 크기의 int index가 나오게 된다.
이 index를 현재 해시의 공간 갯수인 capacity로 %연산을 해서 나온 index에 저장한다.
다른 key값일때도, 최종 index결과가 같을 때가 있는데, 이때문에 해시의 데이터 저장 배열에는 key와 value 모두 저장해서, input으로 넣은 key와, 검색결과의 key가 같은지 확인하고, 만약 그렇다면 그 값을 리턴한다.

key와 Value의 쌍으로만 구성이 될뿐, 자료구조 안에 묶인 쌍들에 대한 순서는 보장할 수 없다.
즉 사용자는 키와 값이 구성되는 위치를 결정하거나 할 수 없다
Key 또는 Value값으로써 null을 허용한다.

해시 충돌

서로 다른 Key값을 넣었음에도 같은 index으로 변환되어 충돌이 일어나는 현상

해시 충돌로는 다음 두 경우가 있다.
1. key는 다른데 해시 함수를 거쳐 나온 index가 같은 경우,
2. key와 hash 모두 다른데, hash % capacity 결과가 같을 때

이를 해결하는 방법으로는 분리 연결법과 개방 주소법 크게 두 가지가 있다.

분리 연결법 Separate Chaining

추가 메모리를 사용하여 다음 데이터의 주소를 저장한다.
그림과 같이 동일한 index로 접근한다면, 데이터들을 연결하여 관리해주고 있다.

이 Chaining방식은 해시 테이블의 확장이 필요없고, 간단히 구현이 가능하며 손쉽게 삭제가 가능하다
하지만 데이터의 수가 많아지면 동일한 index에 chaining되는 데이터가 많아지며
그에 따라 캐시의 효율성이 감소한다는 단점이 있다.

개량 주소법 Open Addressing

Open Addressing이란 추가적인 메모리를 사용하는 Chaining 방식과 다르게
비어있는 해시 테이블의 공간을 활용하는 방법이다.
Open Addressing을 구현하기 위한 대표적인 방법으로는 3가지 방식이 존재한다.

Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다.
예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.
Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

Open Addressing에서 데이터를 삭제하면 삭제된 공간은 Dummy Space로 활용되는데,
그렇기 때문에 Hash Table을 재정리 해주는 작업이 필요하다고 한다.

이러한 문제 때문에 해시 테이블의 시간복잡도가 항상 O(1), 즉 상수시간인것은 아니다.
충돌로 인해 최악의 경우 O(n)까지 갈 수 있으나,
전반적인 평균 시나리오 중심으로 판단한다면 O(1)의 시간복잡도를 가진다.

해시 테이블 리사이징

해시 테이블이 꽉 차서 공간을 늘려주는 작업이다.
java의 경우, 해시 테이블 총 용량의 4/3만큼 차면 capacity를 2배로 늘려준다.

이때, capacity가 8에서 16으로 늘었다고 해보자.
이 작업을 위해 각 저장공간에 key와 value뿐만 아니라, key를 해시함수에 넣어 얻은 결과인 hash도 저장하는데,
이 hash를 늘어난 capacity로 %하여 새로운 index를 얻어, 새로 할당받은 공간에 재정리하여 저장한다.

TreeMap

Key의 값을 이용해 순서대로 정렬하여 데이터를 저장하는 자료구조
Key값을 통한 탐색 뿐 아니라, Key값의 정렬을 통한 탐색 등을 하기에 용의하다.

LinkedHashMap

데이터를 입력한 순서대로 쌓아지며 데이터를 저장하는 자료구조
배열, 리스트처럼 인덱싱 접근을 하기에 용이하다.

맵과 해시맵의 차이

특정 키에 대한 값을 찾는 과정에서 Map은 red-black-tree 알고리즘을 사용하며,
해시맵은 hash table을 이용하여 키-값 관계를 유지한다.
Map은 인터페이스이고, HashMap은 그 인터페이스의 구현이다.

c++ STL에 포함된 map

map

red-black 트리로 구현된 map 컨테이너로, 이진탐색트리의 특성 상 순서를 정렬한다.
따라서 삽입&삭제가 빈번할 경우 성능이 낮아질 수 있다.
원소들의 순서가 중요한 경우 사용한다.
삽입&삭제&조회의 시간복잡도는 O(log n)

사용 예

#include <iostream>
#include <map>

int main() {
    // 1. map 선언 및 초기화
    std::map<std::string, int> my_map;

    // 2. 원소 삽입
    my_map["apple"] = 3;
    my_map["banana"] = 5;
    my_map["orange"] = 2;
    my_map.insert(std::make_pair("kiwi", 1));

    // 3. 원소 조회
    std::cout << "Number of apples: " << my_map["apple"] << std::endl;
    std::cout << "Number of oranges: " << my_map["orange"] << std::endl;

    // 4. 원소 개수 확인
    std::cout << "Size of my_map: " << my_map.size() << std::endl;

    // 5. 원소 삭제
    my_map.erase("banana");
    std::cout << "Size of my_map after erasing banana: " << my_map.size() << std::endl;

    // 6. 원소 순회
    std::cout << "Contents of my_map:" << std::endl;
    for (const auto& element : my_map) {
        std::cout << element.first << " => " << element.second << std::endl;
    }

    // 7. 원소 존재 여부 확인
    if (my_map.find("banana") == my_map.end()) {
        std::cout << "Banana not found in my_map" << std::endl;
    }

    return 0;
}

unordered_map

해쉬맵으로 구현된 map컨테이너
순서를 정렬하지 않아 map의 단점인 빈번한 삽입&삭제에도 성능이 낮아지지 않는 장점이 있다.
삽입&삭제&조회의 시간복잡도는 O(1), 하지만 최악의 경우 O(n)
원소의 순서가 중요하지 않은 경우에 사용한다.

#include <iostream>
#include <unordered_map>

int main() {
    // 1. unordered_map 선언 및 초기화
    std::unordered_map<std::string, int> my_unordered_map;

    // 2. 원소 삽입
    my_unordered_map["apple"] = 3;
    my_unordered_map["banana"] = 5;
    my_unordered_map["orange"] = 2;
    my_unordered_map.insert(std::make_pair("kiwi", 1));

    // 3. 원소 조회
    std::cout << "Number of apples: " << my_unordered_map["apple"] << std::endl;
    std::cout << "Number of oranges: " << my_unordered_map["orange"] << std::endl;

    // 4. 원소 개수 확인
    std::cout << "Size of my_unordered_map: " << my_unordered_map.size() << std::endl;

    // 5. 원소 삭제
    my_unordered_map.erase("banana");
    std::cout << "Size of my_unordered_map after erasing banana: " << my_unordered_map.size() << std::endl;

    // 6. 원소 순회
    std::cout << "Contents of my_unordered_map:" << std::endl;
    for (const auto& element : my_unordered_map) {
        std::cout << element.first << " => " << element.second << std::endl;
    }

    // 7. 원소 존재 여부 확인
    if (my_unordered_map.find("banana") == my_unordered_map.end()) {
        std::cout << "Banana not found in my_unordered_map" << std::endl;
    }

    return 0;
}

unordered_multimap

중복 키를 허용하는 unordered_map이다.
마찬가지로 해쉬맵으로 구현되었다.

#include <unordered_map> // 헤더 파일 include

int main()
{
    // unordered_multimap 생성
    std::unordered_multimap<std::string, int> my_map;

    // 삽입
    my_map.insert(std::make_pair("apple", 1));
    my_map.insert(std::make_pair("orange", 2));
    my_map.insert(std::make_pair("apple", 3));
    my_map.insert(std::make_pair("banana", 4));

    // 검색
    auto iter = my_map.find("apple"); // 첫 번째 "apple"을 찾음
    if (iter != my_map.end())
    {
        std::cout << "Key found. Value = " << iter->second << std::endl;
    }
    else
    {
        std::cout << "Key not found." << std::endl;
    }

    // 삭제
    my_map.erase("apple"); // 첫 번째 "apple"을 삭제

    return 0;
}

중복된 키가 있을 때 하나만 삭제하는법

#include <unordered_map>

int main()
{
    std::unordered_multimap<int, int> my_map = {{1, 2}, {2, 4}, {1, 5}, {3, 6}};

    int key_to_delete = 1;

	//key_to_delete에 해당하는 범위를 리턴한다.
    auto range = my_map.equal_range(key_to_delete);

    if (range.first != range.second)
    {
    	//첫번째로 발견된 값을 삭제한다.
        my_map.erase(range.first);
    }

    return 0;
}