[Java] Hash란? - HashSet, HashMap 특징과 구현

오늘은 자료구조 중 하나인 Hash에 대해 알아보겠습니다.

 

Hash는 데이터를 효율적으로 저장하고 검색하기 위해 사용되는 자료구조 중 하나입니다.  Hash는 해시 함수(Hash Function)를 통해 입력 데이터를 고정된 크기의 값(해시 값 또는 해시 코드)으로 변환하고 고유한 해시 값(Hash Value)을 가지도록 설계 됩니다. 

 

Hash는 해시 테이블 구조를 사용하여 데이터를 매우 빠르게 검색할 수 있는 장점이 있습니다. 앞에서 말한 해시 값을 인덱스로 사용하여 데이터를 저장하고 접근할 수 있는 것이죠. (해시 테이블이란 키와 값을 함께 저장해 둔 데이터 구조를 말합니다.)

해시 테이블 예

 

---

 

HashSet과 HashMap 구현에 앞서 차이점을 살펴보도록 하겠습니다. 비슷해 보이는데 어떤 차이가 있을까요?

 

• HashSet : Set 인터페이스의 구현체이며 내부적으로 HashMap을 사용

HashMap을 내부적으로 사용한다고 함은, 데이터 저장 구조가 HashMap 기반으로 구현된다는 의미입니다.

Key 에는 객체 그 자체를 데이터로 저장, Value 값으로는 HashSet 내부 구현 코드에서 선언한 dummy 객체를 사용.

 

dummy 객체 저장? -> HashMap의 값 부분은 HashSet에서는 사용되지 않으므로, 모든 키에 대해 동일한 더미 객체를 value 값으로 저장함

 

 

• HashMap : Map 인터페이스의 구현체이며 해시 테이블과 유사한 형태로 데이터를 저장

Key - Value 형태로 데이터를 저장하며 각 value들이 key에 Mapping 되어 있습니다.

 

---

 

- 데이터 삽입은 HashSet의 경우 add() 메소드를 통해 삽입하고 HashMap의 경우 put() 메소드로 데이터를 삽입합니다. 

 

- 데이터 중복 허용 여부

 

HashSet의 경우 객체 자체를 저장하기 때문에 중복을 허용하지 않습니다.

ex. {"a", "b", "c"}

HashMap의 경우 중복 Key는 허용하지 않지만, Value는 중복을 허용합니다.

ex. {"a":2, "b":1, "c":2} 가능 / {"a":2, "b":1, "a":2} 불가능

 

 

HashSet 구현 (프로그래머스의 Lv.1 "폰켓몬" 문제)

import java.util.HashSet;

class Solution {
    public int solution(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        
        // 폰켓몬 종류를 HashSet에 추가 (폰켓몬 종류가 중복 없이 저장됨)
        for (int num : nums) {
            set.add(num);
        }
        
        // 선택할 수 있는 최대 폰켓몬 종류의 수는 nums.length / 2 이하
        return Math.min(nums.length / 2, set.size());
    }
}

 

 

HashMap 구현 (프로그래머스의 Lv.1 "완주하지 못한 선수" 문제)

import java.util.HashMap;

class Solution {
    public String solution(String[] participant, String[] completion) {
        // 참가자 명단을 저장할 HashMap 생성
        HashMap<String, Integer> map = new HashMap<>();
        
        // 참가자 명단을 순회하면서 HashMap에 이름과 해당 이름의 인원수를 저장
        for (String player : participant) {
            map.put(player, map.getOrDefault(player, 0) + 1);
        }
        
        // 완주자 명단을 순회하면서 HashMap에서 이름의 인원수를 감소
        for (String player : completion) {
            map.put(player, map.get(player) - 1);
        }
        
        // HashMap을 순회하면서 값이 1인 이름(완주하지 못한 선수)을 반환
        for (String key : map.keySet()) {
            if (map.get(key) > 0) {
                return key;
            }
        }
        
        // 모든 선수들이 완주한 경우(이 문제의 제약사항에서는 발생하지 않음)
        return null;
    }
}