[자료구조] 해시 맵(Hash Map)

해시 맵(Hash Map)이란?

자바에서 해시맵(HashMap)은 키(Key)와 값(Value) 쌍으로 이루어진 데이터를 저장하고 검색하는 데 사용되는 자료구조 중 하나다. 해시맵은 내부적으로 해시 함수(hash function)를 이용하여 키를 해시코드(hash code)로 변환하고, 이 해시코드를 기반으로 키-값 쌍을 저장하고 검색한다.

이름(Key)과 전화번호(Value)를 쌍으로 가진 해시

해시 맵의 특징

• 빠른 검색 속도: 해시맵은 해시 함수를 사용하여 키를 해시코드로 변환하고 이를 이용해 검색하기 때문에 빠른 검색 속도를 가짐
• 중복된 키를 허용하지 않음: 해시맵은 중복된 키를 허용하지 않기 때문에 새로운 값을 추가할 때 이미 존재하는 키가 있다면 이전 값은 덮어쓰게 됨 (값은 중복 가능)
• 순서가 보장되지 않음: 해시맵은 내부적으로 순서를 유지하지 않음. 따라서 값들을 순서대로 접근하는 것은 불가능함

 

해시 맵의 주요 명령어

• put(key, value) : 맵에 키와 값을 추가
• get(key) : 맵에서 키와 매핑된 값을 반환
• remove(key) : 맵에서 키와 매핑된 값을 제거하고 반환
• size() : 맵의 크기를 반환 (= 키와 값 쌍의 갯수)
• keySet() : 맵의 key들을 반환
• entrySet() : key와 value쌍을 가진 entry객체들을 반환

import java.util.HashMap;
import java.util.Map.Entry;

public class Main {
    public static void main(String[] args) {
        // 해시맵 생성
        HashMap<String, Integer> map = new HashMap<>();

        // 데이터 추가
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("mango", 3);

        // 데이터 접근
        System.out.println(map.get("apple")); // 1

        // 데이터 삭제
        System.out.println(map.remove("banana")); // 2

        // 해시맵 크기
        System.out.println(map.size()); // 2

        // 해시맵 반복문
        for (String key : map.keySet()) {
            System.out.println(key + " : " + map.get(key));
        }

        for (Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }
    }
}

해시 맵의 시간 복잡도

해시 함수를 사용하여 키를 해시코드로 변환하고, 이를 이용하여 데이터를 저장하고 검색하기 때문에 검색, 삽입, 삭제 모두 일반적으로 O(1)의 상수 시간(compute time)이 소요된다.