[코딩테스트] 알고리즘 문제 유형 - Hash 자료구조

1. Hash 란?

• hash는 키(key)를 특정한 값(value)로 변환하는 방식입니다. 
• 데이터를 효율적으로 저장하고 검색하기 위해 사용합니다. 
• 해시함수(Hash Function)을 사용하여 키를 특정한 인덱스로 매핑합니다. 
• 자바에서는 hashCode() 메서드를 통해 기본적인 해시 값을 생성합니다. 

public class HashExample {
    public static void main(String[] args) {
        String str1 = "hello";
        String str2 = "world";

        System.out.println(str1.hashCode()); // 문자열 "hello"의 해시값 출력
        System.out.println(str2.hashCode()); // 문자열 "world"의 해시값 출력
    }
}

 

1) Hash 자료구조의 종류

1. HashSet
2. HashMap

---

2. 알고리즘 문제에서 해시를 활용하는 경우.

경우	방법
데이터 검색을 빠르게 해야 할 때	HashMap - 시간복잡도 O(1)
데이터 중복 저장을 방지해야 할 때	HashSet
등장 빈도/횟수를 빠르게 세야 할 때	HashMap (key: 요소, value: 횟수)
키-값 형태의 데이터를 저장할 때	HashMap

 

---

3. HashMap

• 키-값 형태로 데이터를 저장하는 자료구조

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();

        // 데이터 삽입 (put)
        map.put("apple", 3);
        map.put("banana", 5);
        map.put("cherry", 7);

        // 데이터 조회 (get)
        System.out.println("바나나 개수: " + map.get("banana")); // 출력: 5

        // 특정 키 존재 여부 확인 (containsKey)
        if (map.containsKey("apple")) {
            System.out.println("사과가 존재합니다.");
        }

        // 데이터 삭제 (remove)
        map.remove("cherry");

        // 전체 출력
        for (String key : map.keySet()) {
            System.out.println(key + " : " + map.get(key));
        }
    }
}

 

---

4. HashSet

• 중복을 허용하지 않는 자료구조
• 내부적으로 HashMap을 사용하여 데이터를 관리함. 
• 데이터 검색, 삽입, 삭제가 평균 O(1)

import java.util.HashSet;

public class HashSetExample {
    public static void main(String[] args) {
        HashSet<Integer> set = new HashSet<>();

        // 데이터 추가
        set.add(1);
        set.add(2);
        set.add(2); // 중복된 값 추가 (무시됨)
        set.add(3);

        // 데이터 포함 여부 확인
        System.out.println(set.contains(2)); // true
        System.out.println(set.contains(4)); // false

        // 데이터 삭제
        set.remove(2);

        // 전체 출력
        for (int num : set) {
            System.out.println(num);
        }
    }
}

 

---

5. Hash Collision(해시 충돌)

해시 충돌이란?

서로 다른 키가, 같은 해시값(인덱스)로 매핑되는 경우

HashCode() 결과값이 동일할 경우, eqauls() 메서드를 사용하여 두 값을 구분할 수 있다. 

 

해시 충돌을 해결하는 방법

1. 체이닝(Chaining)
   - 같은 해시 값을 가지는 데이터를 연결 리스트로 관리
   - 자바의 HashMap은 체이닝 방식을 사용함 
2. 오픈 어드레싱(Open Addressing)
   - 충돌 발생 시 다른 빈 공간을 찾아 데이터를 저장하는 방식

---

6. Hash 자료구조의 시간복잡도 & 공간복잡도

연산	평균 시간 복잡도	최악 시간 복잡도 (해시충돌)	공간 복잡도
삽입	O(1)	O(N)	O(N)
삭제	O(1)	O(N)	O(N)
탐색	O(1)	O(N)	O(N)

• 보통 해시 자료구조는 O(1)의 빠른 속도를 제공하지만, 해시 충돌이 많아지면 성능이 저하될 수 있다. 
• 해시 테이블이 가득 차면, 성능이 저하되기 때문에 적절하게 크기를 조정해주어야 한다. (리사이징)
• 해시 함수가 고르게 분포되지 않으면 충돌이 많아져서 시간 복잡도가 O(N)까지 증가할 수 있다.
  (N개의 모든 키 값에 대한 해시 함수에서 모두 충돌이 일어나는 경우)
• 충돌이 적고 데이터가 균등하게 분배되는 좋은 해시 함수를 설계하는 것이 중요하다.

---

7.  코딩테스트에서 해시를 활용하는 전략

 

1 ) HashMap을 사용한 빠른 데이터 탐색

ex. 어떠한 값이 존재하는지 빠르게 확인해야할 때 (주차타워에 6666번 차량이 존재하는지)

 

2 ) HashSet을 사용한 중복 제거

ex. 중복 원소를 제거해야할 때 (배열에서 중복 원소 제거, 주어진 데이터에서 유일한 값 찾기)

 

3 ) HashMap을 사용한 빈도수 계산

ex. 각 요소의 등장 횟수를 빠르게 계산해야 할 때 (문자열 내 각 문자의 개수 세기)