HashMap - 자료구조

목차 

1. HashMap이란?

2. 해싱

3. 버킷

4. 충돌처리 방법

  4-1) 체이닝

  4-2) 오픈 어드레싱

     4-2-1) 선형탐사

     4-2-2) 이차탐사

     4-2-3) 이중해싱

5. HashMap의 주요 메소드

6. 성능 특성 (시간복잡도 / 공간복잡도)

7. HashMap VS HashTable

8. 문제풀이 

---

👩‍💻 HashMap 이란? 

HashMap 은 Key와 Value가 쌍을 이뤄 저장되는 형태의 자료구조이다.

각 key는 고유하여 중복된 값을 가질 수 없으며 key를 사용하여 해당하는 Value에 접근하는 방식이다.

 

✏️ 해싱 (Hashing)

* Hash Map의 핵심이 되는 원리로 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정이다.

(해시 함수를 사용하여 키를 해시 코드로 변환하며 이 해시 코드는 HashMap 내부의 배열 인덱스로 사용된다. )

즉, 키가 해시 함수를 통해 배열의 특정 위치에 매핑된다.

- 해싱 함수 :키를 해시값으로 매핑하는 연산

- 해시 테이블 : 키-값을 연관시켜 저장하는 데이터 구조

 

✏️ 버킷 (Bucket)

같은 해시 코드를 갖는 키-값 쌍들은 같은 버킷에 저장된다. 각 버킷은 배열의 슬롯을 나타내며, 충돌이 발생하면 링크드 리스트나 트리 구조를 사용하여 저장한다.

 

✏️ 충돌 처리(Collision Handling)

해시 함수가 서로 다른 키들에 대해 동일한 해시 코드를 생성하는 경우 충돌이 발생한다. 이를 처리하는 두 가지 주요 방법은 체이닝(Chaining)과 오픈 어드레싱 (Open Addressing)이다. 체이닝은 각 버킷이 링크드 리스트를 사용하여 충돌을 해결하고, 오픈 어드레싱은 충돌이 발생한 경우 다른 빈 슬롯을 찾아 저장하는 것이다.

1)  체이닝(Chaining) 

체이닝은 각 버킷이 하나의 슬롯이 아니라 연결 리스트(Linked List)나 다른 컬렉션 구조를 가지고 있는 방식이다. 충돌이 발생하면 해당 슬롯에 값을 추가하는 대신 리스트에 새로운 값을 추가한다.

 

장점 : 

• 해시 테이블이 꽉 차는 문제가 없다.
• 삭제가 간단하다.

단점 : 

• 외부 저장 공간이 필요하다.
• 많은 충돌이 발생하면 리스트가 길어져서 성능 저하가 될 수 있다. 

2)  오픈 어드레싱(Open Addressing)

오픈 어드레싱은 충돌이 발생하면 다른 빈 슬롯을 찾아 삽입하는 방식이다. 주요 기법으로는 1. 선형 탐사(Linear Probing), 2. 이차 탐사(Quadratic Probing), 3. **이중 해싱(Double Hashing)**이 있다.

2-1) 선형 탐사 (Linear Probing)

충돌이 발생하면 정해진 간격(보통 1씩 증가)으로 다음 슬롯을 확인한다.

장점 : 추가적인 데이터 구조가 필요 없다.

단점 : 클러스터링 문제 발생 가능(많은 충돌이 인접한 슬롯에 몰리는 것) <- 군집화

 

2-2) 이차 탐사 (Quadratic Probing)

충돌이 발생하면 이차함수꼴 (ex) 1, 4, 9, 16 ... 형태로 슬롯을 확인한다.

장점 : 군집화를 줄여준다. 

단점 : 이차 함수에 따라 특정 패턴으로 이차 군집화가 일어날 수 있다. 

2-3) 이중 해싱 (Double Hashing)

충돌이 발생하면 두 번째 해시 함수를 사용하여 새로운 위치를 찾는 기법이다.

이중해싱시 두 가지의 해시 함수는 달라야 키를 더 잘 분배할 수 있다.

또한 해싱함수의 시간복잡도가 O(1)이여야 성능이 좋으며 두 번째 해시함수의 결과가 0이 되면 첫 번째 해시함수의 결과와 같아지므로 결과가 0이면 안된다. 

장점 : 군집화를 줄여준다.

단점 : 두 개의 해시 함수가 필요하다.

 

충돌 처리는 해시맵의 성능을 유지하는데 매우 중요하다.

체이닝은 외부 저장 공간을 사용하여 충돌을 해결하고, 오픈 어드레싱은 해시 테이블 자체에서 충돌을 해결한다. 

각 방법에는 위에 서술한 것과 같이 장 단점이 있으며, 특정 상황과 요구사항에 따라 적합한 방법을 선택해야 한다. 

 

 

✏️ HashMap의 주요 메서드

• put(K key, V value): 주어진 키와 값 쌍을 HashMap에 추가합니다. 만약 키가 이미 존재하면 해당 키의 값을 새 값으로 대체한다.
• get(Object key): 주어진 키에 해당하는 값을 반환한다. 만약 키가 존재하지 않으면 null을 반환한다.
• remove(Object key): 주어진 키와 그에 대응하는 값을 HashMap에서 제거한다.
• containsKey(Object key): 주어진 키가 HashMap에 존재하는지 여부를 반환한다.
• containsValue(Object value): 주어진 값이 HashMap에 하나 이상 존재하는지 여부를 반환한다.
• size(): HashMap에 저장된 키-값 쌍의 개수를 반환한다.

 

✏️성능 특성

• 시간 복잡도: HashMap은 평균적으로 O(1)의 시간 복잡도로 상수 시간에 키-값 쌍을 삽입, 삭제, 검색할 수 있다. 하지만 최악의 경우(모든 키가 같은 해시 코드를 가질 때)에는 O(n)의 시간이 걸릴 수 있다.
• 공간 복잡도: HashMap은 키-값 쌍을 저장하기 위해 추가적인 공간을 사용합니다. 충돌이 많을수록 더 많은 공간이 필요합니다.

 

✏️ Hash Map 과 Hash Table의 비교

공통점

• 해시 함수를 사용하여 데이터를 저장: 둘 다 내부적으로 해시 테이블을 사용하여 키를 해시 값으로 변환하고, 이를 통해 데이터를 저장한다. 
• 키-값 쌍: 둘 다 키-값 쌍으로 데이터를 저장하며, 키는 유일해야 한다.

차이점

1. 동기화 (Synchronization)

• Hashtable: 동기화된(synchronized) 메서드를 제공하여 스레드 안전합니다. 이는 멀티스레드 환경에서 동시에 여러 스레드가 Hashtable에 접근하더라도 문제가 발생하지 않도록 한다.
• HashMap: 동기화되지 않은 메서드를 제공하여 스레드 안전하지않다. 따라서 멀티스레드 환경에서 사용할 경우 외부에서 동기화를 처리해야 한다.

2. 성능 (Performance)

• Hashtable: 동기화 때문에 성능이 상대적으로 낮을 수 있다.
• HashMap: 동기화가 없어서 단일 스레드 환경에서 Hashtable보다 더 높은 성능을 제공한다.

3. Null 키와 값 (Null Keys and Values)

• Hashtable: 키와 값 모두 null을 허용하지 않는다.
• HashMap: 하나의 null 키와 여러 개의 null 값을 허용한다.

4. 초기 용량과 확장 (Initial Capacity and Load Factor)

• Hashtable: 기본 초기 용량은 11이고, 크기를 조정할 때 두 배로 증가한다. 기본 로드 팩터(load factor)는 0.75이다.
• HashMap: 기본 초기 용량은 16이고, 크기를 조정할 때 두 배로 증가한다. 기본 로드 팩터는 0.75로, 로드 팩터를 통해 해시 테이블의 밀도를 조정할 수 있다.

5. 상속 계층 구조 (Inheritance Hierarchy)

• Hashtable: Hashtable 클래스는 Dictionary 클래스를 상속받고 있으며, Map 인터페이스를 구현한다. 이는 Legacy 클래스이다.
• HashMap: HashMap 클래스는 AbstractMap 클래스를 상속받고 Map 인터페이스를 구현한다. 이는 더 현대적인 컬렉션 프레임워크의 일부이다.

결론: 

• HashMap은 더 유연하고, 성능이 우수하며, 싱글스레드 환경에서 사용하기 적합하다.
• Hashtable은 스레드 안전을 보장하지만, 성능이 떨어지고 현대적인 사용에는 덜 적합하다.

(멀티스레드 환경에서는 HashMap을 사용할 때 외부에서 동기화를 처리하거나 ConcurrentHashMap과 같은 스레드 안전한 대안을 고려할 수 있다)

 

 

✏️  관련 문제 풀이

1) 백준 26008번 : 해시해킹 (복습)

해당 문제는 해시함수의 이론에 대한 문제지만 풀이법은 그냥 수학적으로 다가가야 시간을 넘기지 않고 풀 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int a = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(br.readLine());

        long result = 1;
        for(int i=0; i<n-1; i++){
            result = (result * m) % 1000000007;
        }

        System.out.println(result % 1000000007);
    }
}

풀이 :

(h(p) = H)일 경우의 수 = M (왜냐하면 0 <= h(p) <= M-1 이므로)

또한  배열 P의 나올 수 있는 경우의 수는 길이가 N인 p들이 각각 0~M-1 사이의 값을 가지므로 M^N 개를 가진다.

따라서 h(p)가 구한 해싱값 H일 경우의 수 = 배열 P가 나올 수 있는 경우의 수 * h(p)의 값이 H일 확률 이므로

구하고자 하는 값 = M^(N) * (1/M) = M^(N-1) 이다.

문제에서는 값이 너무 커지는 것을 방지하기 위해서 주어진 조건으로 % 1000000007을 해가면서 문제를 풀었다.

 

2. 프로그래머스 : 해시_의상

import java.util.*;

class Solution {
    public int solution(String[][] clothes) {
        int answer = 1;

		// Map에 key값을 의상의 종류로 두고 key값이 중복되는 만큼 value에 count++
        Map<String, Integer> clothesMap = new HashMap<>();
        for(int i=0; i<clothes.length; i++){
            if(clothesMap.containsKey(clothes[i][1])){
                int temp = clothesMap.remove(clothes[i][1]) + 1;
                clothesMap.put(clothes[i][1], temp);
            }else{
                clothesMap.put(clothes[i][1], 1);
            }
        }

		// count를 모아둔 values값 가져오기
        Collection<Integer> values = clothesMap.values();

		// 경우의 수는 각 의상별로 가지고 있는 의상수가 x일때 (x+1)C1 <- 조합 을 모두 곱한 뒤 아예 안입은 경우 1을 빼는 것이다. 
        for(Integer val : values){
            answer *= (val + 1);
        }
        answer--;
        return answer;
    }
}

* 풀이는 어렵지 않게 풀었지만, 더 깔끔한 코드를 보았는데, Stream을 이용해서 푸는 방법을 더 공부해보면 좋을 것 같다!!

내가 푼 풀이랑 비슷하게는 Collection을 iterator로 불러오는것을 추가하는 정도?