[코딩 테스트 합격자 되기 C++ 스터디] STEP 3. 해시

인프런 강의 링크: https://inf.run/DuvN7

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런

3주 차

스터디 일자: (2024. 07. 21(일) ~ 2024. 07. 27(토))

 

시작에 앞서

알고리즘에서도 자주 등장하고, 정보 보안 파트에서도 자주 볼 수 있는 해시에 대해 학습하고자 한다

보통 자바의 HashMap, HashSet을 많이 사용했었다

C++에서는 어떻게 해시를 사용하는지 학습하고, 알고리즘에 적용하는 것이 목표이다

---

1. 해시 개념

해시는 데이터를 고유한 값(해시 코드 또는 해시 값)으로 매핑하는 과정이다

매핑에는 해시 함수 알고리즘을 사용해 변환 값을 인덱스처럼 사용한다

key 값을 통해 빠른 데이터 탐색이 가능하다

 

인덱스는 고정 길이의 해시 코드 형태를 가지며, 이 해시 코드를 통해 O(1) 시간 복잡도로 데이터를 탐색할 수 있어 배열보다 빠른 탐색이 가능하다

 

데이터는 해시 테이블에 담기며, row 하나를 버킷이라고 부른다

해시 테이블 크기가 N이라면 0 ~ N-1개의 데이터를 저장할 수 있다

 

해시값이 중복되는 경우가 생길 수 있는데, 이를 해시 충돌이라 부른다

---

2. 해시 함수

2-1. 나눗셈 법

$h(x) = x\ mod\ k$ 로 나타낼 수 있으며 x는 key, k는 소수인 수다

해시 테이블 크기는 곧 k가 된다(x%k의 값은 0 ~ k-1)

 

그럼 왜 k 값을 소수로 사용할까?

 

크게 3가지 이유가 있다

1. 균등한 해시 분포

k가 소수일 경우 해시 값은 0부터 k-1까지 균등하게 분포될 확률이 높아진다

 

해시 값이 소수가 아닌 경우를 보자

x = {1, 2, 3, ..., 14}

k = 6

x mod k = {1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2}

해시 값은 {0, 1, 2, 3, 4, 5}를 가진다

 

소수인 경우도 살펴보자

x = {1, 2, 3, ..., 14}

k = 7

x mod k = {1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0}

해시 값은 {0, 1, 2, 3, 4, 5, 6}을 가진다

 

데이터 값의 패턴이 1씩 증가하기 때문에 둘 다 분포가 고르다고 생각된다

 

그렇다면 데이터 값에 특수한 패턴이 있는 경우에는 어떨까

단적인 예로 짝수와 홀수 패턴을 살펴보자

(어떠한 수의 배수 패턴은 생략하도록 한다. 배수 패턴은 3번에서도 나오겠지만, 소수이든 소수가 아니든 데이터가 고르게 분포되지 못한다)

 

- 데이터 값이 짝수 패턴인 경우

x = {2, 4, 6, 8, 10, 12, ...}

k = 6

x mod k = {2, 4, 0, 2, 4, 0, ...}

k가 소수가 아니라면 해시 값은 {0, 2, 4}로 특정 값에 몰린다

 

x = {2, 4, 6, 8, 10, 12, ...}

k = 7

x mod k = {2, 4, 6, 1, 3, 5, ...}

k가 소수라면 {1, 2, 3, 4, 5, 6}으로 고른 분포를 보인다

 

데이터 값이 짝수라 이렇게 나온다고 생각할 수 있으니 홀수인 예시도 보자

 

- 데이터 값이 홀수 패턴인 경우

x = {1, 3, 5, 7, 9, 11, 13, ...}

k = 6

x mod k = {1, 3, 5, 1, 3, 5, 1, ...}

k가 소수가 아니라면 데이터 값이 {1, 3, 5}의 반복 패턴을 보인다

 

x = {1, 3, 5, 7, 9, 11, 13, ...}

k = 7

x mod k = {1, 3, 5, 0, 2, 4, 6, ...}

k가 소수라면 데이터 값은 {0, 1, 2, 3, 4, 5, 6}으로 고른 분포를 보인다

 

k가 홀수면서 소수가 아닌 경우 하나만 더 살펴보도록 하자

x = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, ...}

k = 9

x mod k = {1, 3, 5, 7, 0, 2, 4, 6, 8, 1, ...}

나름 고른 분포를 보인다

 

하지만 9에게는 3이라는 약수가 존재한다

데이터 패턴이 홀수가 아닌 3과 관련된 패턴이라면?

일반 홀수도 결국 데이터의 불균형이 일어나게 된다

 

따라서 우리는 홀수 중 소수를 선택하여 특정 패턴이 미치는 영향을 최소화하기 위해 소수 k를 해시 테이블 크기로 설정하는 것이다

 

자기 자신의 배수 패턴을 가지는 경우는 나눗셈 법에서 나타나는 공통적인 문제이므로 다른 영향을 최소화 한 소수가 테이블 크기로 적절하다고 생각하자

 

2. 공통 패턴에 대한 충돌 방지

k가 소수가 아니라면, 데이터 값에 특정한 패턴이 존재할 경우 충돌 발생 가능성이 더 높아진다

데이터 값이 모두 짝수이고, k도 짝수인 경우 k는 항상 짝수만 나오게 된다

 

따라서 특정 값에 몰리는 현상을 방지할 수 있다

 

위에서 살펴본 예시와 같다

 

3. 최대 공약수(GCD) 문제 

k가 소수가 아니고, 데이터 값들이 k의 약수같은 특정한 공통 패턴을 가진다면, 해시 충돌이 자주 발생할 수 있다

데이터 값들이 모두 4의 배수이고 k = 8이라면?

 

x = {4, 8, 12, 16...}

k = 8인 경우를 생각해 보자

해시 값은 다음과 같다

 

x mod k = {4, 0, 4, 0...}

 

x mod k의 값은 0, 4만 나오기 때문에 불균형하게 분포된다

 

나눗셈법에서는 테이블 크기가 커질 경우 더 큰 소수를 필요로 하는데, 이 소수를 찾는 일이 쉽지가 않다

---

2-2. 곱셈법

곱셈법은 나눗셈법에서 소수 찾기가 어려워 찾아낸 방법이다

소수가 아닌 황금비를 곱하는 방식으로 해시 값을 도출한다

 

식은 다음과 같다

$$h(x) = \left\lfloor m \cdot \left( x \cdot A \mod 1 \right) \right\rfloor$$

 

상수 A는 0과 1 사이의 숫자로 이루어지며, 황금비(ϕ)의 상보수(ϕ-1)를 주로 사용한다

$$\Phi = \frac{1 + \sqrt{5}}{2} ≈ 1.6180339887$$

$$1 - \Phi = 1 - \frac{1 + \sqrt{5}}{2} = \frac{1 - \sqrt{5}}{2}$$

$$A ≈ 0.6180339887$$ 로 나타낼 수 있다

 

x는 데이터 값이고, m은 테이블 크기를 의미한다

바깥에 기호는 소수점 아래를 버리는 내림 연산이다

---

2-3. 문자열 해싱

문자열 해싱 방식은 문자열의 아스키 코드 값을 활용해 해싱한다

방식도 여러가지가 있는 듯 하다

폴링 해시, DJB2 해시, FNV 해시 등... 깊게 파기에는 조금 어려운 영역인 듯하다

 

간단히 설명하자면

 

폴링 해시는 각 문자를 다항식으로 처리해 해시 값을 계산한다

$$h(s) = \left( \sum_{i=0}^{n-1} s[i] \cdot p^i \right) \mod m$$

 

DJB2 해시는 문자열 각 문자에 대해 해시 값을 받는데, 상수 33을 곱하고 XOR 연산을 진행한다

$$h(s) = ((h \cdot 33) \oplus \text{ord}(s[i])) \mod m$$

 

FNV 해시도 문자열의 각 문자에 대해 해시 값을 업데이트하며 FNV prime 상수를 사용한다

$$h(s) = (h \cdot \text{FNV\_prime}) \oplus \text{ord}(s[i])$$

 

그냥 이런 방법을 쓰는구나 정도만 이해하고 넘어가자

 

참고로 자바 객체의 해시 코드는

public int hashCode() {
    int hash = 0;
    for (int i = 0; i < value.length; i++) {
        hash = 31 * hash + value[i];
    }
    return hash;
}

 

이렇게 계산 된다

 

참고로 자주 등장하는 31이란 숫자는 메르센 소수이다

 

java의 HashMap은 메모리 주소를 기반으로 작동한다

각 객체는 Object.hashCode()로 고유 해시 값을 가지고 있으며, 이를 HashMap이 버킷 인덱스 계산에 사용한다

 

아래 hash 코드는 HashMap이 객체 해시 값을 변형해 충돌을 줄이는 방법이다

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

 

---

3. 충돌 처리

위에 살펴보았듯 소수를 테이블 크기로 설정하는 것이 데이터 불균형을 최소화하는 방법이다

하지만 소수 또한 충돌을 완전히 없앨 수 없다

동일한 해시 값이 나와 데이터 저장에 문제가 일어난다

이것이 해시 충돌이라 이야기 했었다

 

그렇다면 어떻게 이 충돌을 해결할 수 있을까?

해시 충돌의 처리 방법은 크게 두 가지가 있다

3-1. Chaining(체이닝)

충돌이 일어나는 경우 값을 LinkedList로 연결해 같은 주소에 연쇄적으로 삽입한다

따라서 충돌이 많은 경우 O(N)의 시간이 소요될 수 있다(탐색에 소요)

하지만 해시 충돌 자체가 드문 일이라 저렇게 시간이 걸일 일은 없다고 본다

 

체이닝 방식은 추가적인 메모리도 필요하다

 

Red-Black Tree(O(logN))를 사용하거나, 해시 테이블 크기를 동적으로 조절하는 등의 방법으로 문제점을 개선할 수 있다

---

3-2. Open Addressing(개방 주소법, 오픈 어드레싱)

해시 테이블에 버킷이 빈 상태에만 입력을 한다

따라서 충돌이 발생하면 다른 버킷을 찾아 데이터를 삽입한다

기법으로 선형 탐사(Linear Probing), 제곱 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있다

 

체이닝 방식에 비해 메모리 효율을 노릴 수 있다

1. 선형 탐사

$$h(k, i) = (h(k) + i) \mod m$$

k는 키 값, i는 이동할 버킷 수, m은 버킷 사이즈를 나타낸다

 

현재 위치 + 1씩 진행하며 빈 버킷을 찾는다

구현도 간단하고 이해도 쉽지만, 데이터가 한 곳에 몰리는 클러스터링 현상이 일어날 수 있다

 

2. 제곱 탐사

일정 제곱 함수에 따라 빈 자리를 찾는다

$$h(k, i) = (h(k) + i ^ 2) \mod m$$

 

클러스터링 문제를 해결할 수 있고, 선형 탐사보다 효과적이지만

구현이 선형 탐사보다 복잡하고 버킷을 찾지 못할 가능성이 여전히 존재한다

 

3. 이중 해싱

해시 충돌이 발생하면 두 번째 해시 함수를 사용해 새로운 위치를 계산한다

$$h(k, i) = (h_{1}(k) + i * h_{2}(k)) \mod m$$

 

클러스터링 문제를 해결할 수 있지만 구현이 가장 복잡하다

 

---

Java에서는 체이닝 방식을 사용해 충돌을 처리한다

연결 리스트를 사용하다가 일정 값이 넘으면 Red-Black Tree로 변환해 성능 개선을 진행한다

 

C++에서도 체이닝 방식을 사용하는데, LinkedList를 사용한다

 

두 언어 공통적으로 해시 테이블 크기가 변하면 리해싱을 통해 처리한다

---

4. 실제 예시

해시를 사용하는 경우는 언제일까

해시를 사용한다는 것은 코테에서 Map을 사용하는 것과 유사하다(Set도 해시를 사용하긴 한다)

 

C++의 map은 이진 탐색트리를 활용한다

C++의 해시 사용은 unordered_map임을 꼭 기억하자!

 

따라서 고유한 key값을 바탕으로 value를 추출해야 할 때 해시를 고려해봐야 한다

이 때 index와 달리 빠른 탐색, 접근이 필요한 경우여야 한다

key는 반드시 고유해야 한다

 

DB의 기본키와 데이터랑 좀 비슷하다랄까..?

---

5. 문제 풀이

이번 문제는 Java로 진행했다

C++은 추후에 또 연습해서 수정하도록 하겠다

5-1. 오픈채팅방

링크

프로그래머스

 

import java.util.*;

class Solution {
    public String[] solution(String[] record) {
        
        Map<String, String> map = new HashMap<>();
        List<String> list = new ArrayList<>();
        
        for(String s : record) {
            String[] token = s.split(" ");
            String key = token[0];
            String uid = token[1];
            String nickname = "";
            if(!key.equals("Leave")) nickname = token[2];
            
            if(key.equals("Enter")) {
                map.put(uid, nickname);
                list.add(uid+",님이 들어왔습니다.");
            } else if(key.equals("Leave")) {
                list.add(uid+",님이 나갔습니다.");
            } else {
                map.put(uid, nickname);
            }
        }
        String[] answer = new String[list.size()];
        int idx = 0;
        for(String s : list) {
            String[] token = s.split(",");
            String uid = token[0];
            String nickname = map.get(uid);
            
            answer[idx++] = nickname+token[1];   
        }
        
        
        return answer;
    }
}

 

---

5-2. 메뉴 리뉴얼

링크

프로그래머스

import java.util.*;

class Solution {
    
    static Map<String, Integer>[] map = new HashMap[21];
    static boolean[] visited;
    static int[] max = new int[21];
    
    public List<String> solution(String[] orders, int[] course) {
        List<String> answer = new ArrayList<>();
        for(int i = 0; i < 21; i++) {
            map[i] = new HashMap<>();
        }
        
        for(String s : orders) {
            char[] c = s.toCharArray();
            Arrays.sort(c);
            for(int i : course) {
                if(c.length < i) continue;
                visited = new boolean[s.length()];
                dfs(c, "", 0, i, 0); // 전체 주문, 현재 선택된 주문, 현재 depth, 전체 depth, 방문 배열
            }
        }
        
        for(int i : course) {
            if(max[i] < 2) continue;
            for(String s : map[i].keySet()) {
                if(map[i].get(s) == max[i]) {
                    answer.add(s);
                }
            }
        }
        
        Collections.sort(answer);
        
        // System.out.println(Arrays.toString(map));
        return answer;
    }
    
    static void dfs(char[] total, String select, int now, int depth, int idx) {
        if(now == depth) {  
            map[depth].put(select, map[depth].getOrDefault(select, 0) + 1);
            max[depth] = Math.max(max[depth], map[depth].getOrDefault(select, 0));
            return;
        }

        for(int i = idx; i < total.length; i++) {
            if(visited[i]) continue;
            visited[i] = true;
            dfs(total, select + total[i], now + 1, depth, i);
            visited[i] = false;
        }
        
    }
}

 

---

마무리

Hash에 대해서 학습했고, HashMap을 통한 문제 해결을 진행해보았다

어떤 상황에서 Hash를 사용해야 하는지 판단하고 문제를 해결하는 연습을 해야겠다

Hash는 보통 하나의 알고리즘 문제로 나오는 경우보다는 다른 문제를 풀 때 같이 활용하는 유형이 많은 것 같다

 

C++에서는 unordered_map을 주로 쓰고, 정렬된 map은 이진 탐색 트리인 것도 알게 되었다