HashMap 이란, 예제문제 정복하기

이창호·2023년 2월 16일

HashMap 자료구조 제로베이스 취준생

자료구조

목록 보기

4/6

HashMap이란?

HashMap은 Key-Value 쌍으로 이루어진 자료구조이다.
Key를 통해 Value를 저장하고, Key를 통해 Value를 검색할 수 있다.
자바에서 HashMap은 매우 자주 사용되는 자료구조 중 하나이다.

HashMap의 내부 구조

HashMap은 내부적으로 해시 테이블을 사용하여 데이터를 저장한다.
Key를 해시 함수에 적용하여 해시값을 계산하고, 이 해시값을 인덱스로 사용하여 데이터를 저장한다.
해시 충돌이 발생할 경우, 연결 리스트를 사용하여 데이터를 추가적으로 저장한다.
버킷이란 해시 테이블에서 값을 저장하는 공간으로, 연결 리스트를 가리키는 포인터를 가지고 있다.

HashMap의 주요 메소드

put(key, value): Key-Value 쌍을 추가한다.
get(key): Key에 해당하는 Value를 반환한다.
remove(key): Key에 해당하는 Key-Value 쌍을 삭제한다.
keySet(): Key 집합을 Set 형태로 반환한다.
entrySet(): Key-Value 쌍의 집합을 Set 형태로 반환한다.

HashMap 성능과 주의점

HashMap의 성능은 해시 함수의 성능, 해시 충돌 처리 방법 등에 따라 영향을 받는다.
데이터가 많아질수록 해시 충돌이 발생할 확률이 높아지므로, 충돌 처리 방법에 주의해야 한다.
Key의 해시값을 계산하기 위해 사용되는 객체의 equals()와 hashCode() 메소드는 올바르게 구현되어야 한다.
큰 데이터셋에 대해서는 대량의 메모리를 필요로 할 수 있으므로, 메모리 사용에 주의해야 한다.

HashMap의 시간복잡도

HashMap은 삽입, 검색에 시간복잡도 O(1)이라는 이점을 가지고 있다.
만약에 HashMap을 사용하지 않고 List를 사용했다면 원소를 검색하는데 시간복잡도는 O(n)일 것이다.
List를 사용한 문제가 효율성 테스트에 통과하지 못했다면, HashMap을 사용하여 시간복잡도를 줄여보자!

예제문제

해시 해킹(백준 26008번)

그린닷컴의 운영자 연두는 비밀번호를 평문 그대로 저장하는 과오를 뒤로하고, 이제부터 암호에 해시 함수를 적용해 저장하려고 한다. 연두가 아는 해시 함수라고는 알고리즘 문제 풀이에 많이 사용되는 롤링 해시 함수밖에 없기 때문에 이것을 응용하여 사용하기로 했다.

그린닷컴의 비밀번호 규칙은 꽤 특이한데, 길이가 정확히 $N$ 이어야 하며, 비밀번호를 이루는 문자는 지정된 $M$ 개의 문자 중 하나여야 한다. 따라서, 사용 가능한 각 문자를 $0$ 부터 차례대로 정수에 대응시키면, 비밀번호를 길이가 $N$ 이고 모든 원소가 $0$ 이상 $M-1$ 이하인 배열 $P = [P_0, P_1, \dots, P_{N-1} ]$ 로 나타낼 수 있다.

이렇게 비밀번호를 배열 $P$ 로 나타낸 후, 미리 정해진 정수 $A$ 를 이용하여 다음과 같은 해시 함수 $h$ 를 적용한다.

$h(P) = (P_0 \cdot A^0 + P_1 \cdot A^1 + ... + P_{N-1} \cdot A^{N-1}) \mod M$

예를 들어 배열 $P = [10, 30, 20], A = 7, M = 55$ 인 경우를 생각해보자. 이 경우 $h(P) = (10 \cdot 7^0 + 30 \cdot 7^1 + 20 \cdot 7^2) \mod 55 = (10 + 210 + 980) \mod 55 = 45$ 이다. 여기서 $\bmod$ 는 나머지 연산으로 $1200 = 21 \cdot 55 + 45$ 이므로 $1200 \mod 55 = 45$ 이다. 따라서 해시값은 항상 $0$ 이상 $M-1$ 이하의 정수이다.

그린닷컴 관리자 계정의 비밀번호 해시값을 해킹한 재현이는, 이 해시값으로 실제 비밀번호가 뭐였는지 역추적해보려고 한다. 하지만 그린닷컴에서 사용 가능한 비밀번호는 $M^N$ 개나 있고, 이 중 과연 알아낸 해시값과 일치하는 비밀번호는 몇 개나 될지 궁금해졌다. 여러분이 이것을 대신 구해주자.

입력
첫째 줄에 비밀번호의 길이 $N$ 과 문자 종류의 개수 $M$ , 정수 $A$ 가 주어진다. ( $1 \le N, M, A \le 5\,000\,000$ )

둘째 줄에 재현이가 알아낸 해시값 정수 $H$ 가 주어진다. ( $0 \le H < M$ )

출력
주어진 해시값을 갖는 비밀번호의 개수를 출력한다. 출력하는 값이 너무 커질 수 있으므로, 이것을 $1\,000\,000\,007 ( = 10^9 + 7)$ 로 나눈 나머지를 출력한다.

예제 입력 1
3 2 1
1
예제 출력 1
4

나의 생각

문제를 천천히 읽어보며 이해할 필요가 있다.
주어진 조건에서 구하려는 값은 모든 원소가 0부터 M-1까지의 값을 가질 수 있는 N의 길이의 배열에서 해시 함수를 적용하여 그 결과가 H가 되는 배열의 개수이다.
배열의 모든 원소는 지정된 M개의 문자 중 하나여야 하므로, 배열에서 중복되는 문자가 없다.
위 문장을 이해 시켜주겠다.
예로 M=3인 경우 P_i는 {0, 1, 2} 가 될 수 있다. 물론 {10, 92, 75} 이렇게 3개가 될 수도 있다. 중요한 점은 이 3개의 숫자가 중복되지 않는다는 것이다.
왜냐하면 M은 종류의 갯수를 의미하니까!! 3종류는 3개가 중복되지 않는 다는 의미이다.
문제로 다시 돌아가서, 한 원소를 선택하면, 그 원소에 어떤 값이 들어가든 상관없이 그 원소를 제외한 나머지 N-1개의 원소에 대해 모든값 M개를 가질 수있다.
예를 들면 M=3이고 P가 {0, 1, 2}일때, N=3 인 상황을 생각해보면서 비밀번호를 만들어보자 처음 숫자를 0으로 골랐다면, 다음 숫자(N-1개)는 M개 중 하나를 고를 수 있다는 뜻이다. (0, 1, 2 중 하나를 또 고르면 된다.) 즉, 조합 문제이다.
그러므로, 한 원소가 선택되면 가능한 배열의 개수는 M^(N-1)개가 되며, 어떤 원소든지 이 규칙을 따른다. 즉, M^(N-1)은 가능한 모든 배열의 개수이면서 어떤 해시값이 H인 배열의 개수이다.

정리

해시함수의 특성상, 서로 다른 P 배열이 같은 해시값을 가질 수 있다. 이 때문에 가능한 모든 P 배열 중에서 해시값이 H인 배열의 개수를 구하려면 모든 가능한 P 배열을 찾아보면서 해시값이 H인 배열의 개수를 찾아야 한다.
이 경우, 가능한 모든 배열의 개수는 M^N이 된다. 그리고 한 원소가 선택되면, 그 원소를 제외한 나머지 N-1개의 원소에 대해 모든 값 M개를 가질 수 있으므로, 가능한 배열의 개수는 M^(N-1)이 된다. 가능한 모든 배열 중에서 해시값이 H인 배열의 개수는 M^(N-1)이 된다.
맞다, 사실 그 해시값이 1인지 뭔지, 알수는 없다. 그러나 M^(N-1)개의 값이 해시값 H를 중복으로 갖고있다.
문제에서는 " $1\,000\,000\,007 ( = 10^9 + 7)$ 로 나눈 나머지를 출력한다." 라고 했으니 M^(N-1)에 나머지 연산만 해주면 문제가 해결된다!
결국 입력값 M과 N만 있어도 풀 수 있다??!!

다시

가능한 모든 배열 중에서 해시값이 H인 배열의 개수를 찾기 위해서는, 각각의 경우마다 P 배열을 만들어 해시 함수를 적용하고, 그 결과가 H인 경우의 수를 세어야 한다. 원래는

하지만, 해시함수의 특성상 M^(N-1)개의 value값들은 항상 같은 Key값(해시값 H)을 갖기 때문에, 가능한 배열의 개수는 M^(N-1)개이며, 이 값은 해시값이 H인 배열의 개수와 일치하게 된다.

구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        BigInteger n = new BigInteger(st.nextToken()); //비밀번호의 길이
        BigInteger m = new BigInteger(st.nextToken());//사용될 문자종류의 갯수
        BigInteger mod = BigInteger.valueOf(1000000007); // 나머지 연산 할 (10^9+7)
        System.out.println(m.modPow(n.subtract(BigInteger.ONE), mod));
  // BigInteger의 modPow는 매개변수 (a,b)가 있을 때, a승 하고 b로 나눈 나머지를 반환한다.
 //n.subtract(BigInteger.ONE)는 n-1을 의미한다. 여기서 n의 타입을 BigInteger으로 선언했으므로, 
 //int형 1과 '-' 연산할 수 없다. 밑에 이미지 참고
 
 		br.close();
    }
}