Map 이란?

Map은 데이터를 모아서 관리할 수 있는 컬렉션입니다.
컬렉션은 그 타입에 따라 내부 데이터를 저장하는 구조와 처리 방법이 다릅니다. 내부에서 처리하는 방법에 따라 데이터의 탐색이 빠른 경우가 있고, 추가/제거가 빠른 경우가 있습니다.
사용하는 컬렉션의 특성을 잘 알고 사용해야 불필요한 성능 저하를 피할 수 있습니다.

0️⃣ 맵의 계층 구조

Untitled

1️⃣ HashMap - O(1)

가장 흔하게 사용되는 Map으로 내부적으로는 Entry 배열을 만들어서 관리한다.
map.put() 메서드를 이용해서 앤트리를 추가하면 key 값으로 넘겨준 객체의 해시코드를 계산하여 앤트리 배열의 접근 인덱스로 사용합니다.
- key1 이라는 문자열의 해시코드를 계산했을 때 10이라는 값이 나오면 배열의 10번째 항목으로 value를 저장하는 방법입니다.
HashMap의 해시값 계산은 자바 버전에 따라 다르지만 기본적으로 객체의 hashCode() 메서드의 리턴값을 기반으로 동작하게 됩니다. 또한 해시충돌(Hash Coliision)의 경우를 대비해 equals() 메서드까지 사용해서 key값이 정말 같은 경우에만 Value를 리턴해줍니다.
따라서 키 값으로 사용할 클래스의 특성에 따라 필요한 경우 hashCode() 메서드와 equals() 메서드를 오버라이드 해야 할 수도 있습니다.

Map<String, String> Map = new HashMap<>();

map.put("key1","value1");
map.put("key1","value1");

System.out.println(map.get("key1")); // value1

HashMap으로 관리되는 데이터 전체를 뽑을 때에는 순서가 뒤섞이게 됩니다. HashCode를 계산해서 사용하기 때문입니다.

Map<String, String> map = new HashMap<>();

map.put("Google","USA");
map.put("Naver","Korea");
map.put("Facebook","USA");

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

입력된 순서나 Key 값의 정렬 순서는 지켜지지 않고 다 섞이게 됩니다. 다만 다른 Map에 비해 빠른 탐색시간을 갖습니다.
해시 함수를 사용하기 때문에 O(1)의 시간복잡도를 가지게 됩니다.

해싱이란?

Untitled