HashMap이란?
HashMap은 자바에서 가장 많이 사용되는 자료구조 중 하나로,
key-value 쌍으로 데이터를 저장하는 방식을 사용한다.
HashMap은 키(Key)를 기반으로 데이터를 저장하고,
검색 및 수정 작업을 빠르게 수행할 수 있도록 해준다.
HashMap은 많은 데이터를 저장할 때 빠르고 효율적인 자료구조이다.
하지만, key 값의 충돌(Collision)이 발생할 경우에는 성능이 저하될 수 있다.
따라서, HashMap을 사용할 때는 충돌을 최소화하기 위해 적절한 hash함수를 선택해야한다.
- Map 인터페이스를 구현한 컬렉션
- 키(Key)와 값(Value)으로 구성된 Entry 객체를 저장하는 구조를 가지는 자료구조
- 키는 중복 저장 불가능 X
- 값은 중복 저장 가능 O
- 기존에 저장된 키로 값을 저장하면 기존 값은 없어지고 새로운 값이 저장된다.
HashMap의 기본 구조
HashMap의 기본 구조는 배열과 연결리스트를 사용하여 구현되며,
배열은 데이터를 저장할 때 사용되고, 연결리스트는 충돌(Collision)이 발생했을 때 사용된다.
충돌이란, 서로 다른 key가 같은 hash 값을 갖는 경우를 말한다.
HashMap의 시간복잡도
HashMap은 key-value 쌍을 저장할 때 key를 hash함수를 통해 hash값으로 변환하여
배열의 인덱스로 사용한다.
이렇게 함으로써, 검색 및 수정 작업을 상수 시간 O(1)에 수행할 수 있다.
하지만, 충돌(Collision)이 발생하면, key값이 같은 데이터가 이미 저장되어 있는 경우이다.
이 경우에는 연결 리스트를 사용하여 데이터를 저장한다. 이 때, 연결 리스트의 길이가 길어지면 검색 및 수정 작업의 시간 복잡도는 선형 시간 O(n)으로 증가할 수 있다.
따라서, HashMap의 시간 복잡도는 다음과 같다.
데이터 추가: 상수 시간 O(1)
데이터 검색: 상수 시간 O(1) ~ 선형 시간 O(n)
데이터 삭제: 상수 시간 O(1) ~ 선형 시간 O(n)
가장 자주 사용되는 메소드들
자주 사용되는 get, put, getOrDefault 메소드에 대해서만 정리.
1. get(Object key)
- 주어진 키에 해당하는 값(Value)을 반환한다. 만약 키가 존재하지 않으면 null을 반환
HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 100);
map.put("banana", 200);
System.out.println(map.get("apple")); // 100
System.out.println(map.get("orange")); // null
2. put(K key, V value)
- 주어진 키(Key)와 값(Value)을 이용하여 새로운 키-값 쌍을 저장하고, 만약 같은 키가 이미 존재하면 값을 덮어쓴다.
HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 100);
map.put("banana", 200);
map.put("apple", 150); // 기존 키 "apple"의 값을 덮어씀
System.out.println(map.get("apple")); // 1503. getOrDefault(Object key, V defaultValue)
- 주어진 키에 해당하는 값(Value)을 반환합니다. 만약 키가 존재하지 않으면 기본값(defaultValue)을 반환한다.
HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 100);
map.put("banana", 200);
System.out.println(map.getOrDefault("apple", 0)); // 100
System.out.println(map.getOrDefault("orange", 0)); // 0이 외에도 containsKey(), remove(), size() 등 다양한 메서드가 제공된다.
