1Page 노트정리 해시맵

May 23, 2024

1 Page 노트 정리

new repo

Hash와 Map 개념

Hash

해시(Hash): 입력 데이터를 고정된 길이의 데이터로 변환한 값을 말합니다. 이를 해시 값, 해시 코드, 체크섬이라고도 부릅니다.
해시 함수(Hash Function): 임의의 크기를 가진 입력 데이터를 고정된 크기의 데이터로 변환하는 함수입니다. 주로 데이터 검색과 저장을 효율적으로 하기 위해 사용됩니다.

Map

맵(Map): 키-값 쌍을 저장하는 추상 자료형(ADT, Abstract Data Type)입니다. 각 키는 유일하며 중복될 수 없습니다. 그러나 값은 중복될 수 있습니다.
다른 이름: 맵은 연관 배열(Associative array) 또는 딕셔너리(Dictionary)라고도 불립니다.
사용 사례: 키 값에 대응하는 값을 찾거나 매핑하고 싶을 때 사용합니다. 예를 들어, 영화의 제목을 키로, 평점을 값으로 저장하여 특정 영화의 평점을 빠르게 찾을 수 있습니다.

HashMap이란?

정의: HashMap은 Java의 Map 인터페이스를 구현한 컬렉션 클래스로, 키-값 쌍을 저장합니다.
특징:
- 삽입, 삭제, 조회 연산의 평균 시간 복잡도는 O(1)입니다.
- 키의 중복을 허용하지 않습니다.
- 입력된 데이터의 순서를 보장하지 않습니다.
- 동기화를 지원하지 않아 Thread-unsafe합니다.

HashMap과 HashTable 비교

HashMap: 비동기화로 인해 빠르지만 Thread-safe하지 않습니다.
HashTable: 동기화되어 Thread-safe하지만 상대적으로 느립니다.

HashMap의 동작 원리

기본 원리

해싱: 해시 함수를 사용하여 데이터를 고정된 크기의 해시 값으로 변환합니다.
버킷: 해시 값을 인덱스로 사용하여 데이터(키-값 쌍)를 저장합니다.

해시 충돌

해시 충돌: 서로 다른 키가 동일한 해시 값을 가질 때 발생합니다.
해결 방법:
- Separate Chaining: 충돌이 발생한 인덱스에서 연결 리스트를 사용하여 여러 항목을 저장합니다.
- Open Addressing: 충돌이 발생하면 다른 빈 인덱스를 찾아 저장합니다. 대표적으로 Linear Probing 방법이 있습니다.

Open Addressing은 해시 충돌을 해결하기 위한 방법 중 하나로, 충돌이 발생했을 때 다른 빈 슬롯을 찾아 데이터를 저장하는 방식입니다. Open Addressing의 주요 기법에는 Linear Probing, Quadratic Probing, 그리고 Double Hashing이 있습니다. 각각의 기법을 자세히 설명해 보겠습니다.

1. Linear Probing

Linear Probing은 충돌이 발생했을 때, 고정된 간격(보통 1)으로 다음 슬롯을 순차적으로 탐색하여 빈 슬롯을 찾는 방법입니다.

탐색 과정:
1. 충돌이 발생한 인덱스 i에서 시작합니다.
2. 인덱스 (i + 1) % 테이블 크기, (i + 2) % 테이블 크기, … 식으로 다음 슬롯을 탐색합니다.
3. 빈 슬롯을 찾거나 원래 슬롯으로 돌아올 때까지 탐색을 계속합니다.

장점:

구현이 간단합니다.
클러스터링 현상이 발생할 수 있습니다(인접한 슬롯들이 연속적으로 채워지기 시작하면, 충돌이 더 빈번해질 수 있음).

예시:

// 해시 함수: hash(key) = key % table_size
int index = (hash(key) + i) % table_size; // i는 0부터 시작하는 정수

2. Quadratic Probing

Quadratic Probing은 충돌이 발생했을 때, 일정한 간격이 아닌 점차적으로 증가하는 간격을 사용하여 빈 슬롯을 찾는 방법입니다.

탐색 과정:
1. 충돌이 발생한 인덱스 i에서 시작합니다.
2. 인덱스 (i + 1^2) % 테이블 크기, (i + 2^2) % 테이블 크기, (i + 3^2) % 테이블 크기, … 식으로 다음 슬롯을 탐색합니다.
3. 빈 슬롯을 찾거나 원래 슬롯으로 돌아올 때까지 탐색을 계속합니다.

장점:

클러스터링 문제를 완화할 수 있습니다.
2차 클러스터링 문제가 발생할 수 있습니다(간격이 제곱수로 증가하므로, 특정 패턴으로 충돌이 발생할 수 있음).

예시:

// 해시 함수: hash(key) = key % table_size
int index = (hash(key) + i * i) % table_size; // i는 0부터 시작하는 정수

3. Double Hashing

Double Hashing은 두 개의 해시 함수를 사용하여 충돌이 발생할 때마다 다른 해시 함수를 적용해 새로운 인덱스를 찾는 방법입니다.

탐색 과정:
1. 첫 번째 해시 함수 h1(key)로 인덱스 i를 계산합니다.
2. 충돌이 발생하면, 두 번째 해시 함수 h2(key)를 사용하여 이동할 간격을 결정합니다.
3. 인덱스 (i + j * h2(key)) % 테이블 크기 (j는 0부터 시작하는 정수)로 빈 슬롯을 탐색합니다.

장점:

클러스터링 문제를 효과적으로 줄일 수 있습니다.
충돌 해결을 위한 탐색 패턴이 다양해져 충돌을 줄일 수 있습니다.

예시:

// 해시 함수: h1(key) = key % table_size
// 두 번째 해시 함수: h2(key) = prime_number - (key % prime_number)
int index = (h1(key) + j * h2(key)) % table_size; // j는 0부터 시작하는 정수

표로 정리

기법	탐색 방식	장점	단점
Linear Probing	고정된 간격으로 다음 슬롯 순차 탐색	구현이 간단	클러스터링 문제
Quadratic Probing	점차적으로 증가하는 간격으로 슬롯 탐색	클러스터링 문제 완화	2차 클러스터링 문제 발생 가능
Double Hashing	두 번째 해시 함수로 간격 결정	클러스터링 문제 최소화	구현이 복잡

결론

Open Addressing의 각 기법은 해시 충돌을 해결하는 데 고유한 장단점을 가지고 있습니다.
Linear Probing은 가장 간단하지만 클러스터링 문제가 있습니다.
Quadratic Probing은 클러스터링 문제를 줄이지만 2차 클러스터링이 발생할 수 있습니다.
Double Hashing은 클러스터링 문제를 최소화하지만 구현이 복잡합니다.
해시 테이블의 특성과 사용 용도에 따라 적절한 기법을 선택하는 것이 중요합니다.

HashMap 사용법

주요 메서드

V get(Object key): 키에 대응하는 값을 반환합니다. 키가 존재하지 않으면 null을 반환합니다.
V getOrDefault(Object key, V defaultValue): 지정된 키가 존재하면 해당 값을, 그렇지 않으면 기본 값을 반환합니다.
V put(K key, V value): 키-값 쌍을 추가합니다.
V remove(Object key): 지정된 키에 대응하는 항목을 제거합니다.
void clear(): 모든 항목을 제거합니다.
boolean containsKey(Object key): 키가 존재하는지 확인합니다.
boolean containsValue(Object value): 값이 존재하는지 확인합니다.
boolean isEmpty(): 맵이 비어 있는지 확인합니다.
Set<K> keySet(): 모든 키를 포함하는 Set을 반환합니다.
V replace(K key, V value): 지정된 키에 대응하는 값을 새로운 값으로 대체합니다.

예제 코드

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, String> hashMap = new HashMap<>();
        
        // 데이터 삽입
        hashMap.put("혹성탈출", "9.22");
        
        // 데이터 조회
        System.out.println(hashMap.get("혹성탈출")); // 출력: "9.22"
        System.out.println(hashMap.getOrDefault("범죄도시4", "0")); // 출력: "0"
        
        // 전체 키 조회
        for (String key : hashMap.keySet()) {
            System.out.println(key + ": " + hashMap.get(key));
        }
        
        // 키와 값의 존재 여부 확인
        System.out.println(hashMap.containsKey("혹성탈출")); // true
        System.out.println(hashMap.containsKey("범죄도시4")); // false
        System.out.println(hashMap.containsValue("9.22")); // true
        System.out.println(hashMap.containsValue("10")); // false
    }
}

표로 정리

메서드	설명	시간 복잡도
`get(Object key)`	키에 대응하는 값을 반환	O(1)
`getOrDefault(Object key, V defaultValue)`	키가 없으면 기본 값 반환	O(1)
`put(K key, V value)`	키-값 쌍을 추가	O(1)
`remove(Object key)`	키에 대응하는 항목 제거	O(1)
`clear()`	모든 항목 제거	O(1)
`containsKey(Object key)`	키 존재 여부 확인	O(1)
`containsValue(Object value)`	값 존재 여부 확인	O(N)
`isEmpty()`	맵이 비어 있는지 확인	O(1)
`keySet()`	모든 키를 포함하는 Set 반환	O(1)
`replace(K key, V value)`	키에 대응하는 값을 대체	O(1)

결론

HashMap은 키-값 쌍을 효율적으로 관리할 수 있는 강력한 자료구조입니다. 해시 함수와 해시 테이블을 이용해 빠른 데이터 검색, 삽입, 삭제가 가능하며, 다양한 상황에서 유용하게 사용할 수 있습니다. 해시 충돌 해결 방법과 동작 원리를 이해하면 HashMap을 더욱 효과적으로 활용할 수 있습니다.

해시 해킹 성공

해시 함수와 모듈러 연산을 이용한 조합 개수 계산

해시 값을 H, 배열의 원소를 P, 곱해지는 숫자를 A, mod 연산할 수를 M이라고 정의합니다. 주어진 해시 함수는 다음과 같습니다:

H=(P 0 ×A 0 +P 1 ×A 1 +…+P n−1 ×A n−1 )modM

모듈러 연산을 M으로 하기 때문에 해시값은 0부터 (M-1) 사이의 값이 됩니다. P 배열을 어떤 수로 조합하더라도 결과는 0부터 (M-1) 사이의 값이 됩니다. P는 0부터 (M-1) 사이의 값을 가지며, P는 n개의 원소로 구성되므로 가능한 조합의 수는 ( M^n )이 됩니다.

조합 개수 계산

해시값 H가 가질 수 있는 P 배열의 조합 개수는 다음과 같습니다: ( M^n−1 )

코드 설명

모든 수를 입력받고 ( M^n−1 )을 계산하기 위해 반복문을 작성합니다.
문제에서 배열의 조합 개수가 너무 많을 경우를 대비해 1000000007로 나눈 값을 반환합니다.
( M^n−1 )의 수가 너무 클 경우 long 자료형에 다 담지 못할 것을 대비해 M을 곱할 때마다 1000000007로 나누어줍니다.
그리고 마지막에 한 번 더 1000000007로 나누어 정답을 반환합니다.
모듈로 연산의 곱셈 법칙을 이용한 연산: (A×B)modC=((AmodC)×(BmodC))

코드

import java.util.Scanner;

public class Main {
    public static void solution(int n, int m){
        long result = 1;
        for(int i = 0; i < n-1; i++){
            result = (result * m) % 1000000007;
        }
        long answer = result % 1000000007;
        System.out.println(answer);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        solution(n, m);
    }
}

요약

해시 함수의 정의와 그에 따른 해시 값 계산.
모듈로 연산의 곱셈 법칙을 이용하여 큰 수를 다루기 위한 방법.
Java 코드를 통해 ( M^{N-1} ) 값을 계산하고 1000000007로 나누어 반환하는 과정.

출처 : 백준, https://www.acmicpc.net/problem/26008

문제 설명

스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어, 스파이가 가진 옷이 다음과 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면, 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용해야 합니다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때, 서로 다른 옷의 조합의 수를 반환하는 solution 함수를 작성해주세요.

제한사항

clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
스파이가 가진 의상의 수는 1개 이상 30개 이하입니다.
같은 이름을 가진 의상은 존재하지 않습니다.
clothes의 모든 원소는 문자열로 이루어져 있습니다.
모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 ‘_‘로만 이루어져 있습니다.
스파이는 하루에 최소 한 개의 의상은 입습니다.

입출력 예

clothes	return
[[“yellowhat”, “headgear”], [“bluesunglasses”, “eyewear”], [“green_turban”, “headgear”]]	5
[[“crowmask”, “face”], [“bluesunglasses”, “face”], [“smoky_makeup”, “face”]]	3

입출력 예 설명

예제 #1: headgear에 해당하는 의상이 yellow_hat, green_turban이고 eyewear에 해당하는 의상이 blue_sunglasses이므로 아래와 같이 5개의 조합이 가능합니다.

yellow_hat
blue_sunglasses
green_turban
yellow_hat + blue_sunglasses
green_turban + blue_sunglasses

예제 #2: face에 해당하는 의상이 crow_mask, blue_sunglasses, smoky_makeup이므로 아래와 같이 3개의 조합이 가능합니다.

crow_mask
blue_sunglasses
smoky_makeup

문제 접근 방식

문제를 단순화하여 여러 종류의 옷이 있고, 각 종류별로 하나 이하를 입을 수 있을 때 가능한 모든 경우의 수를 계산하는 문제입니다. 예제를 단순화하면 다음과 같은 경우의 수를 계산할 수 있습니다.

단순화 예제 #1:

headgear의 경우의 수: 3 (yellow_hat, green_turban, 입지 않음)
eyewear의 경우의 수: 2 (blue_sunglasses, 입지 않음)

총 경우의 수는 (3 \times 2 = 6)가지이고, 이 중 한 가지는 모든 옷을 입지 않는 경우이므로 이를 제외하면 (6 - 1 = 5)가지가 정답이 됩니다.

해결책 1: 해시를 사용한 solution

해시를 통해 각 옷 종류별로 가짓수를 계산하고, 총 경우의 수를 산출할 수 있습니다.

import java.util.HashMap;
import java.util.Iterator;

class Solution {
    public int solution(String[][] clothes) {
        // 1. 옷을 종류별로 구분하기
        HashMap<String, Integer> map = new HashMap<>();
        for (String[] clothe : clothes) {
            String type = clothe[1];
            map.put(type, map.getOrDefault(type, 0) + 1);
        }

        // 2. 입지 않는 경우를 추가하여 모든 조합 계산하기
        Iterator<Integer> it = map.values().iterator();
        int answer = 1;
        
        while(it.hasNext())
            answer *= it.next().intValue() + 1;

        // 3. 아무 종류의 옷도 입지 않는 경우 제외하기
        return answer - 1;
    }
}

구현 설명

HashMap 만들기:
- HashMap<String, Integer>로 각 옷 종류를 Key, 해당 옷 종류의 가짓수를 Value로 설정합니다.
clothes 배열에 존재하는 모든 옷 종류의 count table 만들기:
- HashMap.put(Key, Value)를 사용하여 각 옷 종류별로 가짓수를 입력합니다.
- map.getOrDefault(type, 0) + 1을 사용하여 해당 종류의 옷 가짓수를 증가시킵니다.
각 옷 종류별 경우의 수를 answer에 곱해주기:
- 각 옷 종류별로 입지 않는 경우를 포함하여 경우의 수를 계산합니다.
- answer *= it.next().intValue() + 1을 사용하여 각 옷 종류별로 입지 않는 경우를 포함하여 곱해줍니다.
예외처리:
- 아무 종류의 옷도 입지 않는 경우를 제외하기 위해 마지막에 -1을 해줍니다.

출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42578

1Page 노트정리 해시맵

1 Page 노트 정리

Hash와 Map 개념

Hash

Map

HashMap이란?

HashMap과 HashTable 비교

HashMap의 동작 원리

기본 원리

해시 충돌

1. Linear Probing

2. Quadratic Probing

3. Double Hashing

표로 정리

결론

HashMap 사용법

주요 메서드

예제 코드

표로 정리

결론

해시 해킹 성공

해시 함수와 모듈러 연산을 이용한 조합 개수 계산

조합 개수 계산

코드 설명

코드

요약

문제 설명

제한사항

입출력 예

입출력 예 설명

문제 접근 방식

해결책 1: 해시를 사용한 solution

구현 설명

Leave a comment

You may also enjoy

김태원 8월 특강 정렬

김태원 8월 특강 그리디

스프링 핵심가이드 8주차

스프링 핵심가이드 7주차