[DSA] 해싱

---

---

개요

우선, 자료 구조에 대해 간단히 알아보고 들어가보자.

자료 구조는 데이터를 효율적으로 구성하는 방식을 의미한다. 여기서 자료 구조는 인터페이스와 구현으로 나눌 수 있다.

인터페이스는 자료 구조와의 상호작용 방법을 규정하는 계약과 같다. 이는 우리가 수행할 수 있는 작업과 필요한 입력, 기대되는 출력 등을 포함한다.

예를 들어, 동적 배열을 생각해보자. 인터페이스는 추가, 삽입, 삭제, 업데이트 등의 작업을 포함한다. 이러한 작업들은 명확하게 정의되어 있으며, 사용 시 특정 규칙을 따라야 한다. 예를 들어 요소를 추가하려면, .append()나 .push() 같은 내장 메서드를 사용해 추가할 요소를 인자로 넘긴다. 일반적으로 이러한 작업은 반환 값이 없다.

구현은 자료 구조가 실제로 작동하는 코드 부분이다. 데이터 저장 방식과 작업 수행 방법의 세부 사항이 여기에 속한다. 예를 들어, 동적 배열의 구현에는 리스트에 대한 메모리 할당, 크기 관리, 삭제 작업 시 요소 재배열 등이 포함될 수 있다.

자료 구조의 구현은 복잡할 수 있으며, 복잡한 알고리즘과 데이터 조작을 포함한다. 그러나 이러한 세부 사항은 우리에게 크게 중요하지 않다 - 중요한 것은 인터페이스를 이해하고 올바르게 사용하는 방법을 아는 것이다.

앞으로 우리는 자료 구조의 구현 세부 사항을 다룰 것이다. 기본적인 이해를 하는 것은 꽤 도움이 되지만, 꼭 모든 세부 사항을 외울 필요는 없다. 여기서는 완성도를 높이기 위해 포함시킨 것이다.

더 중요한 것은 인터페이스를 이해하는 것이다. 모든 주요 프로그래밍 언어에는 주요 자료 구조의 내장 구현이 있다. 면접에서는 이러한 내장 자료 구조를 사용하는 방법을 알고 있어야 하지만, 직접 구현할 필요는 없다.

---

이 장에서는 해시 맵과 세트에 대해 이야기할 것이다. 이들은 해싱을 사용하여 구현된다.

해시 함수는 입력을 받아 프로그래머가 지정한 고정된 크기의 정수로 변환하는 함수이다. 입력은 키로 불리우며, 동일한 입력은 항상 동일한 정수로 변환된다. 영어 알파벳 문자를 포함한 문자열에 적용되는 해시 알고리즘의 예를 들면 다음과 같다:

1. 정수 total을 초기화한다.
2. 문자열의 각 문자를 검토하며, 그 문자가 알파벳에서 몇 번째에 위치하는지 파악한다. 예를 들어, a는 1번, c는 3번, z는 26번째에 해당한다.
3. 이 숫자를 문자의 위치(index + 1)와 곱하여 total에 더한다. 예를 들어, "abc"에서 b는 알파벳에서 2번째, 문자열에서도 2번째에 위치하므로 total에 2 * 2 = 4를 추가한다.
4. 모든 문자를 처리한 후, total의 최종값을 얻는다.

이 방식은 실제 해시 함수와는 다르다. 단지 문자열을 정수로 변환하는 한 방법에 불과하다. total을 프로그래머가 정한 범위 안에 맞추는 것이 중요하다. 이를 위해 4단계를 아래와 같이 수정할 수 있다:

• 모든 문자를 처리한 후, total % x를 계산한다.

여기서 %는 모듈로 연산을 의미하며, 이는 최종 변환된 값이 [0, x - 1] 범위 안에 들어갈 수 있도록 한다.

---

해시 함수의 중요성

우리는 배열이 $O(1)$의 무작위 접근이 가능하다는 사실을 알고 있다. 주어진 임의의 인덱스에 대해 배열의 값을 상수 시간 내에 접근하고 업데이트할 수 있다. 배열의 주된 제약은 그 크기가 고정되어 있고 인덱스가 정수 형태여야 한다는 것이다. 해시 함수는 어떠한 입력도 정수로 변환할 수 있으므로, 인덱스가 정수여야 한다는 제약을 효과적으로 없앨 수 있다. 해시 함수를 배열과 결합하면 해시 맵 또는 해시 테이블, 딕셔너리라고 알려진 구조가 만들어진다.

배열에서는 인덱스를 값에 매핑한다. 반면 해시 맵에서는 키를 값에 매핑하며, 키는 거의 모든 것이 될 수 있다. 해시 맵의 키에 대한 일반적인 제약은 변경 불가능해야 한다는 것이다(이는 언어에 따라 다를 수 있지만 일반적으로 좋은 지침이다). 값은 어떠한 것이든 될 수 있다.

해시 맵은 알고리즘 면접에서 매우 중요한 개념이다. 이는 강력한 기능을 제공하며, 다양한 문제에서 알고리즘의 시간 복잡도를 $O(n)$으로 줄이는 데 큰 도움이 된다. 모든 주요 프로그래밍 언어는 해시 맵을 내장하고 있다. 예를 들어, 파이썬에서는 이를 “딕셔너리”라 부르며, 선언은 dic = {}와 같이 간단하다. 이 과정에서 가장 중요한 것은 사용하는 프로그래밍 언어에서 해시 맵 인터페이스를 완전히 이해하고 숙달하는 것이다.

요약하면, 해시 맵은 순서가 없는 자료 구조로서 키와 값의 쌍을 저장한다. 해시 맵은 $O(1)$에 요소를 추가하거나 제거할 수 있으며, 키와 관련된 값을 업데이트하고 키의 존재 여부도 $O(1)$에 확인할 수 있다. 해시 맵의 키와 값에 대해서는 반복할 수 있지만, 반복이 특정한 순서를 따르지는 않는다(이는 구현 방법과 사용하는 언어에 따라 다르다).

정렬된 자료 구조는 삽입 순서를 기억하는 반면, 정렬되지 않은 자료 구조는 삽입 순서가 중요하지 않다.

---

배열과의 비교

시간 복잡도 측면에서 해시 맵은 배열을 압도한다. 해시 맵에서는 다음과 같은 연산들이 모두 $O(1)$로 수행된다:

• 요소를 추가하고 값과 연결
• 요소가 존재하는 경우 삭제
• 요소의 존재 여부를 확인

해시 맵은 배열과 동일한 유용한 속성들을 가지며, 동일한 시간 복잡도를 보인다:

• 요소의 길이/개수 찾기
• 값 업데이트
• 요소 순회

해시 맵은 사용하기에도 간편하다. 만약 키가 정수인 경우에도, 그 최대 크기를 모르면 얼마나 큰 배열이 필요한지 결정하기 어렵다. 해시 맵을 사용하면 이런 문제가 해결된다. 해시 맵에서는 키가 프로그래머가 정한 범위 내에서 적절한 크기의 새로운 정수로 변환되기 때문에, 배열의 크기에 대해 걱정할 필요가 없다.

그러나 실제 사용 시 해시 맵에는 몇 가지 단점이 있으며, 면접에서 이러한 장단점에 대해 논하는 것이 중요하다.

해시 맵의 가장 큰 단점 중 하나는 작은 입력 크기에 대해 오버헤드 때문에 느려질 수 있다는 것이다. $O(1)$ 시간 복잡도는 상수를 무시하기 때문에 때때로 현실과 다를 수 있다 - 실제로는 $O(10)$과 같은 것일 수도 있다. 모든 키는 해시 함수를 거쳐야 하며, 충돌도 발생할 수 있다.

또한 해시 테이블은 더 많은 공간을 차지할 수 있다. 동적 배열은 실제로 고정된 크기의 배열로, 용량을 초과하면 자체적으로 크기를 조정한다. 해시 테이블도 고정된 크기의 배열을 사용하여 구현된다. 문제는 해시 테이블의 크기 조정이 더 비싸다는 것이다. 모든 기존 키를 다시 해싱해야 하며, 해시 테이블은 저장된 요소의 수에 비해 훨씬 큰 배열을 사용할 수도 있다. 예를 들어, $10,000$개 아이템의 한도를 설정했지만 실제로는 $10$개만 저장한다고 가정해보자. $10,000$이 너무 크다고 주장할 수도 있겠지만, 다음 테스트 케이스에서 $100,000$개 요소를 저장해야 한다면 어떨까? 요점은 필요한 요소의 수를 모를 때, 배열이 크기 조정과 공간 낭비에 있어 더 유연하다는 것이다.

참고로, 시간 복잡도를 나타낼 때는 해당 함수에서 정의된 변수들만 고려한다. 예를 들어, 해시 맵 연산의 시간 복잡도가 $O(1)$이라고 할 때, 우리가 주로 고려하는 것은 해시 맵의 크기인 $n$이다. 하지만 이러한 표현은 오해의 소지가 있을 수 있다. 예를 들어, 문자열을 해시 맵에 넣는 데에는 $O(m)$ 시간이 걸릴 수 있으며, 여기서 $m$은 문자열의 길이를 나타낸다. 따라서 상수 시간 연산이라는 표현은 해시 맵의 크기에만 상대적으로 적용되는 것이다.

---

충돌

서로 다른 키들이 같은 정수로 변환되는 것을 충돌이라 한다. 충돌을 관리하지 않으면 이전 키들이 덮어쓰여져 데이터가 손실될 위험이 있다. 충돌을 처리하기 위한 여러 방법이 있으나, 여기서는 체이닝이라 불리는 일반적인 방법을 소개한다.

아직 링크드 리스트에 대해 잘 모르더라도 걱정하지 않아도 된다. 링크드 리스트는 다음 장에서 자세히 다룰 예정이다. 현재는 이를 배열과 유사한 자료 구조로 생각하면 충분하다.

체이닝을 사용하는 경우, 해시 맵의 배열 내에 직접 요소를 저장하는 대신 링크드 리스트를 저장한다. 이 링크드 리스트의 노드는 키와 값을 모두 보관한다. 충돌이 발생하면, 충돌한 키-값 쌍이 링크드 리스트에 연결된다. 이후 이러한 키-값 쌍에 접근하려 할 때는 해당 링크드 리스트를 키가 일치할 때까지 탐색한다.

이 부분이 혼란스러울 수 있으나, 모든 주요 프로그래밍 언어의 해시 맵 구현은 충돌을 자동으로 처리한다. 해시 맵의 내부 작동 원리를 이해하는 것은 면접에서 특정 질문을 받거나 해시 맵 사용의 장단점을 논의할 수 있으므로 중요하지만, 이러한 경우는 드물다.

충돌은 처리가 필요하고 이 과정이 시간이 소요되어 해시 맵의 전반적인 속도와 효율성을 저하시키는 문제를 일으킨다. 그렇다면 해시 맵을 어떻게 설계해야 충돌을 최소화할 수 있을까? 가장 중요한 것은 해시 테이블의 배열 크기와 모듈러스가 소수여야 한다는 것이다. 일반적으로 사용되는 중요한 규모의 소수들은 다음과 같다:

• 10,007
• 1,000,003
• 1,000,000,007

---

세트

세트는 해시 테이블과 매우 비슷한 자료 구조이다. 이 구조는 키를 정수로 변환하기 위해 해싱이라는 같은 방법을 사용한다. 세트와 해시 테이블의 주된 차이는 세트가 키를 다른 값에 매핑하지 않는다는 점이다. 요소의 존재 여부만을 확인하는 경우에 세트를 사용하는 것이 더 편리하다. 세트에서는 요소를 추가하거나 제거하고, 요소가 존재하는지 여부를 $O(1)$에 확인할 수 있다.

세트에 관해 알아두어야 할 중요한 사항은 빈도 수를 추적하지 않는다는 것이다. 만약 어떤 세트에 동일한 요소를 $100$번 추가한다면, 첫 번째 추가에서 요소가 세트에 들어가고 이후의 $99$번 추가에서는 아무런 작업도 이루어지지 않는다.

---

배열을 해시 맵의 키로 사용하는 방법

해시 맵에서 키로 사용되기 위해서는 보통 불변성이 요구된다. 하지만 배열은 내용을 변경할 수 있다. 그렇다면 요소가 정렬된 배열을 해시 맵의 키로 사용할 수 있을까?

사용하는 프로그래밍 언어에 따라 배열을 변하지 않는 고유한 키로 바꾸는 여러 방법이 있다. 예를 들어, 파이썬에서는 튜플이 변경할 수 없으므로, 배열을 튜플로 바꾸기만 하면 된다. 이를 위해 tuple(arr) 같은 명령을 사용한다.

또 다른 방법은 배열의 요소를 특정 문자로 구분하여 문자열로 만드는 것이다. 예를 들어, 정수들 사이에 쉼표를 넣어 [1, 51, 163]를 "1,51,163"과 같이 만드는 것이다. C++ 같은 언어는 자체적으로 변경 가능한 키를 지원하기도 한다.

---

인터페이스 가이드

다음은 C++과 Rust에서 사용되는 해시 맵 인터페이스에 대한 설명이다:

// 선언: C++은 다양한 구현을 지원하지만, 여기서는 std::unordered_map을 사용한다.
// 키와 값의 데이터 타입을 지정한다.
unordered_map<int, int> hashMap;

// 초기값을 포함하여 초기화하고자 한다면 다음과 같은 문법을 사용한다:
unordered_map<int, int> hashMap = {{1, 2}, {5, 3}, {7, 2}};

// 키의 존재 여부를 확인하려면 다음과 같은 문법을 사용한다:
hashMap.find(1) != hashMap.end(); // 참
hashMap.find(9) != hashMap.end(); // 거짓

// 주어진 키로 값에 접근하려면, 배열과 유사하게 대괄호를 사용한다.
hashMap[5]; // 3

// 키를 추가하거나 업데이트할 때도, 배열과 유사하게 대괄호를 사용한다.
// 키가 이미 존재한다면 해당 값이 업데이트된다.
hashMap[5] = 6;

// 키가 아직 존재하지 않는다면, 키와 값의 쌍이 삽입된다.
hashMap[9] = 15;

// 키를 삭제하려면 .erase() 메소드를 사용한다.
hashMap.erase(9);

// 해시 맵의 크기를 알아내려면
hashMap.size(); // 3

// 키와 값의 쌍을 순회하려면 다음 코드를 사용한다.
// .first는 키를, .second는 값을 반환한다.
for (auto const& pair: hashMap) {
    cout << pair.first << " " << pair.second << endl;
}

// 선언 및 초기화: Rust에서는 타입을 명시적으로 선언해야 한다.
// 여기서는 i32 타입의 키와 값을 갖는 HashMap을 생성한다.
let mut hash_map: HashMap<i32, i32> = HashMap::new();

// 초기값을 가진 HashMap을 생성하는 다른 방법:
let mut hash_map: HashMap<i32, i32> = [(1, 2), (5, 3), (7, 2)].iter().cloned().collect();

// 키의 존재 여부를 확인하려면 contains_key 메소드를 사용한다:
println!("{}", hash_map.contains_key(&1)); // true 출력
println!("{}", hash_map.contains_key(&9)); // false 출력

// 주어진 키로 값에 접근하려면, get 메소드를 사용하고 결과를 unwrap한다.
// 값이 없는 경우 대비해 unwrap_or 메소드로 기본값을 제공한다.
println!("{}", hash_map.get(&5).unwrap_or(&-1)); // 3 출력

// 키에 값을 추가하거나 업데이트하려면 insert 메소드를 사용한다.
hash_map.insert(5, 6);

// 키가 존재하지 않을 경우, 새 키-값 쌍이 삽입된다.
hash_map.insert(9, 15);

// 키를 삭제하려면 remove 메소드를 사용한다.
hash_map.remove(&9);

// 해시 맵의 크기를 알아내려면 len 메소드를 사용한다.
println!("{}", hash_map.len()); // 3 출력

// 키와 값의 쌍을 순회하며 출력하려면 for 루프를 사용한다.
for (key, value) in &hash_map {
    println!("{} {}", key, value);
}

---

출처: Leetcode