Hamplease

1. 문자열 해시 함수: unordered_map<string, int, '문자열 해시 함수'> poketmon_dogam;

• 균일한 해시 분포
• 해시 충돌을 줄여 unordered_map 성능 향상
• 충돌 적음 ->  버킷 체인 길이 줄어듦 -> 메모리 사용량 감소

문자열 해시 함수
: unordered_map의 세 번째 템플릿 인자로 사용자 정의 해시 함수를 지정할 때
보통 함수 객체(functor)를 정의하는 구조체(struct)를 사용
*** operator()를 오버로딩해서 해시 함수의 동작을 정의
따라서, 커스텀 해시 함수를 정의하면 기본 해시 함수 대신 사용 가

# DJB2
struct StringHash {
    size_t operator()(const string& s) const {
        size_t hash = 5381;
        for (char c : s)
            hash = ((hash << 5) + hash) + c;
        return hash;
    }
};

// 사용 예:
unordered_map<string, int, StringHash> my_map;
-------------------------------------------------------------------------------------------
# FNV-1a
struct FNV1a {
    size_t operator()(const std::string& s) const {
        size_t hash = 14695981039346656037ULL;
        for (char c : s) {
            hash ^= static_cast<size_t>(c);
            hash *= 1099511628211ULL;
        }
        return hash;
    }
};
// 사용 예:
unordered_map<string, int, FNV-1a> my_map;
-------------------------------------------------------------------------------------------
# Murmur2
struct MurmurHash2 {
    size_t operator()(const string& s) const {
        const unsigned int m = 0x5bd1e995;
        const int r = 24;
        unsigned int seed = 0;
        unsigned int len = s.length();
        const unsigned char* data = (const unsigned char*)s.c_str();

        unsigned int h = seed ^ len;

        while (len >= 4) {
            unsigned int k = *(unsigned int*)data;

            k *= m;
            k ^= k >> r;
            k *= m;

            h *= m;
            h ^= k;

            data += 4;
            len -= 4;
        }

        switch (len) {
        case 3:
            h ^= data[2] << 16;
        case 2:
            h ^= data[1] << 8;
        case 1:
            h ^= data[0];
            h *= m;
        };

        h ^= h >> 13;
        h *= m;
        h ^= h >> 15;

        return h;
    }
};
// 사용 예:
unordered_map<string, int, MurmurHash2> my_map;

2. unordered_map과 vector 조합:

• unordered_map은 문자열을 키로, 정수를 값으로 저장합니다. 이는 문자열 검색에 O(1) 시간 복잡도를 제공합니다.
• vector는 정수 인덱스로 문자열에 직접 접근할 수 있어, 정수 입력에 대해 O(1) 시간 복잡도로 검색할 수 있습니다.
• 이 조합은 양방향 검색을 효율적으로 수행할 수 있게 합니다.

3. 메모리 효율성:

• vector는 연속된 메모리 공간을 사용하기 때문에 캐시 효율성이 좋음
• unordered_map은 해시 테이블을 사용하여 빠른 검색을 제공하며, 커스텀 해시 함수로 메모리 사용을 최적화 가능

unordered_map template

template <class Key,    // 키 형식 : key_tyep
        class Ty,	// 매핑된 형식 : mapped_type
        class Hash = std::hash<Key>,	// 해시 함수 개체 형식 : hasher
        class Pred = std::equal_to<Key>,// 같음 비교 함수 개체 형식 : key_equal
        class Alloc = std::allocator<std::pair<const Key, Ty>>>	// 할당자 클래스 : allocator_type
class unordered_map;

처음으로 작성한 코드
Time: 23 ms (61.21%), Space: 22.9 MB (87.58%)

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> answer;

        sort(intervals.begin(), intervals.end());
        int left = intervals[0][0], right = intervals[0][1];
        answer.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            // intervals[i][0]이 right보다 크면 answer.push_back(intervals[i]) 하고, left&right 초기화
            // intervals[i][0]이 right보다 작거나 같으면 넘어가기 (아래로)
            // intervals[i][1]이 right보다 크면 right = intervals[i][1], answer 마지막 원소 right 값 갱신
            if (right < intervals[i][0]) {
                answer.push_back(intervals[i]);
                left = intervals[i][0];
                right = intervals[i][1];
            }

            right = max(right, intervals[i][1]);
            answer.back()[1] = right;
        }

        return answer;
    }
};

두 번째 코드
Time: 15 ms (96.72%), Space: 23 MB (37.6%)

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> answer;
        sort(intervals.begin(), intervals.end());
        int size = intervals.size();
        for (int i = 0; i < size; i++) {
            if (answer.empty() || answer.back()[1] < intervals[i][0]) {
                answer.push_back(intervals[i]);
            }
            else {
                answer.back()[1] = max(answer.back()[1], intervals[i][1]);
            }
        }

        return answer;
    }
};

(1) Time: 15 ms (96.72%), Space: 23 MB (37.6%)

int size = intervals.size();
for (int i = 0; i < size; i++) { }

(2) Time: 30 ms (19.53%), Space: 23 MB (72.73%)

for (int i = 0; i < intervals.size(); i++) { }

=> 생각보다 많이 남 ㅜㅜ